Czy można powiedzieć predyktorowi gałęzi, jak prawdopodobne jest podążanie za gałęzią?

Tak, ale będzie to miało NIE efekt. Wyjątkami są starsze (przestarzałe) architektury przed Netburst, i nawet wtedy nie robi nic mierzalnego.

Istnieje kod opcode" gałąź podpowiedzi " Intel wprowadzony wraz z architekturą Netburst, oraz domyślna statyczna gałąź przewidywania zimnych skoków (przewidywana wstecz podjęta, przewidywana naprzód nie podjęta) na niektórych starszych architekturach. GCC implementuje to z __builtin_expect (x, prediction), gdzie przewidywanie jest zwykle 0 lub 1. Kod opcode emitowany przez kompilator jest ignorowany na wszystkich nowszych architekturach procesorów (>=Core 2). Mała narożna obudowa, w której to rzeczywiście coś robi, to przypadek zimnego skoku na starej architekturze Netburst. Intel zaleca teraz, aby nie używać statycznych podpowiedzi gałęzi, prawdopodobnie dlatego, że uważają zwiększenie rozmiaru kodu za bardziej szkodliwe niż możliwe krańcowe przyspieszenie.

Poza bezużyteczną podpowiedzią dla predyktora, __builtin_expect ma swoje zastosowanie, kompilator może zmienić kolejność kodu, aby poprawić pamięć podręczną użycie lub zapisanie pamięci.

Jest wiele powodów, dla których nie działa zgodnie z oczekiwaniami.

• procesor potrafi doskonale przewidzieć małe pętle (n
• procesor potrafi doskonale przewidywać małe powtarzające się wzorce (N~7).
• sam procesor potrafi oszacować prawdopodobieństwo powstania gałęzi w czasie pracy lepiej niż kompilator / programista w czasie kompilacji.
• przewidywalność (= prawdopodobieństwo, że gałąź zostanie prawidłowo przepowiedziana) gałęzi jest o wiele ważniejsze niż prawdopodobieństwo, że oddział zostanie zajęty. Niestety, jest to bardzo zależne od architektury, a przewidywanie przewidywalności gałęzi jest notorycznie trudne.

Czytaj więcej o wewnętrznych pracach oddziału w Agner Fogs podręczniki . Zobacz także listę dyskusyjną gcc .

Pentium 4 (aka Netburst microarchitecture) miało podpowiedzi branch-predictor jako prefiksy do instrukcji jcc, ale tylko P4 kiedykolwiek coś z nimi zrobił. Zobacz http://ref.x86asm.net/geek32.html . i sekcja 3.5 doskonałego przewodnika ASM opt Agner Fog , z http://www.agner.org/optimize / . ma też poradnik optymalizacji w C++.

Wcześniejsze i późniejsze procesory x86 po cichu ignorują te prefiksy. czy są jakieś wyniki testów wydajności dla użycia prawdopodobnych / nieprawdopodobnych podpowiedzi? wspomina, że PowerPC ma pewne instrukcje skoku, które mają podpowiedź przewidywania gałęzi jako część kodowania. To dość rzadka cecha architektoniczna. Statyczne przewidywanie gałęzi w czasie kompilacji jest bardzo trudne do zrobienia dokładnie, więc zwykle lepiej zostawić to sprzętowi, aby to rozgryźć.

Niewiele jest oficjalnie opublikowanych informacji o tym, jak zachowują się predyktory gałęzi i bufory gałęzi w najnowszych procesorach Intela i AMD. Na podręczniki optymalizacji (łatwe do znalezienia na stronach internetowych AMD i Intela) dają pewne porady, ale nie dokumentują konkretnych zachowań. Niektórzy uruchamiali testy, aby spróbować zrozumieć implementację, np. ile wpisów BTB ma Core2... W każdym razie pomysł sugerowania predyktora został (na razie) porzucony.

Udokumentowane jest na przykład to, że Core2 ma bufor historii gałęzi, który może uniknąć błędnego wskazania loop-exit, jeśli pętla zawsze uruchamia stałą, krótką liczbę iteracji, doskonałe .

Zobacz także dlaczego Intel zmienił mechanizm przewidywania gałęzi statycznych przez te lata? : Intel, ponieważ Sandybridge w ogóle nie używa predykcji statycznej, o ile możemy stwierdzić z eksperymentów wydajnościowych, które próbują Inżynieria wsteczna, co robią Procesory. (Wiele starszych procesorów ma predykcję statyczną jako rezerwę, gdy przewidywanie dynamiczne chybi. Normalną prognozą statyczną jest to, że gałęzie do przodu nie są brane, a gałęzie do tyłu są brane (ponieważ gałęzie do tyłu są często gałęziami pętli).)

Efekt likely()/unlikely() makra uĹźywajÄ ... CE GNU C __builtin_expect (Jak wspomina w odpowiedzi Drakosha) nie wstawiajÄ ... bezpoĹ " rednio podpowiedzi BP do asm. (Może to zrobić z gcc -march=pentium4, ale nie wtedy, gdy kompilacji do czegokolwiek innego).

Faktycznym efektem jest ułożenie kodu tak, aby Szybka ścieżka miała mniej branych gałęzi, a być może mniej instrukcji ogółem. Pomoże to przewidywać gałęzie w przypadkach, gdy w grę wchodzi przewidywanie statyczne (np. dynamiczne predykatory są zimne, na procesorach, które wracają do przewidywania statycznego, zamiast po prostu pozwalać gałęziom nazywać się aliasami w buforach predyktora.)

Zobacz Jaka jest zaleta _ _ built_ _ GCC w if else Oświadczenia? dla konkretnego przykładu kodu-gen.

Przeskakiwanie między różnymi blokami potencjalnie dotyka większej liczby linii kodu cache , zwiększając L1I Cache footprint i może powodować więcej chybionych instrukcji cache, jeśli było zimno. (I potencjalnie UOP-Cache footprint). Więc jest to kolejna zaleta, aby Szybka ścieżka była krótka i liniowa.

Optymalizacja profilu GCC zwykle sprawia, że makra prawdopodobne/mało prawdopodobne są niepotrzebne. Kompilator zbiera dane w czasie wykonywania, w jaki sposób każda gałąź poszła do decyzji o układzie kodu i identyfikacji gorących vs. zimnych bloków / funkcji. (np. rozwiąże pętle w funkcjach gorących, ale nie zimnych.) Patrz -fprofile-generate i -fprofile-use w podręczniku GCC . Jak korzystać z optymalizacji profili w g++?

W Przeciwnym Razie GCC musi zgadywać używając różnych heurystyk, jeśli nie używałeś prawdopodobnych / nieprawdopodobnych makr i nie używałeś PGO. {[6] } jest domyślnie włączone w -O1 i wyżej.

Https://www.phoronix.com/scan.php?page=article&item=gcc-82-pgo&num=1 mA wyniki testów PGO vs.regular z gcc8.2 na procesorze Xeon Scalable Server. (Skylake-AVX512). Każdy benchmark ma co najmniej małe przyspieszenie, a niektóre skorzystały o ~10%. (Większość z nich pochodzi prawdopodobnie z rozwijania pętli w hot loopach, ale część prawdopodobnie pochodzi z lepszego układu gałęzi i innych efektów.)

Proponuję zamiast martwić się o przewidywanie gałęzi, profilować kod i zoptymalizować kod, aby zmniejszyć liczbę gałęzi. Jednym z przykładów jest rozwijanie pętli, a drugim używanie technik programowania logicznego zamiast instrukcji if.

Większość procesorów uwielbia prefetch. Ogólnie rzecz biorąc, Instrukcja branch wygeneruje błąd wewnątrz procesora, powodując przepłukanie kolejki prefetch. Tu jest największa kara. Aby skrócić ten czas kar, przepisz (i zaprojektuj) kod tak, aby dostępnych było mniej gałęzi. Ponadto niektóre procesory mogą warunkowo wykonywać instrukcje bez konieczności rozgałęziania.

Zoptymalizowałem program z 1 godziny wykonania do 2 minut za pomocą rozwijania pętli i dużych buforów We / Wy. Przewidywanie oddziałów nie przyniosłoby w tym przypadku dużej oszczędności czasu.

SUN C Studio ma pewne pragmaty zdefiniowane dla tego przypadku.

#pragma rarely_called ()

Działa, jeśli jedna część wyrażenia warunkowego jest wywołaniem funkcji lub zaczyna się od wywołania funkcji.

Ale nie ma sposobu, aby oznaczyć ogólne wyrażenie if / while

Nie, ponieważ nie ma komendy assembly, która by dała znać predyktorowi gałęzi. Nie martw się, branch predictor jest całkiem sprytny.

Również obowiązkowy komentarz o przedwczesnej optymalizacji i o tym, jak to jest złe.

EDIT: Drakosha wspomniał o makrach dla GCC. Uważam jednak, że jest to optymalizacja kodu i w rzeczywistości nie ma nic wspólnego z prognozowaniem gałęzi.

Brzmi to dla mnie jak przesada - tego typu optymalizacja pozwoli zaoszczędzić niewielkie ilości czasu. Na przykład użycie bardziej nowoczesnej wersji gcc będzie miało znacznie większy wpływ na optymalizację. Spróbuj również włączyć i wyłączyć wszystkie flagi optymalizacji; nie wszystkie poprawiają wydajność.

Zasadniczo wydaje się bardzo mało prawdopodobne, że zrobi to znaczącą różnicę w porównaniu do wielu innych owocnych ścieżek.

EDIT: dzięki za komentarze. Zrobiłem to. community wiki, ale zostawił to, aby inni mogli zobaczyć komentarze.