Czy istnieje wskazówka kompilatora dla GCC, aby wymusić przewidywanie gałęzi, aby zawsze iść w określony sposób?

118

Czy w przypadku architektur Intela istnieje sposób, aby poinstruować kompilator GCC, aby generował kod, który zawsze wymusza przewidywanie gałęzi w określony sposób w moim kodzie? Czy sprzęt Intel w ogóle to obsługuje? A co z innymi kompilatorami lub oprogramowaniem sprzętowym?

Użyłbym tego w kodzie C ++, w którym znam przypadek, w którym chcę działać szybko i nie przejmuję się spowolnieniem, gdy inna gałąź musi zostać podjęta, nawet jeśli niedawno zajęła tę gałąź.

for (;;) {
  if (normal) { // How to tell compiler to always branch predict true value?
    doSomethingNormal();
  } else {
    exceptionalCase();
  }
}

Jako następne pytanie dla Evdzhana Mustafy, czy wskazówka może po prostu podać wskazówkę po raz pierwszy, gdy procesor napotka instrukcję, wszystkie kolejne przewidywania gałęzi, działają normalnie?

WilliamKF
źródło
może również zgłosić wyjątek, jeśli coś stanie się nienormalne (co jest niezależne od kompilatora)
Shep

Odpowiedzi:

9

Począwszy od C ++ 20 prawdopodobne i mało prawdopodobne atrybuty powinny być znormalizowane i są już obsługiwane w g ++ 9 . Jak omówiono tutaj , możesz pisać

if (a>b) {
  /* code you expect to run often */
  [[likely]] /* last statement */
}

np. w poniższym kodzie blok else jest wstawiany dzięki [[unlikely]]blokowi in the if

int oftendone( int a, int b );
int rarelydone( int a, int b );
int finaltrafo( int );

int divides( int number, int prime ) {
  int almostreturnvalue;
  if ( ( number % prime ) == 0 ) {
    auto k                         = rarelydone( number, prime );
    auto l                         = rarelydone( number, k );
    [[unlikely]] almostreturnvalue = rarelydone( k, l );
  } else {
    auto a            = oftendone( number, prime );
    almostreturnvalue = oftendone( a, a );
  }
  return finaltrafo( almostreturnvalue );
}

łącze godbolt porównujące obecność / brak atrybutu

pseyfert
źródło
Dlaczego warto używać [[unlikely]]w ifvs [[likely]]in the else?
WilliamKF
bez powodu, po prostu wylądowałem w tej konstelacji po wypróbowaniu, gdzie atrybut musi się znaleźć.
pseyfert
Całkiem fajne. Szkoda, że ​​metoda nie ma zastosowania do starszych wersji C ++.
Maxim Egorushkin
Fantastyczny link godbolt
Lewis Kelsey
87

GCC obsługuje funkcję __builtin_expect(long exp, long c)dostarczania tego rodzaju funkcji. Możesz sprawdzić dokumentację tutaj .

Gdzie expjest używany warunek i cjest wartością oczekiwaną. Na przykład, jeśli chcesz

if (__builtin_expect(normal, 1))

Ze względu na niezręczną składnię jest to zwykle używane przy definiowaniu dwóch niestandardowych makr, takich jak

#define likely(x)    __builtin_expect (!!(x), 1)
#define unlikely(x)  __builtin_expect (!!(x), 0)

tylko po to, aby ułatwić zadanie.

Weź to pod uwagę:

  1. to jest niestandardowe
  2. kompilator / predyktor gałęzi procesora prawdopodobnie ma większe umiejętności niż ty w podejmowaniu takich decyzji, więc może to być przedwczesna mikro-optymalizacja
Jacek
źródło
3
Czy istnieje powód, dla którego pokazujesz makro, a nie constexprfunkcję?
Columbo
22
@Columbo: Nie sądzę, aby constexprfunkcja mogła zastąpić to makro. ifUważam, że musi to być bezpośrednio zawarte w oświadczeniu. Ten sam powód assertnigdy nie mógł być constexprfunkcją.
Mooing Duck
1
@MooingDuck Zgadzam się, chociaż powodów do asertu jest więcej .
Shafik Yaghmour
7
@Columbo Jednym z powodów używania makra jest to, że jest to jedno z niewielu miejsc w C lub C ++, w których makro jest bardziej poprawne semantycznie niż funkcja. Funkcja wydaje się działać tylko z powodu optymalizacji ( jest to optymalizacja: constexprmówi tylko o semantyce wartości, a nie o wstawianiu zestawu specyficznego dla implementacji); prosta interpretacja (bez inline) kodu jest bez znaczenia. Nie ma żadnego powodu, aby używać do tego funkcji.
Leushenko
2
@Leushenko Uważaj, że __builtin_expectsamo w sobie jest wskazówką optymalizacyjną, więc twierdzenie, że metoda upraszczająca jej użycie zależy od optymalizacji, jest ... nie jest przekonujące. Ponadto nie dodałem constexprspecyfikatora, aby działał w pierwszej kolejności, ale aby działał w stałych wyrażeniach. I tak, istnieją powody, aby używać funkcji. Na przykład nie chciałbym zanieczyszczać całej mojej przestrzeni nazw uroczą małą nazwą, taką jak likely. Musiałbym użyć np. LIKELYŻeby podkreślić, że jest to makro i uniknąć kolizji, ale to po prostu brzydkie.
Columbo
46

gcc ma long __builtin_expect (długie exp, długie c) ( moje podkreślenie ):

Możesz użyć __builtin_expect, aby dostarczyć kompilatorowi informacje przewidywania gałęzi. Ogólnie rzecz biorąc, do tego celu należy używać rzeczywistych opinii o profilu (-fprofile-arcs), ponieważ programiści są notorycznie źli w przewidywaniu rzeczywistego działania ich programów . Są jednak aplikacje, w których trudno jest zebrać te dane.

Wartość zwracana to wartość exp, która powinna być wyrażeniem całkowitym. Semantyka funkcji wbudowanej polega na tym, że oczekuje się, że exp == c. Na przykład:

if (__builtin_expect (x, 0))
   foo ();

wskazuje, że nie oczekujemy wywołania foo, ponieważ spodziewamy się, że x będzie równe zero. Ponieważ jesteś ograniczony do wyrażeń całkowych dla exp, powinieneś używać konstrukcji takich jak

if (__builtin_expect (ptr != NULL, 1))
   foo (*ptr);

podczas testowania wartości wskaźnikowych lub zmiennoprzecinkowych.

Jak zauważa dokumentacja, powinieneś preferować użycie rzeczywistych opinii o profilu, a ten artykuł pokazuje praktyczny przykład tego i jak w ich przypadku przynajmniej kończy się to ulepszeniem w stosunku do używania __builtin_expect. Zobacz także Jak korzystać z optymalizacji sterowanej profilem w g ++?.

Możemy również znaleźć artykuł dla początkujących użytkowników jądra Linuksa na temat prawdopodobnie () i mało prawdopodobnych () makr jądra, które używają tej funkcji:

#define likely(x)       __builtin_expect(!!(x), 1)
#define unlikely(x)     __builtin_expect(!!(x), 0)

Zwróć uwagę na !!używane w makrze wyjaśnienie tego problemu w Dlaczego używać !! (warunek) zamiast (warunek)?.

Tylko dlatego, że ta technika jest używana w jądrze Linuksa, nie oznacza, że ​​zawsze ma sens. Z tego pytania widzimy, że ostatnio odpowiedziałem na różnicę między wydajnością funkcji podczas przekazywania parametru jako stałej czasu kompilacji lub zmiennej że wiele ręcznych technik optymalizacji nie działa w ogólnym przypadku. Musimy uważnie profilować kod, aby zrozumieć, czy technika jest skuteczna. Wiele starych technik może nawet nie mieć zastosowania w przypadku nowoczesnych optymalizacji kompilatorów.

Uwaga, chociaż wbudowane elementy nie są przenośne, clang obsługuje również __builtin_expect .

Również w przypadku niektórych architektur może to nie mieć znaczenia .

Shafik Yaghmour
źródło
To, co jest wystarczająco dobre dla jądra Linuksa, nie wystarcza dla C ++ 11.
Maxim Egorushkin
@MaximEgorushkin uwaga, tak naprawdę nie polecam jego używania, w rzeczywistości dokumentacja gcc, którą cytuję, która jest moim pierwszym cytatem, nawet nie używa tej techniki. Powiedziałbym, że głównym celem mojej odpowiedzi jest uważne rozważenie alternatyw przed pójściem tą drogą.
Shafik Yaghmour
44

Nie, nie ma. (Przynajmniej na nowoczesnych procesorach x86).

__builtin_expectwspomniany w innych odpowiedziach wpływa na sposób, w jaki gcc organizuje kod asemblera. Nie wpływa bezpośrednio na predyktor gałęzi procesora.Oczywiście, zmiana kolejności kodu będzie miała pośredni wpływ na przewidywanie gałęzi. Ale na nowoczesnych procesorach x86 nie ma instrukcji, która mówi procesorowi „załóżmy, że ta gałąź jest / nie jest zajęta”.

Zobacz to pytanie, aby uzyskać więcej szczegółów: Czy faktycznie używana predykcja rozgałęzienia prefiksu Intel x86 0x2E / 0x3E?

Aby było jasne, __builtin_expecti / lub użycie -fprofile-arcs może poprawić wydajność twojego kodu, zarówno poprzez udzielanie wskazówek predyktorowi gałęzi poprzez układ kodu (patrz Optymalizacja wydajności zestawu x86-64 - Wyrównanie i przewidywanie gałęzi ), a także poprawienie zachowania pamięci podręcznej zachowując „mało prawdopodobny” kod z dala od „prawdopodobnego” kodu.

Artelius
źródło
9
To jest niepoprawne. We wszystkich nowoczesnych wersjach x86 domyślnym algorytmem przewidywania jest przewidywanie, że gałęzie do przodu nie są brane, a gałęzie do tyłu są (patrz software.intel.com/en-us/articles/ ... ). Tak więc, zmieniając układ kodu, możesz skutecznie dać wskazówkę procesorowi. Dokładnie to robi GCC, gdy używasz __builtin_expect.
Nemo
6
@Nemo, czy przeczytałeś poprzednie zdanie mojej odpowiedzi? Wszystko, co powiedziałeś, jest objęte moją odpowiedzią lub podanymi linkami. Pytanie zadane, czy można „zmusić prognozowanie gałęzi, aby zawsze szło w określony sposób”, na które odpowiedź brzmi „nie”, a nie sądzę, aby inne odpowiedzi były wystarczająco jasne.
Artelius
4
OK, powinienem był uważniej przeczytać. Wydaje mi się, że ta odpowiedź jest technicznie poprawna, ale bezużyteczna, ponieważ pytający oczywiście szuka __builtin_expect. Więc to powinien być tylko komentarz. Ale to nie jest fałszywe, więc wycofałem swój głos przeciw.
Nemo
IMO to nie jest bezużyteczne; jest to przydatne wyjaśnienie, jak faktycznie działają procesory i kompilatory, co może mieć znaczenie dla analizy wydajności z tymi opcjami lub bez nich. np. zwykle nie możesz użyć __builtin_expectdo trywialnego stworzenia przypadku testowego, który możesz zmierzyć, a perf statktóry będzie miał bardzo wysoki współczynnik błędnych przewidywań gałęzi. Ma to tylko wpływ na układ gałęzi . A tak przy okazji, Intel od czasów Sandybridge lub przynajmniej Haswell nie używa zbyt dużo / wcale statycznych prognoz; w BHT zawsze jest jakieś przewidywanie, czy jest to nieaktualny alias, czy nie. xania.org/201602/bpu-part-two
Peter Cordes
24

Prawidłowy sposób definiowania prawdopodobnych / mało prawdopodobnych makr w C ++ 11 jest następujący:

#define LIKELY(condition) __builtin_expect(static_cast<bool>(condition), 1)
#define UNLIKELY(condition) __builtin_expect(static_cast<bool>(condition), 0)

Ta metoda jest zgodna ze wszystkimi wersjami C ++, w przeciwieństwie do [[likely]], ale opiera się na niestandardowym rozszerzeniu __builtin_expect.


Gdy te makra są zdefiniowane w ten sposób:

#define LIKELY(condition) __builtin_expect(!!(condition), 1)

Może to zmienić znaczenie ifinstrukcji i złamać kod. Rozważ następujący kod:

#include <iostream>

struct A
{
    explicit operator bool() const { return true; }
    operator int() const { return 0; }
};

#define LIKELY(condition) __builtin_expect((condition), 1)

int main() {
    A a;
    if(a)
        std::cout << "if(a) is true\n";
    if(LIKELY(a))
        std::cout << "if(LIKELY(a)) is true\n";
    else
        std::cout << "if(LIKELY(a)) is false\n";
}

I jego wynik:

if(a) is true
if(LIKELY(a)) is false

Jak widać, definicja PRAWDOPODOBNEGO używania !!jako rzutowania boolłamie semantykę if.

Nie o to chodzi operator int()i operator bool()powinno być powiązane. Co jest dobrą praktyką.

Raczej używanie !!(x)zamiast static_cast<bool>(x)traci kontekst dla konwersji kontekstowych C ++ 11 .

Maxim Egorushkin
źródło
Zwróć uwagę, że konwersje kontekstowe pojawiły się w wyniku błędu w 2012 r., A nawet pod koniec 2014 r. Nadal występowały rozbieżności we wdrożeniach. Właściwie wygląda na to, że sprawa, z którą się łączyłem, nadal nie działa dla gcc.
Shafik Yaghmour
@ShafikYaghmour To interesująca obserwacja w odniesieniu do kontekstowej konwersji związanej z switch, dzięki. Konwersja kontekstowa, o której tu mowa,bool jest częściowo związana z typem i pięcioma określonymi kontekstami tam wymienionymi , które nie obejmują switchkontekstu.
Maxim Egorushkin
Dotyczy to tylko C ++, prawda? Nie ma więc powodu, aby zmieniać istniejące projekty C do użycia (_Bool)(condition), ponieważ C nie ma przeciążenia operatora.
Peter Cordes,
2
W twoim przykładzie użyłeś po prostu (condition)nie !!(condition). Oba są truepo zmianie tego (testowane z g ++ 7.1). Czy możesz skonstruować przykład, który faktycznie zademonstruje problem, o którym mówisz, używając funkcji !!booleanize?
Peter Cordes
3
Jak zauważył Peter Cordes, mówisz „Kiedy te makra [są] zdefiniowane w ten sposób:”, a następnie pokazujesz makro za pomocą '!!', „może zmienić znaczenie instrukcji if i złamać kod. Rozważ następujący kod:” ... a następnie pokazujesz kod, który nie używa znaku „!!” w ogóle - co było zepsute jeszcze przed C ++ 11. Zmień odpowiedź, aby pokazać przykład, w którym dane makro (użycie !!) nie działa.
Carlo Wood
18

Ponieważ wszystkie inne odpowiedzi odpowiednio zasugerowały, możesz użyć, __builtin_expectaby dać kompilatorowi wskazówkę, jak zorganizować kod asemblera. Jak wskazują oficjalne dokumenty , w większości przypadków asembler wbudowany w twój mózg nie będzie tak dobry, jak ten stworzony przez zespół GCC. Zawsze najlepiej jest używać rzeczywistych danych profilu do optymalizacji kodu, zamiast zgadywać.

W podobny sposób, ale jeszcze nie wspomniano, znajduje się specyficzny dla GCC sposób wymuszenia na kompilatorze generowania kodu na „zimnej” ścieżce. Obejmuje to użycie atrybutów noinlinei cold, które robią dokładnie to, na co wyglądają. Te atrybuty można zastosować tylko do funkcji, ale w C ++ 11 można deklarować wbudowane funkcje lambda, a te dwa atrybuty można również zastosować do funkcji lambda.

Chociaż nadal należy to do ogólnej kategorii mikrooptymalizacji, a zatem ma zastosowanie standardowa rada - test nie zgaduj - wydaje mi się, że jest ona bardziej użyteczna niż __builtin_expect. Prawie żadne generacje procesorów x86 nie używają wskazówek dotyczących przewidywania rozgałęzień ( odniesienie ), więc jedyną rzeczą, na którą i tak będziesz mógł wpłynąć, jest kolejność kodu asemblera. Ponieważ wiesz, co to jest kod obsługi błędów lub kod „przypadków skrajnych”, możesz użyć tej adnotacji, aby upewnić się, że kompilator nigdy nie przewidział do niego gałęzi i połączy go z „gorącym” kodem podczas optymalizacji pod kątem rozmiaru.

Przykładowe użycie:

void FooTheBar(void* pFoo)
{
    if (pFoo == nullptr)
    {
        // Oh no! A null pointer is an error, but maybe this is a public-facing
        // function, so we have to be prepared for anything. Yet, we don't want
        // the error-handling code to fill up the instruction cache, so we will
        // force it out-of-line and onto a "cold" path.
        [&]() __attribute__((noinline,cold)) {
            HandleError(...);
        }();
    }

    // Do normal stuff
    
}

Co więcej, GCC automatycznie zignoruje to na korzyść opinii o profilu, gdy jest dostępna (np. Podczas kompilacji -fprofile-use).

Zobacz oficjalną dokumentację tutaj: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes

Cody Gray
źródło
2
Przedrostki wskazówek przewidywania gałęzi są ignorowane, ponieważ nie są potrzebne; możesz osiągnąć dokładnie ten sam efekt, po prostu zmieniając kolejność kodu. (Domyślnym algorytmem przewidywania rozgałęzień jest zgadywanie, że gałęzie do tyłu są brane, a gałęzie do przodu - nie.) Można więc w efekcie dać CPU wskazówkę i to właśnie __builtin_expectrobi. To wcale nie jest bezużyteczne. Masz rację, że coldatrybut jest również przydatny, ale __builtin_expectmyślę , że nie doceniasz użyteczności .
Nemo
Nowoczesne procesory Intel nie używają statycznego przewidywania rozgałęzień. Algorytm, który opisujesz, @Nemo, w którym przewiduje się, że gałęzie wstecz są brane, a gałęzie do przodu są przewidywane jako niepobrane, był używany we wcześniejszych procesorach i w górę przez Pentium M lub coś podobnego, ale nowoczesne projekty po prostu zgadują losowo, indeksując do ich gałęzi tabele, w których spodziewałby się znaleźć informacje o tej gałęzi i używając wszelkich informacji, które się tam znajdują (nawet jeśli mogą to być zasadniczo śmieci). Tak więc podpowiedzi do przewidywania gałęzi byłyby teoretycznie przydatne, ale być może nie w praktyce, dlatego Intel je usunął.
Cody Grey
Żeby było jasne, implementacja przewidywania gałęzi jest niezwykle skomplikowana, a ograniczenia miejsca w komentarzach zmusiły mnie do znacznego uproszczenia. To naprawdę byłaby pełna odpowiedź sama w sobie. W nowoczesnych mikroarchitekturach, takich jak Haswell, wciąż mogą istnieć ślady statycznego przewidywania gałęzi, ale nie jest to już tak proste, jak kiedyś.
Cody Grey
Czy masz odniesienie do „nowoczesnych procesorów Intel nie używają statycznego przewidywania gałęzi”? Artykuł Intela ( software.intel.com/en-us/articles/… ) mówi inaczej ... Ale to od 2011
Nemo
Nie mam oficjalnego odniesienia, @Nemo. Firma Intel jest niezwykle skąpi w kwestii algorytmów przewidywania rozgałęzień stosowanych w swoich chipach, traktując je jako tajemnice handlowe. Większość z tego, co jest znane, ustalono na podstawie testów empirycznych. Jak zawsze, materiały Agner Fog są najlepszymi surowcami, ale nawet on mówi: „Wydaje się, że predyktor gałęzi został przeprojektowany w Haswell, ale niewiele wiadomo o jego konstrukcji”. Nie mogę sobie przypomnieć, gdzie po raz pierwszy zobaczyłem testy porównawcze pokazujące, że statyczne ciśnienie BP nie było już używane, niestety.
Cody Gray
5

__builtin_expect może służyć do wskazania kompilatorowi, w którą stronę ma iść gałąź. Może to wpłynąć na sposób generowania kodu. Typowe procesory sekwencyjnie uruchamiają kod szybciej. Więc jeśli piszesz

if (__builtin_expect (x == 0, 0)) ++count;
if (__builtin_expect (y == 0, 0)) ++count;
if (__builtin_expect (z == 0, 0)) ++count;

kompilator wygeneruje kod podobny do

if (x == 0) goto if1;
back1: if (y == 0) goto if2;
back2: if (z == 0) goto if3;
back3: ;
...
if1: ++count; goto back1;
if2: ++count; goto back2;
if3: ++count; goto back3;

Jeśli twoja wskazówka jest poprawna, spowoduje to wykonanie kodu bez żadnych faktycznie wykonanych gałęzi. Będzie działać szybciej niż normalna sekwencja, w której każda instrukcja if będzie rozgałęziać się wokół kodu warunkowego i wykona trzy gałęzie.

Nowsze procesory x86 mają instrukcje dotyczące gałęzi, które mają zostać pobrane, lub dla gałęzi, które mają nie zostać pobrane (istnieje przedrostek instrukcji; nie jestem pewien szczegółów). Nie jestem pewien, czy procesor tego używa. Nie jest to zbyt przydatne, ponieważ przewidywanie gałęzi poradzi sobie z tym dobrze. Więc nie sądzę, że możesz faktycznie wpłynąć na przewidywanie gałęzi .

gnasher729
źródło
2

Jeśli chodzi o OP, nie, w GCC nie ma sposobu, aby powiedzieć procesorowi, aby zawsze zakładał, że gałąź jest lub nie jest zajęta. To, co masz, to __builtin_expect, co robi to, co mówią inni. Ponadto myślę, że nie chcesz mówić procesorowi, czy gałąź jest zajęta, czy nie zawsze . Dzisiejsze procesory, takie jak architektura Intela, potrafią rozpoznawać dość złożone wzorce i skutecznie się dostosowywać.

Jednak są chwile, kiedy chcesz przejąć kontrolę nad tym, czy domyślnie przewiduje się, że gałąź jest brana, czy nie: Kiedy wiesz, że kod będzie nazywany „zimnym” w odniesieniu do statystyk rozgałęzień.

Jeden konkretny przykład: kod zarządzania wyjątkami. Z definicji kod zarządzający będzie działał wyjątkowo, ale być może gdy wystąpi, wymagana jest maksymalna wydajność (może wystąpić błąd krytyczny, aby zająć się jak najszybciej), dlatego warto kontrolować domyślną prognozę.

Inny przykład: możesz sklasyfikować swoje dane wejściowe i przejść do kodu, który obsługuje wynik Twojej klasyfikacji. Jeśli istnieje wiele klasyfikacji, procesor może zbierać statystyki, ale je tracić, ponieważ ta sama klasyfikacja nie następuje wystarczająco szybko, a zasoby prognozowania są przeznaczone na ostatnio wywołany kod. Chciałbym, żeby było prymitywne powiedzenie procesorowi „proszę nie poświęcać zasobów prognozowania temu kodowi”, tak jak czasami można powiedzieć „nie buforuj tego”.

TheCppZoo
źródło