Coba tangkap mempercepat kode saya?

1505

Saya menulis beberapa kode untuk menguji dampak try-catch, tetapi melihat beberapa hasil yang mengejutkan.

static void Main(string[] args)
{
    Thread.CurrentThread.Priority = ThreadPriority.Highest;
    Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.RealTime;

    long start = 0, stop = 0, elapsed = 0;
    double avg = 0.0;

    long temp = Fibo(1);

    for (int i = 1; i < 100000000; i++)
    {
        start = Stopwatch.GetTimestamp();
        temp = Fibo(100);
        stop = Stopwatch.GetTimestamp();

        elapsed = stop - start;
        avg = avg + ((double)elapsed - avg) / i;
    }

    Console.WriteLine("Elapsed: " + avg);
    Console.ReadKey();
}

static long Fibo(int n)
{
    long n1 = 0, n2 = 1, fibo = 0;
    n++;

    for (int i = 1; i < n; i++)
    {
        n1 = n2;
        n2 = fibo;
        fibo = n1 + n2;
    }

    return fibo;
}

Di komputer saya, ini secara konsisten mencetak nilai sekitar 0,96 ..

Ketika saya membungkus loop for di dalam Fibo () dengan blok try-catch seperti ini:

static long Fibo(int n)
{
    long n1 = 0, n2 = 1, fibo = 0;
    n++;

    try
    {
        for (int i = 1; i < n; i++)
        {
            n1 = n2;
            n2 = fibo;
            fibo = n1 + n2;
        }
    }
    catch {}

    return fibo;
}

Sekarang secara konsisten mencetak 0,69 ... - itu benar-benar berjalan lebih cepat! Tapi kenapa?

Catatan: Saya mengkompilasi ini menggunakan konfigurasi Release dan langsung menjalankan file EXE (di luar Visual Studio).

EDIT: Analisis Jon Skeet yang sangat baik menunjukkan bahwa try-catch entah bagaimana menyebabkan CLR x86 menggunakan register CPU dengan cara yang lebih menguntungkan dalam kasus khusus ini (dan saya pikir kita belum mengerti mengapa). Saya mengkonfirmasi temuan Jon bahwa x64 CLR tidak memiliki perbedaan ini, dan lebih cepat daripada x86 CLR. Saya juga menguji menggunakan inttipe di dalam metode Fibo, bukan longtipe, dan kemudian x86 CLR sama cepatnya dengan x64 CLR.


UPDATE: Sepertinya masalah ini telah diperbaiki oleh Roslyn. Mesin yang sama, versi CLR yang sama - masalah tetap seperti di atas ketika dikompilasi dengan VS 2013, tetapi masalahnya hilang ketika dikompilasi dengan VS 2015.

Eren Ersönmez
sumber
111
@ Lloyd ia mencoba mendapatkan jawaban atas pertanyaannya, "itu sebenarnya berjalan lebih cepat! Tapi mengapa?"
Andreas Niedermair
137
Jadi, sekarang "Menelan Pengecualian" beralih dari praktik yang buruk ke optimalisasi kinerja yang baik: P
Luciano
2
Apakah ini dalam konteks aritmatika yang tidak dicentang atau dicentang?
Random832
7
@ taras.roshko: Walaupun saya tidak ingin membuat Eric merugikan, ini bukan pertanyaan C # - ini adalah pertanyaan kompiler JIT. Kesulitan utama adalah mencari tahu mengapa x86 JIT tidak menggunakan banyak register tanpa try / catch seperti halnya dengan blok try / catch.
Jon Skeet
63
Manis, jadi jika kita mencoba menangkap ini, kita bisa lebih cepat, kan?
Chuck Pinkert

Jawaban:

1053

Salah satu insinyur Roslyn yang berspesialisasi dalam memahami optimalisasi penggunaan tumpukan melihat ini dan melaporkan kepada saya bahwa tampaknya ada masalah dalam interaksi antara cara kompiler C # menghasilkan toko variabel lokal dan cara kompiler JIT mendaftar. penjadwalan dalam kode x86 yang sesuai. Hasilnya adalah pembuatan kode suboptimal pada beban dan toko penduduk setempat.

Untuk beberapa alasan yang tidak jelas bagi kita semua, jalur pembuatan kode yang bermasalah dihindari ketika JITter tahu bahwa blok berada di wilayah yang dilindungi coba.

Ini sangat aneh. Kami akan menindaklanjuti dengan tim JITter dan melihat apakah kami dapat memasukkan bug sehingga mereka dapat memperbaikinya.

Selain itu, kami sedang mengerjakan perbaikan untuk algoritma Roslyn ke kompiler C # dan VB untuk menentukan kapan penduduk setempat dapat dibuat "sesaat" - yaitu, hanya didorong dan muncul di tumpukan, daripada mengalokasikan lokasi tertentu di tumpukan untuk durasi aktivasi. Kami percaya bahwa JITter akan dapat melakukan pekerjaan alokasi register yang lebih baik dan yang lainnya jika kami memberikan petunjuk yang lebih baik tentang kapan penduduk lokal dapat "mati" lebih awal.

Terima kasih telah membawa ini menjadi perhatian kami, dan meminta maaf atas perilaku aneh ini.

Eric Lippert
sumber
8
Saya selalu bertanya-tanya mengapa kompiler C # menghasilkan begitu banyak penduduk asing. Misalnya, ekspresi inisialisasi array baru selalu menghasilkan lokal, tetapi tidak pernah diperlukan untuk menghasilkan lokal. Jika ini memungkinkan JITter untuk menghasilkan kode performan yang lebih terukur, mungkin kompiler C # harus sedikit lebih berhati-hati dalam menghasilkan penduduk lokal yang tidak perlu ...
Timwi
33
@ Timwi: Tentu saja. Dalam kode yang tidak dioptimalkan, kompiler menghasilkan penduduk lokal yang tidak perlu dengan mengabaikan karena mereka membuat debug lebih mudah. Dalam kode yang dioptimalkan sementara waktu yang tidak perlu harus dihapus jika memungkinkan. Sayangnya kami memiliki banyak bug selama bertahun-tahun di mana kami secara tidak sengaja mengoptimalkan pengoptimal penghapusan sementara. Insinyur yang disebutkan di atas benar-benar melakukan kembali dari awal semua kode ini untuk Roslyn, dan sebagai hasilnya kita harus banyak memperbaiki perilaku yang dioptimalkan dalam generator kode Roslyn.
Eric Lippert
24
Apakah ada gerakan dalam masalah ini?
Robert Harvey
10
Sepertinya Roslyn memang memperbaikinya.
Eren Ersönmez
56
Anda melewatkan kesempatan Anda untuk menyebutnya "bug JITter".
mbomb007
734

Nah, cara Anda mengatur waktu hal-hal tampak sangat buruk bagi saya. Akan jauh lebih masuk akal untuk mengatur waktu seluruh loop:

var stopwatch = Stopwatch.StartNew();
for (int i = 1; i < 100000000; i++)
{
    Fibo(100);
}
stopwatch.Stop();
Console.WriteLine("Elapsed time: {0}", stopwatch.Elapsed);

Dengan begitu Anda tidak berada di bawah kekuasaan timing kecil, aritmatika floating point dan akumulasi kesalahan.

Setelah melakukan perubahan itu, lihat apakah versi "non-tangkapan" masih lebih lambat dari versi "tangkapan".

EDIT: Oke, saya sudah mencobanya sendiri - dan saya melihat hasil yang sama. Sangat aneh. Saya bertanya-tanya apakah mencoba / menangkap itu menonaktifkan beberapa inlining yang buruk, tetapi menggunakan[MethodImpl(MethodImplOptions.NoInlining)] bukannya tidak membantu ...

Pada dasarnya Anda harus melihat kode JITted yang dioptimalkan di bawah cordbg, saya kira ...

EDIT: Beberapa bit informasi lagi:

  • Menempatkan mencoba / menangkap hanya sekitar n++; garis masih meningkatkan kinerja, tetapi tidak sebanyak menempatkannya di seluruh blok
  • Jika Anda menangkap pengecualian tertentu (ArgumentException dalam pengujian saya) itu masih cepat
  • Jika Anda mencetak pengecualian di blok tangkap, itu masih cepat
  • Jika Anda mengubah kembali pengecualian di blok tangkap itu lambat lagi
  • Jika Anda menggunakan blok akhirnya bukan blok menangkap itu lambat lagi
  • Jika Anda menggunakan blok terakhir dan juga blok tangkap, itu cepat

Aneh...

EDIT: Oke, kami telah membongkar ...

Ini menggunakan kompiler C # 2 dan. NET 2 (32-bit) CLR, disassembling dengan mdbg (karena saya tidak punya cordbg di komputer saya). Saya masih melihat efek kinerja yang sama, bahkan di bawah debugger. Versi cepat menggunakan tryblok di sekitar segala sesuatu antara deklarasi variabel dan pernyataan kembali, hanya dengan catch{}handler. Tentunya versi lambatnya sama kecuali tanpa coba / tangkap. Kode panggilan (yaitu Utama) adalah sama dalam kedua kasus, dan memiliki perwakilan perakitan yang sama (jadi ini bukan masalah inlining).

Kode yang dibongkar untuk versi cepat:

 [0000] push        ebp
 [0001] mov         ebp,esp
 [0003] push        edi
 [0004] push        esi
 [0005] push        ebx
 [0006] sub         esp,1Ch
 [0009] xor         eax,eax
 [000b] mov         dword ptr [ebp-20h],eax
 [000e] mov         dword ptr [ebp-1Ch],eax
 [0011] mov         dword ptr [ebp-18h],eax
 [0014] mov         dword ptr [ebp-14h],eax
 [0017] xor         eax,eax
 [0019] mov         dword ptr [ebp-18h],eax
*[001c] mov         esi,1
 [0021] xor         edi,edi
 [0023] mov         dword ptr [ebp-28h],1
 [002a] mov         dword ptr [ebp-24h],0
 [0031] inc         ecx
 [0032] mov         ebx,2
 [0037] cmp         ecx,2
 [003a] jle         00000024
 [003c] mov         eax,esi
 [003e] mov         edx,edi
 [0040] mov         esi,dword ptr [ebp-28h]
 [0043] mov         edi,dword ptr [ebp-24h]
 [0046] add         eax,dword ptr [ebp-28h]
 [0049] adc         edx,dword ptr [ebp-24h]
 [004c] mov         dword ptr [ebp-28h],eax
 [004f] mov         dword ptr [ebp-24h],edx
 [0052] inc         ebx
 [0053] cmp         ebx,ecx
 [0055] jl          FFFFFFE7
 [0057] jmp         00000007
 [0059] call        64571ACB
 [005e] mov         eax,dword ptr [ebp-28h]
 [0061] mov         edx,dword ptr [ebp-24h]
 [0064] lea         esp,[ebp-0Ch]
 [0067] pop         ebx
 [0068] pop         esi
 [0069] pop         edi
 [006a] pop         ebp
 [006b] ret

Kode yang dibongkar untuk versi lambat:

 [0000] push        ebp
 [0001] mov         ebp,esp
 [0003] push        esi
 [0004] sub         esp,18h
*[0007] mov         dword ptr [ebp-14h],1
 [000e] mov         dword ptr [ebp-10h],0
 [0015] mov         dword ptr [ebp-1Ch],1
 [001c] mov         dword ptr [ebp-18h],0
 [0023] inc         ecx
 [0024] mov         esi,2
 [0029] cmp         ecx,2
 [002c] jle         00000031
 [002e] mov         eax,dword ptr [ebp-14h]
 [0031] mov         edx,dword ptr [ebp-10h]
 [0034] mov         dword ptr [ebp-0Ch],eax
 [0037] mov         dword ptr [ebp-8],edx
 [003a] mov         eax,dword ptr [ebp-1Ch]
 [003d] mov         edx,dword ptr [ebp-18h]
 [0040] mov         dword ptr [ebp-14h],eax
 [0043] mov         dword ptr [ebp-10h],edx
 [0046] mov         eax,dword ptr [ebp-0Ch]
 [0049] mov         edx,dword ptr [ebp-8]
 [004c] add         eax,dword ptr [ebp-1Ch]
 [004f] adc         edx,dword ptr [ebp-18h]
 [0052] mov         dword ptr [ebp-1Ch],eax
 [0055] mov         dword ptr [ebp-18h],edx
 [0058] inc         esi
 [0059] cmp         esi,ecx
 [005b] jl          FFFFFFD3
 [005d] mov         eax,dword ptr [ebp-1Ch]
 [0060] mov         edx,dword ptr [ebp-18h]
 [0063] lea         esp,[ebp-4]
 [0066] pop         esi
 [0067] pop         ebp
 [0068] ret

Dalam setiap kasus * ditampilkan di mana debugger dimasukkan dalam "langkah-ke" sederhana.

EDIT: Oke, saya sekarang telah melihat melalui kode dan saya pikir saya bisa melihat bagaimana setiap versi bekerja ... dan saya percaya versi lebih lambat lebih lambat karena menggunakan register lebih sedikit dan lebih banyak ruang tumpukan. Untuk nilai kecil dari nitu mungkin lebih cepat - tetapi ketika loop mengambil sebagian besar waktu, itu lebih lambat.

Mungkin blok coba / tangkap memaksa lebih banyak register untuk disimpan dan dipulihkan, sehingga JIT juga menggunakannya untuk loop ... yang terjadi untuk meningkatkan kinerja secara keseluruhan. Tidak jelas apakah ini merupakan keputusan yang masuk akal bagi JIT untuk tidak menggunakan sebanyak mungkin register dalam kode "normal".

EDIT: Baru saja mencoba ini di mesin x64 saya. CLR x64 jauh lebih cepat (sekitar 3-4 kali lebih cepat) daripada CLR x86 pada kode ini, dan di bawah x64 blok try / catch tidak membuat perbedaan yang nyata.

Jon Skeet
sumber
4
@GordonSimpson tetapi dalam kasus di mana hanya pengecualian tertentu yang ditangkap maka semua pengecualian lain tidak akan ditangkap, jadi apa pun overhead yang terlibat dalam hipotesis Anda untuk tidak dicoba masih diperlukan.
Jon Hanna
45
Sepertinya ada perbedaan dalam alokasi register. Versi cepat mengelola untuk digunakan esi,ediuntuk salah satu dari rindu, bukan tumpukan. Ini digunakan ebxsebagai penghitung, di mana versi lambat digunakan esi.
Jeffrey Sax
13
@JeffreySax: Ini bukan hanya yang register digunakan tapi berapa banyak. Versi lambat menggunakan lebih banyak ruang tumpukan, lebih sedikit menyentuh register. Saya tidak tahu mengapa ...
Jon Skeet
2
Bagaimana frame pengecualian CLR ditangani dalam hal register dan stack? Apakah pengaturan dapat membebaskan register untuk digunakan?
Random832
4
IIRC x64 memiliki lebih banyak register yang tersedia daripada x86. Speedup yang Anda lihat akan konsisten dengan try / catch yang memaksa penggunaan register tambahan di bawah x86.
Dan Is Fiddling By Firelight
116

Disassemblies Jon menunjukkan, bahwa perbedaan antara dua versi adalah bahwa versi cepat menggunakan sepasang register ( esi,edi) untuk menyimpan salah satu variabel lokal di mana versi lambat tidak.

Kompiler JIT membuat asumsi yang berbeda mengenai register yang digunakan untuk kode yang berisi blok try-catch vs. kode yang tidak. Ini menyebabkannya membuat pilihan alokasi register yang berbeda. Dalam hal ini, ini mendukung kode dengan blok try-catch. Kode yang berbeda dapat menyebabkan efek sebaliknya, jadi saya tidak akan menganggap ini sebagai teknik percepatan tujuan umum.

Pada akhirnya, sangat sulit untuk mengetahui kode mana yang akan berjalan paling cepat. Sesuatu seperti alokasi register dan faktor-faktor yang mempengaruhinya adalah detail implementasi tingkat rendah seperti itu sehingga saya tidak melihat bagaimana teknik spesifik mana pun dapat menghasilkan kode yang lebih cepat secara andal.

Sebagai contoh, perhatikan dua metode berikut. Mereka diadaptasi dari contoh kehidupan nyata:

interface IIndexed { int this[int index] { get; set; } }
struct StructArray : IIndexed { 
    public int[] Array;
    public int this[int index] {
        get { return Array[index]; }
        set { Array[index] = value; }
    }
}

static int Generic<T>(int length, T a, T b) where T : IIndexed {
    int sum = 0;
    for (int i = 0; i < length; i++)
        sum += a[i] * b[i];
    return sum;
}
static int Specialized(int length, StructArray a, StructArray b) {
    int sum = 0;
    for (int i = 0; i < length; i++)
        sum += a[i] * b[i];
    return sum;
}

Yang satu adalah versi generik yang lain. Mengganti tipe generik dengan StructArrayakan membuat metode identik. Karena StructArraymerupakan tipe nilai, ia mendapatkan versi kompilasi sendiri dari metode generik. Namun waktu berjalan sebenarnya jauh lebih lama daripada metode khusus, tetapi hanya untuk x86. Untuk x64, timingnya hampir sama. Dalam kasus lain, saya telah mengamati perbedaan untuk x64 juga.

Jeffrey Sax
sumber
6
Dengan itu dikatakan ... bisakah Anda memaksakan pilihan alokasi register yang berbeda tanpa menggunakan Try / Catch? Baik sebagai tes untuk hipotesis ini atau sebagai upaya umum untuk mengubah kecepatan?
WernerCD
1
Ada sejumlah alasan mengapa kasus spesifik ini mungkin berbeda. Mungkin itu adalah try-catch. Mungkin fakta bahwa variabel digunakan kembali dalam lingkup batin. Apa pun alasan spesifiknya, ini adalah detail implementasi yang tidak dapat Anda andalkan untuk dipertahankan meskipun kode yang sama persis dipanggil dalam program yang berbeda.
Jeffrey Sax
4
@WernerCD Saya akan mengatakan fakta bahwa C dan C ++ memiliki kata kunci untuk menyarankan bahwa yang (A) diabaikan oleh banyak kompiler modern dan (B) diputuskan untuk tidak dimasukkan ke dalam C #, menunjukkan bahwa ini bukan sesuatu yang kita ' Saya akan melihat dengan cara yang lebih langsung.
Jon Hanna
2
@WernerCD - Hanya jika Anda sendiri yang menulis rakitan
OrangeDog
72

Ini seperti kasus inlining menjadi buruk. Pada inti x86, jitter memiliki register ebx, edx, esi dan edi tersedia untuk penyimpanan tujuan umum variabel lokal. Register ecx tersedia dalam metode statis, tidak harus menyimpan ini . Register eax sering diperlukan untuk perhitungan. Tetapi ini adalah register 32-bit, untuk variabel tipe lama harus menggunakan sepasang register. Yaitu edx: eax untuk perhitungan dan edi: ebx untuk penyimpanan.

Itulah yang menonjol dalam pembongkaran untuk versi lambat, baik edi maupun ebx tidak digunakan.

Ketika jitter tidak dapat menemukan register yang cukup untuk menyimpan variabel lokal maka itu harus menghasilkan kode untuk memuat dan menyimpannya dari frame stack. Itu memperlambat kode, mencegah pengoptimalan prosesor yang dinamai "register renaming", trik pengoptimalan inti prosesor internal yang menggunakan banyak salinan register dan memungkinkan eksekusi super skalar. Yang memungkinkan beberapa instruksi untuk berjalan secara bersamaan, bahkan ketika mereka menggunakan register yang sama. Tidak memiliki register yang cukup adalah masalah umum pada core x86, dibahas di x64 yang memiliki 8 register tambahan (r9 hingga r15).

Jitter akan melakukan yang terbaik untuk menerapkan optimasi pembuatan kode lain, ia akan mencoba untuk menyatukan metode Fibo () Anda. Dengan kata lain, tidak membuat panggilan ke metode tetapi menghasilkan kode untuk metode inline dalam metode Main (). Optimasi yang cukup penting itu, untuk satu, membuat properti dari kelas C # gratis, memberi mereka perf bidang. Ini menghindari overhead membuat panggilan metode dan mengatur frame stack-nya, menghemat beberapa nanodetik.

Ada beberapa aturan yang menentukan kapan suatu metode dapat diuraikan. Mereka tidak benar-benar didokumentasikan tetapi telah disebutkan dalam posting blog. Satu aturan adalah bahwa itu tidak akan terjadi ketika tubuh metode terlalu besar. Itu mengalahkan keuntungan dari inlining, itu menghasilkan terlalu banyak kode yang tidak cocok juga di cache instruksi L1. Aturan keras lain yang berlaku di sini adalah bahwa suatu metode tidak akan diuraikan ketika berisi pernyataan coba-coba. Latar belakang di baliknya adalah detail implementasi pengecualian, mereka mendukung dukungan bawaan Windows untuk SEH (Structure Exception Handling) yang berbasis stack-frame.

Salah satu perilaku algoritma alokasi register dalam jitter dapat disimpulkan dari bermain dengan kode ini. Tampaknya menyadari ketika jitter sedang mencoba untuk sebaris metode. Satu aturan tampaknya hanya menggunakan pasangan edx: eax register yang dapat digunakan untuk kode inline yang memiliki variabel lokal bertipe panjang. Tapi tidak edi: ebx. Tidak diragukan lagi karena itu akan terlalu merusak pembuatan kode untuk metode pemanggilan, baik edi dan ebx adalah register penyimpanan yang penting.

Jadi Anda mendapatkan versi cepat karena jitter tahu di muka bahwa tubuh metode berisi pernyataan try / catch. Ia tahu itu tidak pernah bisa diuraikan jadi siap menggunakan edi: ebx untuk penyimpanan untuk variabel panjang. Anda mendapatkan versi lambat karena jitter tidak tahu di muka bahwa inlining tidak akan berfungsi. Itu hanya ditemukan setelah menghasilkan kode untuk badan metode.

Kelemahannya adalah ia tidak kembali dan menghasilkan kembali kode untuk metode ini. Ini bisa dimengerti, mengingat kendala waktu yang harus digunakan.

Perlambatan ini tidak terjadi pada x64 karena untuk yang memiliki 8 register lagi. Untuk yang lain karena bisa menyimpan lama hanya dalam satu register (seperti rax). Dan perlambatan tidak terjadi ketika Anda menggunakan int bukan panjang karena jitter memiliki lebih banyak fleksibilitas dalam memilih register.

Hans Passant
sumber
21

Saya akan menempatkan ini sebagai komentar karena saya benar-benar tidak yakin bahwa ini mungkin terjadi, tetapi seingat saya itu bukan percobaan / kecuali pernyataan melibatkan modifikasi pada cara mekanisme pembuangan sampah kompiler bekerja, dalam hal itu membersihkan alokasi memori objek secara rekursif dari stack. Mungkin tidak ada objek yang akan dibersihkan dalam kasus ini atau loop for dapat merupakan penutupan bahwa mekanisme pengumpulan sampah mengakui cukup untuk menegakkan metode pengumpulan yang berbeda. Mungkin tidak, tapi saya pikir itu layak disebut karena saya belum melihatnya dibahas di tempat lain.

menggiling gorila
sumber