Pertanyaan Coba-tangkap mempercepat kodeku?


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 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: Jon Skeet luar biasa analisis menunjukkan bahwa coba-tangkap entah bagaimana menyebabkan x86 CLR menggunakan register CPU dengan cara yang lebih menguntungkan dalam kasus khusus ini (dan saya pikir kita belum memahami mengapa). Saya mengkonfirmasi temuan Jon bahwa x64 CLR tidak memiliki perbedaan ini, dan itu lebih cepat daripada x86 CLR. Saya juga diuji menggunakan int jenis di dalam metode Fibo, bukan long jenis, dan kemudian x86 CLR sama cepatnya dengan x64 CLR.


MEMPERBARUI: 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.


1338
2018-01-19 15:10


asal


Jawaban:


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

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

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

Juga, kami sedang bekerja pada perbaikan untuk Roslyn ke C # dan VB compiler 'algoritma untuk menentukan kapan penduduk setempat dapat dibuat "ephemeral" - yaitu, hanya mendorong dan muncul di stack, daripada mengalokasikan lokasi tertentu pada stack 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 setempat dapat dibuat "mati" sebelumnya.

Terima kasih telah menyampaikan ini kepada kami, dan mohon maaf atas perilaku aneh tersebut.


927
2018-01-20 20:14



Yah, caramu mengatur waktu semuanya terlihat sangat buruk bagiku. Akan jauh lebih masuk akal untuk hanya 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 cara itu Anda tidak pada belas kasihan timing kecil, floating point aritmatika dan akumulasi kesalahan.

Setelah membuat perubahan itu, lihat apakah "non-catch" versi masih lebih lambat daripada versi "catch".

EDIT: Oke, saya sudah mencobanya sendiri - dan saya melihat hasil yang sama. Sangat aneh. Saya bertanya-tanya apakah try / catch itu melumpuhkan beberapa penyisipan yang buruk, tetapi menggunakan [MethodImpl(MethodImplOptions.NoInlining)]malah tidak membantu ...

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

EDIT: Beberapa bit informasi lagi:

  • Menempatkan try / catch around just the n++; garis masih meningkatkan kinerja, tetapi tidak sebanyak meletakkannya di seluruh blok
  • Jika Anda menangkap pengecualian tertentu (ArgumentException dalam tes saya) masih cepat
  • Jika Anda mencetak pengecualian di blok tangkap, itu masih cepat
  • Jika Anda me-rethrow pengecualian di blok tangkap, itu lambat lagi
  • Jika Anda menggunakan blok yang akhirnya bukan blok tangkap, itu lambat lagi
  • Jika Anda menggunakan blok akhirnya sebaik blok tangkap, cepat

Aneh...

EDIT: Oke, kami telah melakukan pembongkaran ...

Ini menggunakan C # 2 compiler dan .NET 2 (32-bit) CLR, disassembling dengan mdbg (karena saya tidak memiliki cordbg pada mesin saya). Saya masih melihat efek kinerja yang sama, bahkan di bawah debugger. Versi cepat menggunakan try memblokir segala sesuatu di antara deklarasi variabel dan pernyataan kembali, hanya dengan a catch{} pawang Tentunya versi lambatnya sama kecuali tanpa try / catch. Kode panggilan (yaitu. Utama) adalah sama dalam kedua kasus, dan memiliki perwakilan perakitan yang sama (jadi ini bukan masalah inline).

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 itu * menunjukkan di mana debugger dimasukkan dalam "langkah-ke" sederhana.

EDIT: Oke, saya sekarang telah melihat melalui kode dan saya pikir saya bisa melihat bagaimana masing-masing versi berfungsi ... dan saya yakin versi yang lebih lambat lebih lambat karena menggunakan register lebih sedikit dan lebih banyak ruang stack. Untuk nilai-nilai kecil n itu mungkin lebih cepat - tetapi ketika loop mengambil sebagian besar waktu, itu lebih lambat.

Mungkin blok coba / tangkap pasukan lebih banyak register yang disimpan dan dipulihkan, sehingga JIT menggunakan mereka untuk loop juga ... yang terjadi untuk meningkatkan kinerja secara keseluruhan. Tidak jelas apakah itu keputusan yang masuk akal untuk JIT tidak gunakan sebagai banyak register dalam kode "normal".

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


702
2018-01-19 15:15



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

Compiler JIT membuat asumsi yang berbeda mengenai penggunaan register untuk kode yang berisi blok try-catch vs code 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 menghitung ini sebagai teknik percepatan umum.

Pada akhirnya, sangat sulit untuk mengatakan kode mana yang akan berakhir dengan tercepat. Sesuatu seperti alokasi register dan faktor-faktor yang mempengaruhinya adalah rincian implementasi tingkat rendah yang saya tidak melihat bagaimana teknik tertentu dapat menghasilkan kode yang lebih cepat.

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;
}

Salah satunya adalah versi generik dari yang lain. Mengganti tipe generik dengan StructArray akan membuat metode itu identik. Karena StructArray adalah tipe nilai, ia mendapatkan versi metode generik yang dikompilasi sendiri. Namun waktu berjalan sebenarnya jauh lebih lama daripada metode khusus, tetapi hanya untuk x86. Untuk x64, timingnya sangat mirip. Dalam kasus lain, saya telah mengamati perbedaan untuk x64 juga.


110
2018-01-19 18:27



Ini terlihat seperti kasus yang memburuk. Pada inti x86, jitter memiliki ebx, edx, esi dan edi register tersedia untuk penyimpanan tujuan umum dari variabel lokal. Register ecx tersedia dalam metode statis, tidak harus disimpan ini. Register eax sering diperlukan untuk perhitungan. Tapi ini adalah register 32-bit, untuk variabel tipe panjang itu harus menggunakan sepasang register. Yang merupakan edx: eax untuk perhitungan dan edi: ebx untuk penyimpanan.

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

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

Jitter akan melakukan yang terbaik untuk menerapkan optimasi generasi kode lain, itu akan mencoba untuk inline Anda Fibo () metode. Dengan kata lain, tidak membuat panggilan ke metode tetapi menghasilkan kode untuk metode inline dalam metode Main (). Pengoptimalan yang cukup penting yang, untuk satu, membuat properti kelas C # secara gratis, memberi mereka perf of a field. Ini menghindari overhead membuat panggilan metode dan pengaturan bingkai stack, menyimpan beberapa nanodetik.

Ada beberapa aturan yang menentukan kapan tepatnya sebuah metode dapat digarisbawahi. Mereka tidak persis didokumentasikan tetapi telah disebutkan dalam posting blog. Salah satu aturan adalah bahwa itu tidak akan terjadi ketika tubuh metode terlalu besar. Yang mengalahkan gain dari inlining, itu menghasilkan terlalu banyak kode yang tidak cocok juga di cache instruksi L1. Aturan keras lain yang berlaku di sini adalah bahwa metode tidak akan digarisbawahi ketika berisi pernyataan coba / tangkap. Latar belakang di balik itu adalah detail implementasi dari pengecualian, mereka kembali ke dukungan built-in Windows untuk SEH (Structure Exception Handling) yang berbasis stack-frame.

Satu perilaku algoritma alokasi register dalam jitter dapat disimpulkan dari bermain dengan kode ini. Tampaknya menyadari ketika jitter sedang mencoba untuk menyisipkan suatu metode. Satu aturan tampaknya menggunakan bahwa hanya pasangan register ex: eax dapat digunakan untuk kode inlined yang memiliki variabel lokal tipe panjang. Tapi tidak edi: ebx. Tidak diragukan lagi karena itu akan terlalu merugikan generasi kode untuk metode panggilan, baik edi dan ebx adalah register penyimpanan penting.

Jadi Anda mendapatkan versi cepat karena jitter tahu di depan bahwa tubuh metode berisi pernyataan try / catch. Ia tahu itu tidak pernah bisa di inline sehingga mudah menggunakan edi: ebx untuk penyimpanan untuk variabel panjang. Anda mendapat versi lambat karena jitter tidak tahu di depan bahwa inlining tidak akan berfungsi. Itu baru diketahui setelah menghasilkan kode untuk tubuh metode.

Kelemahannya adalah bahwa itu tidak kembali dan diperbarui kode untuk metode ini. Yang dapat dimengerti, mengingat keterbatasan waktu yang harus dioperasikan.

Pelambatan ini tidak terjadi pada x64 karena untuk itu ia memiliki 8 register lebih banyak. Untuk yang lain karena dapat menyimpan lama hanya dalam satu daftar (seperti rax). Dan slow-down tidak terjadi ketika Anda menggunakan int, bukan lama karena jitter memiliki lebih banyak fleksibilitas dalam memilih register.


65
2017-08-03 10:42



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


18
2018-01-20 13:15