Spróbuj złapać przyspieszając mój kod?

1503

Napisałem kod do testowania wpływu try-catch, ale widzę zaskakujące wyniki.

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

Na moim komputerze powoduje to konsekwentne drukowanie wartości około 0,96 ..

Kiedy owijam pętlę for wewnątrz Fibo () blokiem try-catch, takim jak to:

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

Teraz konsekwentnie drukuje 0,69 ... - faktycznie działa szybciej! Ale dlaczego?

Uwaga: skompilowałem to przy użyciu konfiguracji wydania i bezpośrednio uruchomiłem plik EXE (poza Visual Studio).

EDYCJA: Doskonała analiza Jona Skeeta pokazuje, że try-catch w jakiś sposób powoduje, że CLR x86 korzysta z rejestrów procesora w bardziej korzystny sposób w tym konkretnym przypadku (i myślę, że jeszcze nie rozumiemy, dlaczego). Potwierdziłem odkrycie Jona, że ​​x64 CLR nie ma tej różnicy i że jest szybszy niż x86 CLR. Testowałem również przy użyciu inttypów wewnątrz metody Fibo zamiast longtypów, a następnie CLR x86 był równie szybki jak CLR x64.


AKTUALIZACJA: Wygląda na to, że ten problem został rozwiązany przez Roslyn. Ta sama maszyna, ta sama wersja CLR - problem pozostaje jak wyżej po skompilowaniu z VS 2013, ale problem zniknie po skompilowaniu z VS 2015.

Eren Ersönmez
źródło
111
@ Lloyd stara się uzyskać odpowiedź na swoje pytanie „tak naprawdę działa szybciej! Ale dlaczego?”
Andreas Niedermair,
137
Tak więc teraz „wyjątki w połykaniu” przeszły od złej praktyki do dobrej optymalizacji wydajności: P
Luciano
2
Czy dzieje się to w niesprawdzonym lub sprawdzonym kontekście arytmetycznym?
Random832
7
@ taras.roshko: Chociaż nie chcę wyrządzić Ericowi krzywdy, nie jest to tak naprawdę pytanie C # - jest to pytanie kompilatora JIT. Ostateczną trudnością jest ustalenie, dlaczego JIT x86 nie używa tylu rejestrów bez try / catch, jak w przypadku bloku try / catch.
Jon Skeet,
63
Fajnie, więc jeśli zagnieżdżymy te próby, możemy pójść jeszcze szybciej, prawda?
Chuck Pinkert,

Odpowiedzi:

1053

Jeden z inżynierów Roslyn, który specjalizuje się w zrozumieniu optymalizacji wykorzystania stosu, przyjrzał się temu i doniósł mi, że wydaje się, że istnieje problem w interakcji między sposobem, w jaki kompilator C # generuje lokalne magazyny zmiennych, a sposobem, w jaki kompilator JIT rejestruje planowanie w odpowiednim kodzie x86. Rezultatem jest nieoptymalne generowanie kodu dla obciążeń i zapasów mieszkańców.

Z jakiegoś powodu dla nas wszystkich niejasnego unika się problematycznej ścieżki generowania kodu, gdy JITter wie, że blok znajduje się w regionie chronionym przed próbą.

To jest dość dziwne. Później skontaktujemy się z zespołem JITter i sprawdzimy, czy możemy wprowadzić błąd, aby mogli go naprawić.

Pracujemy również nad ulepszeniem Roslyn algorytmów kompilatorów C # i VB w celu określenia, kiedy można określić, że locals mogą stać się „efemeryczne” - to znaczy wystarczy je wcisnąć i wyskoczyć na stosie, zamiast przypisywać określoną lokalizację na stosie czas trwania aktywacji. Wierzymy, że JITter będzie w stanie wykonać lepszą pracę przy przydzielaniu rejestrów, a co więcej, jeśli damy lepsze wskazówki, kiedy miejscowi mogą zostać „martwi” wcześniej.

Dziękujemy za zwrócenie nam na to uwagi i przepraszamy za dziwne zachowanie.

Eric Lippert
źródło
8
Zawsze zastanawiałem się, dlaczego kompilator C # generuje tak wielu obcych użytkowników. Na przykład nowe wyrażenia inicjujące tablicę zawsze generują lokalny, ale nigdy nie jest konieczny do generowania lokalnego. Jeśli pozwoli to JITterowi na generowanie znacznie wydajniejszego kodu, być może kompilator C # powinien być bardziej ostrożny w generowaniu niepotrzebnych miejscowych ...
Timwi
33
@Timwi: Oczywiście. W niezoptymalizowanym kodzie kompilator generuje niepotrzebne pliki lokalne z wielkim porzuceniem, ponieważ ułatwiają debugowanie. W zoptymalizowanym kodzie niepotrzebne pliki tymczasowe należy usunąć, jeśli to możliwe. Niestety przez lata mieliśmy wiele błędów, w których przez przypadek dokonaliśmy dezoptymalizacji tymczasowego optymalizatora eliminacji. Wspomniany inżynier całkowicie przerabia cały kod od samego początku dla Roslyn, w związku z czym powinniśmy mieć znacznie ulepszone zoptymalizowane zachowanie w generatorze kodu Roslyn.
Eric Lippert,
24
Czy kiedykolwiek był jakiś ruch w tej sprawie?
Robert Harvey
10
Wygląda na to, że Roslyn to naprawiła.
Eren Ersönmez
56
Nie wykorzystałeś okazji, by nazwać to „błędem JITtera”.
mbomb007,
734

Sposób, w jaki mierzysz czas, wydaje mi się dość paskudny. O wiele rozsądniej byłoby po prostu zmierzyć całą pętlę:

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

W ten sposób nie jesteś na łasce drobnych czasów, arytmetyki zmiennoprzecinkowej i skumulowanego błędu.

Po dokonaniu tej zmiany sprawdź, czy wersja „non-catch” jest wolniejsza niż wersja „catch”.

EDYCJA: OK, sam tego próbowałem - i widzę ten sam rezultat. Bardzo dziwne. Zastanawiałem się, czy try / catch wyłącza jakieś złe wstawianie, ale użycie [MethodImpl(MethodImplOptions.NoInlining)]zamiast tego nie pomogło ...

Zasadniczo musisz spojrzeć na zoptymalizowany kod JITted pod cordbg, podejrzewam ...

EDYCJA: Kilka dodatkowych informacji:

  • Umieszczenie try / catch na samej n++;linii wciąż poprawia wydajność, ale nie tak bardzo, jak na całym bloku
  • Jeśli złapiesz określony wyjątek ( ArgumentExceptionw moich testach), to wciąż jest szybki
  • Jeśli wydrukujesz wyjątek w bloku catch, nadal będzie on szybki
  • Jeśli ponownie wrzucisz wyjątek w bloku catch, będzie on znowu wolny
  • Jeśli użyjesz bloku w końcu zamiast bloku przechwytywania, znów będzie on wolny
  • Jeśli użyjesz bloku wreszcie, a także bloku catch, jest to szybkie

Dziwne...

EDYCJA: OK, mamy demontaż ...

Korzysta z kompilatora C # 2 i CLR .NET 2 (32-bit), dezasembluje się z mdbg (ponieważ nie mam cordbg na moim komputerze). Nadal widzę te same efekty wydajnościowe, nawet pod debuggerem. Wersja szybka wykorzystuje tryblok wokół wszystkiego między deklaracjami zmiennych a instrukcją return, z tylko catch{}funkcją obsługi. Oczywiście wolna wersja jest taka sama, chyba że bez try / catch. Kod wywołujący (tj. Główny) jest taki sam w obu przypadkach i ma tę samą reprezentację zestawu (więc nie jest to kwestia kluczowa).

Zdemontowany kod dla szybkiej wersji:

 [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

Zdemontowany kod dla wolnej wersji:

 [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

W każdym przypadku *pokazuje, gdzie debuger wszedł w prosty „krok”.

EDYCJA: OK, przejrzałem kod i myślę, że widzę, jak działa każda wersja ... i uważam, że wolniejsza wersja jest wolniejsza, ponieważ wykorzystuje mniej rejestrów i więcej miejsca na stosie. W przypadku małych wartości njest to prawdopodobnie szybsze - ale gdy pętla zajmuje większość czasu, jest wolniejsza.

Być może blok try / catch wymusza zapisywanie i przywracanie większej liczby rejestrów, więc JIT wykorzystuje je również w pętli ... co poprawia ogólną wydajność. Nie jest jasne, czy uzasadnione jest, aby JIT nie używał tylu rejestrów w „normalnym” kodzie.

EDYCJA: Właśnie wypróbowałem to na moim komputerze x64. CLR x64 jest znacznie szybszy (około 3-4 razy szybszy) niż CLR x86 w tym kodzie, a pod x64 blok try / catch nie robi zauważalnej różnicy.

Jon Skeet
źródło
4
@GordonSimpson, ale w przypadku przechwycenia tylko określonego wyjątku, wszystkie inne wyjątki nie zostałyby wychwycone, więc wszelkie koszty ogólne zaangażowane w twoją hipotezę o braku próby byłyby nadal potrzebne.
Jon Hanna,
45
Wygląda to na różnicę w przydziale rejestrów. Szybkiej wersji udaje się użyć esi,edidla jednego z długich zamiast stosu. Używa ebxjako licznika, w którym używana jest wersja wolna esi.
Jeffrey Sax
13
@JeffreySax: Nie chodzi tylko o to, które rejestry są używane, ale o ile. Wersja wolna wykorzystuje więcej miejsca na stosie, dotykając mniejszej liczby rejestrów. Nie mam pojęcia, dlaczego ...
Jon Skeet
2
Jak traktowane są ramki wyjątków CLR pod względem rejestrów i stosu? Czy konfiguracja może uwolnić rejestr do użytku?
Random832
4
IIRC x64 ma więcej dostępnych rejestrów niż x86. Przyspieszenie, które widziałeś, byłoby spójne z try / catch wymuszającym dodatkowe użycie rejestru pod x86.
Dan Is Fiddling By Firelight
116

Z dezasemblacji Jona wynika, że ​​różnica między dwiema wersjami polega na tym, że szybka wersja używa pary rejestrów ( esi,edi) do przechowywania jednej z lokalnych zmiennych, gdzie nie działa wolna wersja.

Kompilator JIT przyjmuje różne założenia dotyczące wykorzystania rejestru do kodu zawierającego blok try-catch w porównaniu do kodu, który tego nie robi. To powoduje, że dokonuje różnych wyborów przydziału rejestrów. W tym przypadku faworyzuje to kod z blokiem try-catch. Inny kod może prowadzić do odwrotnego efektu, więc nie liczyłbym tego jako techniki przyspieszania ogólnego zastosowania.

Ostatecznie bardzo trudno jest stwierdzić, który kod skończy się najszybciej. Coś takiego jak przydział rejestrów i czynniki, które na to wpływają, to tak szczegółowe informacje o implementacji niskiego poziomu, że nie rozumiem, w jaki sposób jakakolwiek konkretna technika mogłaby niezawodnie wytwarzać szybszy kod.

Rozważmy na przykład następujące dwie metody. Zostały zaadaptowane z prawdziwego przykładu:

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

Jedna jest ogólną wersją drugiej. Zastąpienie typu ogólnego typem StructArrayspowoduje, że metody będą identyczne. Ponieważ StructArrayjest to typ wartości, otrzymuje własną skompilowaną wersję ogólnej metody. Rzeczywisty czas działania jest jednak znacznie dłuższy niż w przypadku metody specjalistycznej, ale tylko dla x86. W przypadku x64 czasy są prawie identyczne. W innych przypadkach zaobserwowałem również różnice dla x64.

Jeffrey Sax
źródło
6
Biorąc to pod uwagę, czy możesz wymusić różne opcje przydzielania rejestrów bez użycia Try / Catch? Albo jako test dla tej hipotezy, czy jako ogólna próba dostrojenia prędkości?
WernerCD
1
Istnieje wiele powodów, dla których ten konkretny przypadek może być inny. Może to próba złapania. Być może to fakt, że zmienne są ponownie używane w wewnętrznym zakresie. Niezależnie od konkretnego powodu, jest to szczegół implementacji, na który nie można liczyć, że zostanie zachowany, nawet jeśli ten sam kod zostanie wywołany w innym programie.
Jeffrey Sax
4
@WernerCD Powiedziałbym, że C i C ++ mają słowo kluczowe sugerujące, które (A) jest ignorowane przez wiele współczesnych kompilatorów, a (B) postanowiono nie umieszczać w C #, sugeruje, że nie jest to coś, co „ Zobaczę w bardziej bezpośredni sposób.
Jon Hanna,
2
@WernerCD - Tylko jeśli sam napiszesz zespół
OrangeDog
72

To wygląda na przypadek zepsucia się. Na rdzeniu x86 jitter ma dostępny rejestr ebx, edx, esi i edi do ogólnego przechowywania zmiennych lokalnych. Rejestr ECX będzie dostępny w metodzie statycznej, nie trzeba przechowywać ten . Rejestr eax jest często potrzebny do obliczeń. Ale są to rejestry 32-bitowe, dla zmiennych typu long musi używać pary rejestrów. Które są edx: eax do obliczeń i edi: ebx do przechowywania.

To, co wyróżnia się w demontażu dla wersji wolnej, nie są używane ani edi, ani ebx.

Kiedy jitter nie może znaleźć wystarczającej liczby rejestrów do przechowywania zmiennych lokalnych, musi wygenerować kod, aby załadować i zapisać je z ramki stosu. Spowalnia to kod, zapobiega optymalizacji procesora o nazwie „zmiana nazwy rejestru”, wewnętrznej sztuczki optymalizacji rdzenia procesora, która wykorzystuje wiele kopii rejestru i umożliwia wykonanie super-skalarne. Dzięki temu kilka instrukcji może działać jednocześnie, nawet jeśli używają tego samego rejestru. Brak wystarczającej liczby rejestrów jest powszechnym problemem na rdzeniach x86, rozwiązanym w x64, który ma 8 dodatkowych rejestrów (od r9 do r15).

Jitter dołoży wszelkich starań, aby zastosować kolejną optymalizację generowania kodu, spróbuje wprowadzić metodę Fibo (). Innymi słowy, nie należy wywoływać metody, ale generować kod metody wbudowanej w metodzie Main (). Całkiem ważna optymalizacja, która, na przykład, czyni właściwości klasy C # za darmo, dając im doskonałe pole. Pozwala to uniknąć narzutu wywołania metody i ustawienia ramki stosu, co pozwala zaoszczędzić kilka nanosekund.

Istnieje kilka reguł, które określają dokładnie, kiedy można wprowadzić metodę. Nie są dokładnie udokumentowane, ale zostały wspomniane w postach na blogu. Jedną z zasad jest to, że nie stanie się to, gdy treść metody jest zbyt duża. To niweczy zysk z wbudowania, generuje zbyt dużo kodu, który nie pasuje tak dobrze do pamięci podręcznej instrukcji L1. Inną trudną zasadą, która ma tutaj zastosowanie, jest to, że metoda nie będzie wstawiana, gdy będzie zawierać instrukcję try / catch. Tłem tego jest szczegół implementacji wyjątków, które przywracają do wbudowanej w Windows obsługi SEH (obsługa wyjątków struktury), która jest oparta na ramce stosu.

Jedno zachowanie algorytmu alokacji rejestru w fluktuacji można wywnioskować z gry z tym kodem. Wygląda na to, że zdaje sobie sprawę, kiedy fluktuacja próbuje wprowadzić metodę. Wydaje się, że jedną zasadą jest stosowanie tylko pary rejestru edx: eax dla kodu wstawionego, który ma lokalne zmienne typu long. Ale nie edi: ebx. Bez wątpienia, ponieważ byłoby to zbyt szkodliwe dla generowania kodu dla metody wywołującej, zarówno edi, jak i ebx są ważnymi rejestrami pamięci.

Otrzymujesz szybką wersję, ponieważ jitter z góry wie, że treść metody zawiera instrukcje try / catch. Wie, że nigdy nie da się go wstawić, dlatego z łatwością używa edi: ebx do przechowywania długiej zmiennej. Masz wolną wersję, ponieważ jitter nie wiedział z góry, że inlining nie zadziała. Dowiedział się to dopiero po wygenerowaniu kodu dla treści metody.

Wada polega na tym, że nie cofnął się i nie wygenerował ponownie kodu dla metody. Co jest zrozumiałe, biorąc pod uwagę ograniczenia czasowe, w jakich musi działać.

To spowolnienie nie występuje na x64, ponieważ dla jednego ma jeszcze 8 rejestrów. Po drugie, ponieważ może przechowywać długi w jednym rejestrze (np. Rax). Zwolnienie nie występuje, gdy używasz int zamiast długiego, ponieważ fluktuacja ma znacznie większą elastyczność w pobieraniu rejestrów.

Hans Passant
źródło
21

Umieściłbym to w komentarzu, ponieważ tak naprawdę nie jestem pewien, czy tak się stanie, ale o ile pamiętam, nie jest to instrukcja try / try, która obejmuje modyfikację mechanizmu usuwania śmieci kompilator działa w tym sensie, że usuwa rekursywnie przydziały pamięci obiektów w sposób rekurencyjny ze stosu. W tym przypadku może nie istnieć obiekt do wyczyszczenia lub pętla for może stanowić zamknięcie, które mechanizm wyrzucania elementów bezużytecznych uznaje za wystarczające do wymuszenia innej metody zbierania. Prawdopodobnie nie, ale pomyślałem, że warto o tym wspomnieć, ponieważ nie widziałem o tym nigdzie indziej.

frezować goryla
źródło