Drogi skok z GCC 5.4.0

Miałem funkcję, która wyglądała tak (pokazując tylko ważną część):

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) && (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

Napisana w ten sposób, funkcja zajęła około 34 ms na moim komputerze. Po zmianie warunku na mnożenie bool (nadanie kodowi takiego wyglądu):

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) * (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

czas wykonania zmniejszył się do ~ 19 ms.

Zastosowanym kompilatorem był GCC 5.4.0 z -O3 i po sprawdzeniu wygenerowanego kodu asm za pomocą godbolt.org stwierdziłem, że pierwszy przykład generuje skok, a drugi nie. Zdecydowałem się wypróbować GCC 6.2.0, który również generuje instrukcję skoku w pierwszym przykładzie, ale wydaje się, że GCC 7 już jej nie generuje.

Znalezienie sposobu na przyspieszenie kodu było raczej makabryczne i zajęło trochę czasu. Dlaczego kompilator zachowuje się w ten sposób? Czy jest to zamierzone i czy jest to coś, na co programiści powinni zwracać uwagę? Czy jest więcej podobnych rzeczy?

EDYCJA: link do godbolt https://godbolt.org/g/5lKPF3

Operator logiczny AND ( &&) używa oceny zwarcia, co oznacza, że ​​drugi test jest wykonywany tylko wtedy, gdy pierwsze porównanie daje wynik prawda. Często jest to dokładnie taka semantyka, jakiej potrzebujesz. Weźmy na przykład pod uwagę następujący kod:

if ((p != nullptr) && (p->first > 0))

Musisz upewnić się, że wskaźnik nie jest zerowy, zanim go wyłuskujesz. Jeśli to nie było ocena zwarcia, miałbyś niezdefiniowane zachowanie, ponieważ wyłuskiwałbyś wskaźnik zerowy.

Możliwe jest również, że ocena zwarcia daje wzrost wydajności w przypadkach, gdy ocena warunków jest kosztownym procesem. Na przykład:

if ((DoLengthyCheck1(p) && (DoLengthyCheck2(p))

Jeśli DoLengthyCheck1zawiedzie, nie ma sensu dzwonićDoLengthyCheck2 .

Jednak w wynikowym pliku binarnym operacja zwarcia często powoduje powstanie dwóch gałęzi, ponieważ jest to najłatwiejszy sposób dla kompilatora na zachowanie tej semantyki. (Dlatego z drugiej strony, ocena zwarć może czasami hamować potencjał optymalizacji). Możesz to zobaczyć, patrząc na odpowiednią część kodu wynikowego wygenerowanego dla twojego ifoświadczenia przez GCC 5.4:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L5

    cmp     ax, 478           ; (l[i + shift] < 479)
    ja      .L5

    add     r8d, 1            ; nontopOverlap++

Widzisz tutaj dwa porównania ( cmpinstrukcje), po których następuje oddzielny warunkowy skok / gałąź (ja lub skok, jeśli powyżej).

Ogólna praktyczna zasada mówi, że gałęzie są powolne i dlatego należy ich unikać w ciasnych pętlach. Dotyczyło to praktycznie wszystkich procesorów x86, od skromnego 8088 (którego powolne czasy pobierania i bardzo mała kolejka pobierania wstępnego [porównywalne z pamięcią podręczną instrukcji], w połączeniu z całkowitym brakiem przewidywania gałęzi, oznaczały, że pobrane gałęzie wymagały zrzucenia pamięci podręcznej ) do nowoczesnych wdrożeń (których długie potoki powodują, że źle przewidywane gałęzie są podobnie drogie). Zwróć uwagę na małe zastrzeżenie, które tam wśliznąłem. Nowoczesne procesory od czasu Pentium Pro mają zaawansowane silniki przewidywania gałęzi, które zostały zaprojektowane tak, aby zminimalizować koszt oddziałów. Jeśli kierunek gałęzi można właściwie przewidzieć, koszt jest minimalny. W większości przypadków działa to dobrze, ale jeśli dostaniesz się do patologicznych przypadków, w których predyktor gałęzi nie jest po twojej stronie,Twój kod może działać bardzo wolno . Prawdopodobnie jest to miejsce, w którym tutaj jesteś, ponieważ mówisz, że twoja tablica jest nieposortowana.

Mówisz, że testy porównawcze potwierdziły, że zastąpienie &&a *sprawia, że ​​kod jest zauważalnie szybszy. Przyczyna tego jest oczywista, gdy porównamy odpowiednią część kodu wynikowego:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    xor     r15d, r15d        ; (curr[i] < 479)
    cmp     r13w, 478
    setbe   r15b

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     ax, 478
    setbe   r14b

    imul    r14d, r15d        ; meld results of the two comparisons

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

Trochę sprzeczne z intuicją jest to, że mogłoby to być szybsze, ponieważ jest tutaj więcej instrukcji, ale tak czasami działa optymalizacja. Widzisz, jak cmpwykonywane są tutaj te same porównania ( ), ale teraz każde jest poprzedzone przez, xora po nim następuje setbe. XOR to po prostu standardowa sztuczka do czyszczenia rejestru. setbeJest instrukcją x86 że ustawia bit w oparciu o wartości flagi, i jest często używany do implementacji kodu branchless. Tutaj setbejest odwrotnością ja. Ustawia swój rejestr docelowy na 1, jeśli porównanie było poniżej lub równe (ponieważ rejestr został wstępnie wyzerowany, w przeciwnym razie będzie wynosił 0), a jarozgałęziony, jeśli porównanie było powyżej. Po uzyskaniu tych dwóch wartości w r15bir14brejestry są mnożone razem za pomocą imul. Mnożenie było tradycyjnie stosunkowo powolną operacją, ale na nowoczesnych procesorach jest cholernie szybkie, a będzie to szczególnie szybkie, ponieważ mnoży tylko dwa bajty.

Równie łatwo można by zastąpić mnożenie operatorem bitowym AND ( &), który nie wykonuje oceny zwarcia. To sprawia, że ​​kod jest znacznie bardziej przejrzysty i jest wzorcem, który kompilatory ogólnie rozpoznają. Ale kiedy robisz to ze swoim kodem i kompilujesz go z GCC 5.4, nadal emituje pierwszą gałąź:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L4

    cmp     ax, 478           ; (l[i + shift] < 479)
    setbe   r14b

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

Nie ma żadnego technicznego powodu, dla którego musiałby emitować kod w ten sposób, ale z jakiegoś powodu jego wewnętrzna heurystyka mówi mu, że jest to szybsze. To będzie prawdopodobnie szybciej jeśli predyktorem oddział był po twojej stronie, ale to będzie prawdopodobnie wolniejszy jeśli przewidywania rozgałęzień nie częściej niż to się uda.

Nowsze generacje kompilatora (i innych kompilatorów, takich jak Clang) znają tę regułę i czasami używają jej do generowania tego samego kodu, którego szukałbyś przez ręczną optymalizację. Regularnie widzę, jak Clang tłumaczy &&wyrażenia na ten sam kod, który zostałby wyemitowany, gdybym użył &. Poniżej przedstawiono odpowiednie dane wyjściowe z GCC 6.2 z Twoim kodem przy użyciu zwykłego &&operatora:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L7

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r14b

    add     esi, r14d         ; nontopOverlap++

Zauważ, jak mądry to jest! Używa warunków ze znakiem ( jgi setle) w przeciwieństwie do warunków bez znaku ( jai setbe), ale nie jest to ważne. Możesz zobaczyć, że nadal wykonuje porównanie i rozgałęzienie dla pierwszego warunku, podobnie jak starsza wersja, i używa tej samej setCCinstrukcji do wygenerowania bezgałęziowego kodu dla drugiego warunku, ale stał się znacznie bardziej wydajny w sposobie wykonywania inkrementacji . Zamiast robić drugie, redundantne porównanie w celu ustawienia flag sbboperacji, używa wiedzy, która r14dbędzie wynosić 1 lub 0, aby po prostu bezwarunkowo dodać tę wartość nontopOverlap. Jeśli r14dwynosi 0, to dodawanie nie działa; w przeciwnym razie dodaje 1, dokładnie tak, jak powinien.

GCC 6.2 w rzeczywistości generuje bardziej wydajny kod, gdy używasz &&operatora zwarcia niż &operator bitowy :

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L6

    cmp     eax, 478          ; (l[i + shift] < 479)
    setle   r14b

    cmp     r14b, 1           ; nontopOverlap++
    sbb     esi, -1

Gałąź i zestaw warunkowy nadal istnieją, ale teraz wraca do mniej sprytnego sposobu zwiększania nontopOverlap. To jest ważna lekcja, dlaczego powinieneś być ostrożny, próbując przechytrzyć swój kompilator!

Ale jeśli możesz udowodnić za pomocą testów porównawczych, że kod rozgałęziający jest faktycznie wolniejszy, może się opłacić wypróbowanie sprytnego kompilatora. Wystarczy to zrobić, uważnie sprawdzając dezasemblację - i być przygotowanym na ponowną ocenę swoich decyzji podczas aktualizacji do nowszej wersji kompilatora. Na przykład kod, który posiadasz, można przepisać jako:

nontopOverlap += ((curr[i] < 479) & (l[i + shift] < 479));

Nie ma iftutaj żadnego stwierdzenia, a ogromna większość kompilatorów nigdy nie pomyśli o wyemitowaniu w tym celu kodu rozgałęzienia. GCC nie jest wyjątkiem; wszystkie wersje generują coś podobnego do następującego:

    movzx   r14d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r14d, 478         ; (curr[i] < 479)
    setle   r15b

    xor     r13d, r13d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r13b

    and     r13d, r15d        ; meld results of the two comparisons
    add     esi, r13d         ; nontopOverlap++

Jeśli śledziłeś poprzednie przykłady, powinno to wyglądać znajomo. Oba porównania są wykonywane w sposób bezgałęziowy, wyniki pośrednie są andłączone, a następnie ten wynik (który będzie równy 0 lub 1) jest addedytowany nontopOverlap. Jeśli potrzebujesz kodu bez gałęzi, to praktycznie zapewni, że go otrzymasz.

GCC 7 stało się jeszcze mądrzejsze. Obecnie generuje praktycznie identyczny kod (z wyjątkiem niewielkich zmian w instrukcjach) dla powyższej sztuczki, jak kod oryginalny. A więc odpowiedź na twoje pytanie: „Dlaczego kompilator zachowuje się w ten sposób?” , prawdopodobnie dlatego, że nie są doskonałe! Próbują użyć heurystyki, aby wygenerować jak najbardziej optymalny kod, ale nie zawsze podejmują najlepsze decyzje. Ale przynajmniej z czasem mogą stać się mądrzejsi!

Jednym ze sposobów spojrzenia na tę sytuację jest to, że kod rozgałęziający ma lepszą wydajność w najlepszym przypadku . Jeśli przewidywanie rozgałęzień powiedzie się, pomijanie niepotrzebnych operacji spowoduje nieco szybszy czas działania. Jednak kod bezgałęziowy ma lepszą wydajność w najgorszym przypadku . Jeśli przewidywanie rozgałęzienia się nie powiedzie, wykonanie kilku dodatkowych instrukcji niezbędnych do uniknięcia rozgałęzienia będzie zdecydowanie szybsze niż w przypadku źle przewidzianej gałęzi. Nawet najmądrzejszy i najbardziej sprytny kompilator będzie miał trudności z dokonaniem takiego wyboru.

A jeśli chodzi o pytanie, czy jest to coś, na co programiści muszą uważać, odpowiedź prawie na pewno brzmi nie, z wyjątkiem pewnych gorących pętli, które próbujesz przyspieszyć za pomocą mikro-optymalizacji. Następnie siadasz przy demontażu i znajdujesz sposoby, aby go poprawić. I, jak powiedziałem wcześniej, przygotuj się na powrót do tych decyzji po zaktualizowaniu kompilatora do nowszej wersji, ponieważ może on albo zrobić coś głupiego z twoim podstępnym kodem, albo może zmienić jego heurystykę optymalizacji na tyle, że możesz wrócić do korzystania z oryginalnego kodu. Skomentuj dokładnie!

Jedną ważną rzeczą, na którą należy zwrócić uwagę, jest to

(curr[i] < 479) && (l[i + shift] < 479)

i

(curr[i] < 479) * (l[i + shift] < 479)

nie są semantycznie równoważne! W szczególności, jeśli kiedykolwiek wystąpi sytuacja, w której:

• 0 <= ii i < curr.size()oba są prawdziwe
• curr[i] < 479 to fałsz
• i + shift < 0lub i + shift >= l.size()jest prawdą

to wyrażenie (curr[i] < 479) && (l[i + shift] < 479)ma gwarancję, że będzie dobrze zdefiniowaną wartością logiczną. Na przykład nie powoduje błędu segmentacji.

Jednak w tych okolicznościach wyrażenie (curr[i] < 479) * (l[i + shift] < 479)oznacza niezdefiniowane zachowanie ; to jest dozwolone, aby spowodować błąd segmentacji.

Oznacza to, że na przykład dla oryginalnego fragmentu kodu kompilator nie może po prostu napisać pętli, która wykonuje oba porównania i wykonuje andoperację, chyba że kompilator może również udowodnić, że l[i + shift]nigdy nie spowoduje to segfaulta w sytuacji, w której nie jest wymagane.

Krótko mówiąc, oryginalny fragment kodu oferuje mniej możliwości optymalizacji niż ten drugi. (oczywiście, czy kompilator rozpoznaje możliwość, to zupełnie inna kwestia)

Zamiast tego możesz naprawić oryginalną wersję

bool t1 = (curr[i] < 479);
bool t2 = (l[i + shift] < 479);
if (t1 && t2) {
    // ...

&&Operator realizuje oceny zwarcie. Oznacza to, że drugi operand jest oceniany tylko wtedy, gdy pierwszy z nich ma wartość true. To z pewnością skutkuje skokiem w tym przypadku.

Możesz stworzyć mały przykład, aby to pokazać:

#include <iostream>

bool f(int);
bool g(int);

void test(int x, int y)
{
  if ( f(x) && g(x)  )
  {
    std::cout << "ok";
  }
}

Wyjście asemblera można znaleźć tutaj .

Możesz zobaczyć wygenerowany kod najpierw wywołania f(x), a następnie sprawdza dane wyjściowe i przechodzi do oceny, g(x)kiedy to nastąpiło true. W przeciwnym razie opuszcza funkcję.

Użycie mnożenia "boolowskiego" zamiast tego wymusza ocenę obu operandów za każdym razem, a zatem nie wymaga skoku.

W zależności od danych, skok może spowodować spowolnienie, ponieważ zakłóca potok procesora i inne rzeczy, takie jak wykonanie spekulacyjne. Zwykle przewidywanie gałęzi pomaga, ale jeśli dane są losowe, niewiele można przewidzieć.

Może to być spowodowane tym, że podczas korzystania z operatora logicznego &&kompilator musi sprawdzić dwa warunki, aby instrukcja if zakończyła się powodzeniem. Jednak w drugim przypadku, ponieważ niejawnie konwertujesz wartość int na bool, kompilator przyjmuje pewne założenia na podstawie przekazywanych typów i wartości, wraz z (prawdopodobnie) jednym warunkiem skoku. Możliwe jest również, że kompilator całkowicie optymalizuje jmps z przesunięciami bitów.