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!