Peningkatan kinerja yang aneh dalam tolok ukur sederhana

97

Kemarin saya menemukan artikel oleh Christoph Nahr berjudul ".NET Struct Performance" yang membandingkan beberapa bahasa (C ++, C #, Java, JavaScript) untuk metode yang menambahkan dua titik struct (double tupel).

Ternyata, versi C ++ membutuhkan waktu sekitar 1000ms untuk dieksekusi (1e9 iterations), sementara C # tidak bisa di bawah ~ 3000ms pada mesin yang sama (dan berkinerja lebih buruk di x64).

Untuk mengujinya sendiri, saya mengambil kode C # (dan sedikit disederhanakan untuk memanggil hanya metode di mana parameter diteruskan oleh nilai), dan menjalankannya pada mesin i7-3610QM (dorongan 3.1Ghz untuk inti tunggal), RAM 8GB, Win8. 1, menggunakan .NET 4.5.2, RELEASE build 32-bit (x86 WoW64 karena OS saya 64-bit). Ini adalah versi yang disederhanakan:

public static class CSharpTest
{
    private const int ITERATIONS = 1000000000;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static Point AddByVal(Point a, Point b)
    {
        return new Point(a.X + b.Y, a.Y + b.X);
    }

    public static void Main()
    {
        Point a = new Point(1, 1), b = new Point(1, 1);

        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms", 
            a.X, a.Y, sw.ElapsedMilliseconds);
    }
}

Dengan Pointdidefinisikan secara sederhana:

public struct Point 
{
    private readonly double _x, _y;

    public Point(double x, double y) { _x = x; _y = y; }

    public double X { get { return _x; } }

    public double Y { get { return _y; } }
}

Menjalankannya menghasilkan hasil yang mirip dengan yang ada di artikel:

Result: x=1000000001 y=1000000001, Time elapsed: 3159 ms

Pengamatan aneh pertama

Karena metode ini harus sebaris, saya bertanya-tanya bagaimana kode akan bekerja jika saya menghapus struct sama sekali dan hanya memasukkan semuanya bersama-sama:

public static class CSharpTest
{
    private const int ITERATIONS = 1000000000;

    public static void Main()
    {
        // not using structs at all here
        double ax = 1, ay = 1, bx = 1, by = 1;

        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
        {
            ax = ax + by;
            ay = ay + bx;
        }
        sw.Stop();

        Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms", 
            ax, ay, sw.ElapsedMilliseconds);
    }
}

Dan mendapatkan hasil yang hampir sama (sebenarnya 1% lebih lambat setelah beberapa kali percobaan ulang), yang berarti bahwa JIT-ter tampaknya melakukan pekerjaan yang baik dengan mengoptimalkan semua pemanggilan fungsi:

Result: x=1000000001 y=1000000001, Time elapsed: 3200 ms

Ini juga berarti bahwa tolok ukur tampaknya tidak mengukur structkinerja apa pun dan sebenarnya hanya tampak mengukur dasardouble aritmatika (setelah yang lainnya dioptimalkan).

Hal-hal aneh

Sekarang sampai pada bagian yang aneh. Jika saya hanya menambahkan stopwatch lain di luar loop (ya, saya mempersempitnya ke langkah gila ini setelah beberapa percobaan ulang), kode berjalan tiga kali lebih cepat :

public static void Main()
{
    var outerSw = Stopwatch.StartNew();     // <-- added

    {
        Point a = new Point(1, 1), b = new Point(1, 1);

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms",
            a.X, a.Y, sw.ElapsedMilliseconds);
    }

    outerSw.Stop();                         // <-- added
}

Result: x=1000000001 y=1000000001, Time elapsed: 961 ms

Konyol! Dan itu tidak seperti ituStopwatch memberi saya hasil yang salah karena saya dapat dengan jelas melihat bahwa itu berakhir setelah satu detik.

Adakah yang bisa memberi tahu saya apa yang mungkin terjadi di sini?

(Memperbarui)

Berikut adalah dua metode dalam program yang sama, yang menunjukkan bahwa alasannya bukan JIT:

public static class CSharpTest
{
    private const int ITERATIONS = 1000000000;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static Point AddByVal(Point a, Point b)
    {
        return new Point(a.X + b.Y, a.Y + b.X);
    }

    public static void Main()
    {
        Test1();
        Test2();

        Console.WriteLine();

        Test1();
        Test2();
    }

    private static void Test1()
    {
        Point a = new Point(1, 1), b = new Point(1, 1);

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Test1: x={0} y={1}, Time elapsed: {2} ms", 
            a.X, a.Y, sw.ElapsedMilliseconds);
    }

    private static void Test2()
    {
        var swOuter = Stopwatch.StartNew();

        Point a = new Point(1, 1), b = new Point(1, 1);

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Test2: x={0} y={1}, Time elapsed: {2} ms", 
            a.X, a.Y, sw.ElapsedMilliseconds);

        swOuter.Stop();
    }
}

Keluaran:

Test1: x=1000000001 y=1000000001, Time elapsed: 3242 ms
Test2: x=1000000001 y=1000000001, Time elapsed: 974 ms

Test1: x=1000000001 y=1000000001, Time elapsed: 3251 ms
Test2: x=1000000001 y=1000000001, Time elapsed: 972 ms

Ini pastebin. Anda perlu menjalankannya sebagai rilis 32-bit di .NET 4.x (ada beberapa pemeriksaan dalam kode untuk memastikan ini).

(Perbarui 4)

Mengikuti komentar @ usr tentang jawaban @Hans, saya memeriksa pembongkaran yang dioptimalkan untuk kedua metode, dan mereka agak berbeda:

Test1 di kiri, Test2 di kanan

Hal ini tampaknya menunjukkan bahwa perbedaan mungkin disebabkan oleh penyusun bertingkah lucu dalam kasus pertama, daripada perataan bidang ganda?

Juga, jika saya menambahkan dua variabel (offset total 8 byte), saya masih mendapatkan peningkatan kecepatan yang sama - dan sepertinya tidak lagi terkait dengan penyejajaran bidang yang disebutkan oleh Hans Passant:

// this is still fast?
private static void Test3()
{
    var magical_speed_booster_1 = "whatever";
    var magical_speed_booster_2 = "whatever";

    {
        Point a = new Point(1, 1), b = new Point(1, 1);

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Test2: x={0} y={1}, Time elapsed: {2} ms",
            a.X, a.Y, sw.ElapsedMilliseconds);
    }

    GC.KeepAlive(magical_speed_booster_1);
    GC.KeepAlive(magical_speed_booster_2);
}
c# performance benchmarking cil Groo
sumber
1
Selain JIT, itu juga tergantung pada optimasi kompiler, Ryujit terbaru melakukan lebih banyak optimasi dan bahkan memperkenalkan dukungan instruksi SIMD terbatas.
Felix K.
3
Jon Skeet menemukan masalah kinerja dengan bidang hanya baca di struct: Pengoptimalan mikro: ketidakefisienan bidang hanya baca yang mengejutkan . Cobalah membuat bidang pribadi tidak hanya-baca.
dbc
2
@dbc: Saya melakukan tes hanya dengan doublevariabel lokal , tidak structs, jadi saya telah mengesampingkan inefisiensi pemanggilan metode / tata letak struct.
Groo
3
Sepertinya hanya terjadi pada 32-bit, dengan RyuJIT, saya mendapatkan 1600ms kedua kali.
leppie
2
Saya telah melihat pembongkaran kedua metode. Tidak ada yang menarik untuk dilihat. Test1 menghasilkan kode yang tidak efisien tanpa alasan yang jelas. Bug JIT atau desain. Dalam Test1, JIT memuat dan menyimpan ganda untuk setiap iterasi ke tumpukan. Ini bisa untuk memastikan presisi yang tepat karena unit float x86 menggunakan presisi internal 80 bit. Saya menemukan bahwa pemanggilan fungsi non-inline di bagian atas fungsi membuatnya berjalan cepat lagi.
usr

Jawaban:

10

Pembaruan 4 menjelaskan masalah: dalam kasus pertama, JIT menyimpan nilai yang dihitung (a ,b ) di tumpukan; dalam kasus kedua, JIT menyimpannya di register.

Bahkan, Test1bekerja lambat karena Stopwatch. Saya menulis patokan minimal berikut berdasarkan BenchmarkDotNet :

[BenchmarkTask(platform: BenchmarkPlatform.X86)]
public class Jit_RegistersVsStack
{
    private const int IterationCount = 100001;

    [Benchmark]
    [OperationsPerInvoke(IterationCount)]
    public string WithoutStopwatch()
    {
        double a = 1, b = 1;
        for (int i = 0; i < IterationCount; i++)
        {
            // fld1  
            // faddp       st(1),st
            a = a + b;
        }
        return string.Format("{0}", a);
    }

    [Benchmark]
    [OperationsPerInvoke(IterationCount)]
    public string WithStopwatch()
    {
        double a = 1, b = 1;
        var sw = new Stopwatch();
        for (int i = 0; i < IterationCount; i++)
        {
            // fld1  
            // fadd        qword ptr [ebp-14h]
            // fstp        qword ptr [ebp-14h]
            a = a + b;
        }
        return string.Format("{0}{1}", a, sw.ElapsedMilliseconds);
    }

    [Benchmark]
    [OperationsPerInvoke(IterationCount)]
    public string WithTwoStopwatches()
    {
        var outerSw = new Stopwatch();
        double a = 1, b = 1;
        var sw = new Stopwatch();
        for (int i = 0; i < IterationCount; i++)
        {
            // fld1  
            // faddp       st(1),st
            a = a + b;
        }
        return string.Format("{0}{1}", a, sw.ElapsedMilliseconds);
    }
}

Hasil di komputer saya:

BenchmarkDotNet=v0.7.7.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-4702MQ CPU @ 2.20GHz, ProcessorCount=8
HostCLR=MS.NET 4.0.30319.42000, Arch=64-bit  [RyuJIT]
Type=Jit_RegistersVsStack  Mode=Throughput  Platform=X86  Jit=HostJit  .NET=HostFramework

             Method |   AvrTime |    StdDev |       op/s |
------------------- |---------- |---------- |----------- |
   WithoutStopwatch | 1.0333 ns | 0.0028 ns | 967,773.78 |
      WithStopwatch | 3.4453 ns | 0.0492 ns | 290,247.33 |
 WithTwoStopwatches | 1.0435 ns | 0.0341 ns | 958,302.81 |

Seperti yang bisa kita lihat:

  • WithoutStopwatch bekerja dengan cepat (karena a = a + b menggunakan register)
  • WithStopwatch bekerja lambat (karena a = a + b menggunakan tumpukan)
  • WithTwoStopwatches bekerja dengan cepat lagi (karena a = a + b menggunakan register)

Perilaku JIT-x86 bergantung pada sejumlah besar kondisi yang berbeda. Untuk beberapa alasan, stopwatch pertama memaksa JIT-x86 menggunakan tumpukan, dan stopwatch kedua memungkinkannya menggunakan register lagi.

AndreyAkinshin
sumber
Ini tidak menjelaskan penyebabnya. Jika Anda memeriksa tes saya, akan terlihat bahwa tes yang memiliki tambahan Stopwatchsebenarnya berjalan lebih cepat . Tetapi jika Anda menukar urutan pemanggilannya dalam Mainmetode, maka metode lain akan dioptimalkan.
Groo
75

Ada cara yang sangat sederhana untuk selalu mendapatkan versi "cepat" dari program Anda. Project> Properties> Build tab, hapus centang pada opsi "Lebih suka 32-bit", pastikan bahwa pemilihan target Platform adalah AnyCPU.

Anda benar-benar tidak suka 32-bit, sayangnya selalu diaktifkan secara default untuk proyek C #. Secara historis, toolset Visual Studio bekerja jauh lebih baik dengan proses 32-bit, masalah lama yang telah dihilangkan oleh Microsoft. Saatnya untuk menghapus opsi itu, VS2015 secara khusus membahas beberapa blok jalan terakhir ke kode 64-bit dengan jitter x64 baru dan dukungan universal untuk Edit + Lanjutkan.

Cukup obrolan, apa yang Anda temukan adalah pentingnya keselarasan variabel. Prosesor sangat mempedulikannya. Jika sebuah variabel tidak sejajar dalam memori maka prosesor harus melakukan pekerjaan ekstra untuk mengacak byte untuk mendapatkan mereka dalam urutan yang benar. Ada dua masalah ketidaksejajaran yang berbeda, salah satunya adalah di mana byte masih berada di dalam satu baris cache L1, yang memerlukan siklus tambahan untuk menggesernya ke posisi yang benar. Dan yang lebih buruk, yang Anda temukan, di mana sebagian byte berada dalam satu baris cache dan sebagian lagi di baris lain. Itu membutuhkan dua akses memori terpisah dan merekatkannya bersama. Tiga kali lebih lambat.

Tipe doubledan longadalah pembuat masalah dalam proses 32-bit. Mereka berukuran 64-bit. Dan bisa jadi tidak sejajar dengan 4, CLR hanya bisa menjamin keselarasan 32-bit. Bukan masalah dalam proses 64-bit, semua variabel dijamin diselaraskan ke 8. Juga alasan yang mendasari mengapa bahasa C # tidak dapat menjanjikan mereka untuk menjadi atom . Dan mengapa array ganda dialokasikan di Large Object Heap ketika mereka memiliki lebih dari 1000 elemen. LOH memberikan jaminan penyelarasan 8. Dan menjelaskan mengapa menambahkan variabel lokal menyelesaikan masalah, referensi objek adalah 4 byte sehingga memindahkan variabel ganda sebesar 4, sekarang membuatnya selaras. Kebetulan.

Kompiler 32-bit C atau C ++ melakukan pekerjaan ekstra untuk memastikan bahwa double tidak dapat disejajarkan. Bukan masalah yang sederhana untuk dipecahkan, tumpukan dapat menjadi tidak sejajar ketika sebuah fungsi dimasukkan, mengingat bahwa satu-satunya jaminan adalah bahwa ia selaras dengan 4. Prolog dari fungsi tersebut perlu melakukan pekerjaan ekstra untuk membuatnya sejajar dengan 8. Trik yang sama tidak berfungsi dalam program yang dikelola, pengumpul sampah sangat peduli tentang di mana tepatnya variabel lokal berada dalam memori. Diperlukan agar dapat menemukan bahwa objek di heap GC masih direferensikan. Itu tidak dapat menangani dengan baik variabel seperti yang dipindahkan oleh 4 karena tumpukan tidak selaras saat metode dimasukkan.

Ini juga masalah mendasar dengan kegugupan .NET yang tidak mendukung instruksi SIMD dengan mudah. Mereka memiliki persyaratan penyelarasan yang jauh lebih kuat, jenis yang tidak dapat diselesaikan oleh prosesor dengan sendirinya. SSE2 membutuhkan penyelarasan 16, AVX membutuhkan penyelarasan 32. Tidak bisa mendapatkan itu dalam kode yang dikelola.

Last but not least, perhatikan juga bahwa ini membuat kinerja program C # yang berjalan dalam mode 32-bit sangat tidak dapat diprediksi. Saat Anda mengakses double atau long yang disimpan sebagai kolom di objek, kinerja dapat berubah secara drastis saat pengumpul sampah memadatkan heap. Yang memindahkan objek dalam memori, bidang seperti itu sekarang bisa tiba-tiba menjadi salah / sejajar. Sangat acak tentu saja, bisa sangat membingungkan :)

Tidak ada perbaikan sederhana kecuali satu, kode 64-bit adalah masa depan. Hapus pemaksaan jitter selama Microsoft tidak mengubah template proyek. Mungkin versi selanjutnya saat mereka merasa lebih percaya diri dengan Ryujit.

Hans Passant
sumber
1
Tidak yakin bagaimana penyelarasan berperan dalam hal ini ketika variabel ganda bisa (dan berada di Test2) terdaftar. Test1 menggunakan tumpukan, Test2 tidak.
usr
2
Pertanyaan ini berubah terlalu cepat untuk saya ikuti. Anda harus berhati-hati terhadap tes itu sendiri yang mempengaruhi hasil tes. Anda perlu meletakkan [MethodImpl (MethodImplOptions.NoInlining)] pada metode pengujian untuk membandingkan apel dengan jeruk. Anda sekarang akan melihat bahwa pengoptimal dapat menyimpan variabel di tumpukan FPU dalam kedua kasus.
Hans Passant
4
Ya ampun, itu benar. Mengapa penyelarasan metode berdampak pada instruksi yang dibuat ?! Seharusnya tidak ada perbedaan apa pun untuk badan loop. Semua harus dalam register. Prolog penyelarasan harus tidak relevan. Sepertinya masih ada bug JIT.
usr
3
Saya harus merevisi jawabannya secara signifikan, payah. Saya akan membahasnya besok.
Hans Passant
2
@HansPassant apakah Anda akan menggali melalui sumber JIT? Itu akan menyenangkan. Pada titik ini yang saya tahu adalah bug JIT acak.
usr
5

Mempersempitnya (tampaknya hanya memengaruhi runtime CLR 4.0 32-bit).

Perhatikan penempatan var f = Stopwatch.Frequency;make all the difference.

Lambat (2700ms):

static void Test1()
{
  Point a = new Point(1, 1), b = new Point(1, 1);
  var f = Stopwatch.Frequency;

  var sw = Stopwatch.StartNew();
  for (int i = 0; i < ITERATIONS; i++)
    a = AddByVal(a, b);
  sw.Stop();

  Console.WriteLine("Test1: x={0} y={1}, Time elapsed: {2} ms",
      a.X, a.Y, sw.ElapsedMilliseconds);
}

Cepat (800ms):

static void Test1()
{
  var f = Stopwatch.Frequency;
  Point a = new Point(1, 1), b = new Point(1, 1);

  var sw = Stopwatch.StartNew();
  for (int i = 0; i < ITERATIONS; i++)
    a = AddByVal(a, b);
  sw.Stop();

  Console.WriteLine("Test1: x={0} y={1}, Time elapsed: {2} ms",
      a.X, a.Y, sw.ElapsedMilliseconds);
}
leppie
sumber
Memodifikasi kode tanpa menyentuh Stopwatchjuga mengubah kecepatan secara drastis. Mengubah tanda tangan metode Test1(bool warmup)dan menambahkan kondisional dalam Consoleoutput: if (!warmup) { Console.WriteLine(...); }juga memiliki efek yang sama (tersandung pada ini saat membangun pengujian saya untuk merepro masalah).
peralihan
@InBetween: Saya melihat, ada sesuatu yang mencurigakan. Juga hanya terjadi pada struct.
leppie
4

Tampaknya ada beberapa bug di Jitter karena perilakunya bahkan lebih aneh. Perhatikan kode berikut:

public static void Main()
{
    Test1(true);
    Test1(false);
    Console.ReadLine();
}

public static void Test1(bool warmup)
{
    Point a = new Point(1, 1), b = new Point(1, 1);

    Stopwatch sw = Stopwatch.StartNew();
    for (int i = 0; i < ITERATIONS; i++)
        a = AddByVal(a, b);
    sw.Stop();

    if (!warmup)
    {
        Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms",
            a.X, a.Y, sw.ElapsedMilliseconds);
    }
}

Ini akan berjalan dalam 900ms, sama seperti casing stopwatch luar. Namun, jika kami menghapus if (!warmup)kondisi tersebut, ini akan berjalan dalam 3000ms. Yang lebih aneh lagi, kode berikut juga akan berjalan dalam 900ms:

public static void Test1()
{
    Point a = new Point(1, 1), b = new Point(1, 1);

    Stopwatch sw = Stopwatch.StartNew();
    for (int i = 0; i < ITERATIONS; i++)
        a = AddByVal(a, b);
    sw.Stop();

    Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms",
        0, 0, sw.ElapsedMilliseconds);
}

Catatan Saya telah menghapus a.Xdan a.Yreferensi dari Consoleoutput.

Saya tidak tahu apa yang sedang terjadi, tetapi ini berbau cukup buggy bagi saya dan ini tidak terkait dengan memiliki luar Stopwatchatau tidak, masalahnya tampaknya sedikit lebih umum.

Diantara
sumber
Saat Anda menghapus panggilan ke a.Xdan a.Y, compiler mungkin bebas untuk mengoptimalkan hampir semua yang ada di dalam loop, karena hasil operasi tidak digunakan.
Groo
@Groo: ya, itu tampaknya masuk akal tetapi tidak ketika Anda memperhitungkan perilaku aneh lainnya yang kami lihat. Menghapus a.Xdan a.Ytidak membuatnya berjalan lebih cepat daripada ketika Anda memasukkan if (!warmup)kondisi atau OP outerSw, yang berarti tidak mengoptimalkan apa pun, itu hanya menghilangkan bug apa pun yang membuat kode berjalan pada kecepatan suboptimal ( 3000ms bukan 900ms).
peralihan
2
Oh, ok, saya pikir peningkatan kecepatan yang terjadi ketika warmupitu benar, tetapi dalam kasus bahwa garis bahkan tidak dicetak, sehingga kasus di mana ia tidak bisa dicetak sebenarnya referensi a. Saya tetap ingin memastikan bahwa saya selalu mereferensikan hasil perhitungan di suatu tempat di dekat akhir metode, setiap kali saya melakukan benchmarking.
Groo