Dziwny wzrost wydajności w prostym benchmarku

97

Wczoraj znalazłem artykuł Christopha Nahra zatytułowany ".NET Struct Performance", w którym porównano kilka języków (C ++, C #, Java, JavaScript) dla metody, która dodaje dwie struktury punktowe ( doublekrotki).

Jak się okazało, wykonanie wersji C ++ zajmuje około 1000 ms (iteracje 1e9), podczas gdy C # nie może zejść poniżej ~ 3000 ms na tej samej maszynie (i działa jeszcze gorzej na x64).

Aby samemu to przetestować, wziąłem kod C # (i nieco uprościłem, aby wywołać tylko metodę, w której parametry są przekazywane przez wartość) i uruchomiłem go na maszynie i7-3610QM (3,1 GHz doładowanie dla pojedynczego rdzenia), 8 GB pamięci RAM, Win8. 1, przy użyciu .NET 4.5.2, wersja RELEASE 32-bitowa (x86 WoW64, ponieważ mój system operacyjny jest 64-bitowy). To jest wersja uproszczona:

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

Z Pointdefinicją po prostu:

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

Uruchomienie go daje wyniki podobne do tych w artykule:

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

Pierwsza dziwna obserwacja

Ponieważ metoda powinna być wbudowana, zastanawiałem się, jak działałby kod, gdybym całkowicie usunął struktury i po prostu wstawił całość razem:

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

I uzyskał praktycznie ten sam wynik (właściwie 1% wolniej po kilku próbach), co oznacza, że ​​JIT-ter wydaje się wykonywać dobrą robotę optymalizując wszystkie wywołania funkcji:

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

Oznacza to również, że benchmark nie wydaje się mierzyć żadnej structwydajności i wydaje się mierzyć tylko podstawową doublearytmetykę (po optymalizacji wszystkiego innego).

Dziwne rzeczy

Teraz czas na dziwną część. Jeśli po prostu dodam kolejny stoper poza pętlą (tak, zawęziłem to do tego szalonego kroku po kilku próbach), kod działa trzy razy szybciej :

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

To niedorzeczne! I to nie Stopwatchjest tak, że daje mi złe wyniki, ponieważ wyraźnie widzę, że kończy się po jednej sekundzie.

Czy ktoś może mi powiedzieć, co się tutaj dzieje?

(Aktualizacja)

Oto dwie metody w tym samym programie, które pokazują, że przyczyną nie jest 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();
    }
}

Wynik:

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

Oto pastebin. Musisz go uruchomić w wersji 32-bitowej na platformie .NET 4.x (w kodzie znajduje się kilka elementów sprawdzających, aby to zapewnić).

(Aktualizacja 4)

Po komentarzach @ usr na temat odpowiedzi @Hansa sprawdziłem zoptymalizowany demontaż dla obu metod i są one raczej różne:

Test1 po lewej, Test2 po prawej

To wydaje się pokazywać, że różnica może wynikać z dziwnego działania kompilatora w pierwszym przypadku, a nie z wyrównania podwójnego pola?

Ponadto, jeśli dodam dwie zmienne (całkowite przesunięcie 8 bajtów), nadal otrzymuję to samo przyspieszenie - i nie wydaje się, że jest to związane z wyrównaniem pola, o którym wspomniał 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);
}
Groo
źródło
1
Oprócz JIT zależy to również od optymalizacji kompilatora, najnowszy Ryujit wykonuje więcej optymalizacji, a nawet wprowadził ograniczoną obsługę instrukcji SIMD.
Felix K.
3
Jon Skeet znalazł problem z wydajnością w przypadku pól tylko do odczytu w strukturach: Mikrooptymalizacja: zaskakująca nieefektywność pól tylko do odczytu . Spróbuj ustawić pola prywatne jako nie tylko do odczytu.
dbc
2
@dbc: Zrobiłem test z tylko doublezmiennymi lokalnymi , bez structs, więc wykluczyłem nieefektywność układu struktury / wywołania metody.
Groo
3
Wydaje się, że dzieje się to tylko na 32-bitowym, z RyuJIT, oba razy otrzymuję 1600 ms.
leppie
2
Przyjrzałem się demontażowi obu metod. Nie ma nic ciekawego do zobaczenia. Test1 generuje nieefektywny kod bez wyraźnego powodu. Błąd JIT lub projekt. W Test1 JIT ładuje i przechowuje dublety dla każdej iteracji na stosie. Może to mieć na celu zapewnienie dokładnej precyzji, ponieważ jednostka pływająca x86 wykorzystuje wewnętrzną precyzję 80-bitową. Zauważyłem, że każde wywołanie funkcji nieliniowej na górze funkcji sprawia, że ​​działa ona szybko.
usr

Odpowiedzi:

10

Aktualizacja 4 wyjaśnia problem: w pierwszym przypadku JIT przechowuje obliczone wartości ( a, b) na stosie; w drugim przypadku JIT przechowuje je w rejestrach.

W rzeczywistości Test1działa powoli, ponieważ Stopwatch. Napisałem następujący minimalny test porównawczy oparty na 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);
    }
}

Wyniki na moim komputerze:

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 |

Jak możemy zobaczyć:

  • WithoutStopwatchdziała szybko (bo a = a + bkorzysta z rejestrów)
  • WithStopwatchdziała powoli (ponieważ a = a + bużywa stosu)
  • WithTwoStopwatchesznów działa szybko (bo a = a + bużywa rejestrów)

Zachowanie JIT-x86 zależy od dużej ilości różnych warunków. Z jakiegoś powodu pierwszy stoper wymusza na JIT-x86 użycie stosu, a drugi pozwala na ponowne użycie rejestrów.

AndreyAkinshin
źródło
To naprawdę nie wyjaśnia przyczyny. Jeśli sprawdzisz moje testy, okaże się, że test, który ma dodatkowy, Stopwatchfaktycznie działa szybciej . Ale jeśli zmienisz kolejność, w jakiej są wywoływane w Mainmetodzie, druga metoda zostanie zoptymalizowana.
Groo
75

Istnieje bardzo prosty sposób, aby zawsze uzyskać „szybką” wersję programu. Projekt> Właściwości> karta Kompilacja, usuń zaznaczenie opcji „Preferuj 32-bitowe”, upewnij się, że wybrana platforma docelowa to AnyCPU.

Naprawdę nie preferujesz wersji 32-bitowej, niestety zawsze jest domyślnie włączona dla projektów C #. W przeszłości zestaw narzędzi programu Visual Studio działał znacznie lepiej z procesami 32-bitowymi, starym problemem, który rozwiązał Microsoft. Czas na usunięcie tej opcji, VS2015 w szczególności rozwiązał kilka ostatnich rzeczywistych przeszkód w 64-bitowym kodzie z zupełnie nowym jitterem x64 i uniwersalną obsługą Edytuj + Kontynuuj.

Dość gadania, odkryłeś znaczenie dopasowania zmiennych. Procesor bardzo o to dba. Jeśli zmienna jest źle wyrównana w pamięci, procesor musi wykonać dodatkową pracę, aby przetasować bajty, aby uzyskać je we właściwej kolejności. Istnieją dwa różne problemy związane z niewspółosiowością, z których jeden polega na tym, że bajty nadal znajdują się w pojedynczej linii pamięci podręcznej L1, co kosztuje dodatkowy cykl, aby przesunąć je do właściwej pozycji. I ten bardzo zły, ten, który znalazłeś, w którym część bajtów znajduje się w jednej linii pamięci podręcznej, a część w drugiej. Wymaga to dwóch oddzielnych dostępów do pamięci i sklejania ich ze sobą. Trzy razy wolniej.

doubleI longtypy są kłopoty decydentów w procesie 32-bitowym. Mają rozmiar 64-bitowy. I może w ten sposób zostać źle wyrównany o 4, CLR może zagwarantować tylko 32-bitowe wyrównanie. Nie stanowi to problemu w procesie 64-bitowym, wszystkie zmienne są wyrównane do 8. Również podstawowy powód, dla którego język C # nie może obiecać, że są atomowe . I dlaczego tablice double są przydzielane w stosie dużych obiektów, gdy mają więcej niż 1000 elementów. LOH zapewnia gwarancję wyrównania równą 8. I wyjaśnia, dlaczego dodanie zmiennej lokalnej rozwiązało problem. Odniesienie do obiektu ma 4 bajty, więc podwójna zmienna została przesunięta o 4, teraz wyrównując. Przez przypadek.

32-bitowy kompilator C lub C ++ wykonuje dodatkową pracę, aby upewnić się, że double nie może zostać źle wyrównany. Nie jest to do końca prosty problem do rozwiązania, stos może być źle wyrównany po wprowadzeniu funkcji, biorąc pod uwagę, że jedyną gwarancją jest to, że jest wyrównana do 4. Prolog takiej funkcji wymaga dodatkowej pracy, aby dostosować ją do 8. Ta sama sztuczka nie działa w zarządzanym programie, moduł odśmiecania pamięci bardzo dba o to, gdzie dokładnie znajduje się zmienna lokalna w pamięci. Jest to konieczne, aby mógł odkryć, że obiekt w stercie GC nadal zawiera odwołania. Nie może poprawnie poradzić sobie z przesunięciem takiej zmiennej o 4, ponieważ stos był nieprawidłowo wyrównany przy wprowadzaniu metody.

Jest to również podstawowy problem związany z drganiami .NET, które nie obsługują łatwo instrukcji SIMD. Mają znacznie silniejsze wymagania dotyczące wyrównania, których procesor również nie może rozwiązać samodzielnie. SSE2 wymaga wyrównania 16, AVX wymaga wyrównania 32. Nie można tego uzyskać w kodzie zarządzanym.

Na koniec należy zauważyć, że dzięki temu wydajność programu C # działającego w trybie 32-bitowym jest bardzo nieprzewidywalna. Kiedy uzyskujesz dostęp do double lub long, które jest przechowywane jako pole w obiekcie, wówczas perf może drastycznie się zmienić, gdy moduł odśmiecania pamięci kompaktuje stertę. Które przenosi obiekty w pamięci, takie pole może teraz nagle zostać źle wyrównane. Oczywiście bardzo przypadkowe, może być niezłe drapanie w głowę :)

Cóż, nie ma prostych poprawek, ale jeden, 64-bitowy kod to przyszłość. Usuń wymuszanie jitter, o ile Microsoft nie zmieni szablonu projektu. Może kolejna wersja, kiedy poczują się pewniej Ryujit.

Hans Passant
źródło
1
Nie jestem pewien, jak działa wyrównanie, gdy podwójne zmienne mogą być (i są w Test2) zarejestrowane. Test1 używa stosu, Test2 nie.
usr
2
To pytanie zmienia się zbyt szybko, abym mógł go śledzić. Musisz uważać na sam test wpływający na wynik testu. Musisz umieścić [MethodImpl (MethodImplOptions.NoInlining)] na metodach testowych, aby porównać jabłka z pomarańczami. Zobaczysz teraz, że optymalizator może zachować zmienne na stosie FPU w obu przypadkach.
Hans Passant
4
Omg, to prawda. Dlaczego dopasowanie metody ma jakikolwiek wpływ na generowane instrukcje ?! Nie powinno być żadnej różnicy w przypadku korpusu pętli. Wszystko powinno być w rejestrach. Prolog dostosowania powinien być nieistotny. Nadal wygląda na błąd JIT.
usr
3
Muszę znacznie zmienić odpowiedź, bummer. Dojdę do tego jutro.
Hans Passant
2
@HansPassant czy zamierzasz przekopać się przez źródła JIT? To byłoby fajne. W tym momencie wszystko, co wiem, to losowy błąd JIT.
usr
5

Zawęziło to trochę (wydaje się, że wpływa tylko na 32-bitowe środowisko wykonawcze CLR 4.0).

Zwróć uwagę, że umieszczenie znaku var f = Stopwatch.Frequency;robi różnicę.

Wolno (2700 ms):

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

Szybki (800 ms):

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
źródło
Modyfikacja kodu bez dotykania Stopwatchrównież drastycznie zmienia prędkość. Zmiana sygnatury metody na Test1(bool warmup)i dodanie warunku na Consolewyjściu: if (!warmup) { Console.WriteLine(...); }również ma ten sam efekt (natknąłem się na to podczas budowania moich testów w celu odtworzenia problemu).
Pomiędzy
@InBetween: Widziałem, coś jest podejrzane. Dzieje się również tylko na strukturach.
leppie
4

Wygląda na to, że w Jitter jest jakiś błąd, ponieważ zachowanie jest jeszcze dziwniejsze. Rozważ następujący kod:

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

Będzie to działać w 900ms, tak samo jak w przypadku zewnętrznego stopera. Jeśli jednak usuniemy if (!warmup)warunek, będzie działał w 3000ms. Jeszcze dziwniejsze jest to, że następujący kod również zostanie uruchomiony w 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);
}

Uwaga Usunąłem a.Xi a.Yodniesienia z danych Consolewyjściowych.

Nie mam pojęcia, co się dzieje, ale dla mnie to dość buggy i nie ma związku z posiadaniem zewnętrznego Stopwatchlub nie, problem wydaje się nieco bardziej uogólniony.

Pomiędzy
źródło
Po usunięciu wywołań a.Xi a.Y, kompilator prawdopodobnie będzie mógł zoptymalizować prawie wszystko wewnątrz pętli, ponieważ wyniki operacji są nieużywane.
Groo
@Groo: tak, wydaje się to rozsądne, ale nie, jeśli weźmie się pod uwagę inne dziwne zachowanie, które obserwujemy. Usuwanie a.Xi a.Ynie sprawia, że ​​działa szybciej niż wtedy, gdy dołączasz if (!warmup)warunek lub OP outerSw, co oznacza, że ​​nie optymalizuje niczego, po prostu eliminuje każdy błąd, który powoduje, że kod działa z nieoptymalną prędkością ( 3000ms zamiast 900ms).
Pomiędzy
2
Oh, ok, myślałem, że poprawa prędkości stało, gdy warmupbyło to prawdą, ale w tym przypadku linia nie jest jeszcze wydrukowane, więc w przypadku, gdy ma się wydrukowanym faktycznie odniesień a. Niemniej jednak lubię mieć pewność, że zawsze odwołuję się do wyników obliczeń gdzieś pod koniec metody, gdy wykonuję testy porównawcze.
Groo