Jaka jest zaleta __builtin_expect GCC w instrukcjach if else?

144

Natknąłem się na plik, #definew którym używają __builtin_expect.

Dokumentacja mówi:

Wbudowana funkcja: long __builtin_expect (long exp, long c)

Możesz użyć, __builtin_expectaby dostarczyć kompilatorowi informacje przewidywania gałęzi. Ogólnie rzecz biorąc, do tego ( -fprofile-arcs) należy używać rzeczywistych opinii o profilu , ponieważ programiści są notorycznie słabi 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 elementu wbudowanego polega na tym, że jest to oczekiwane exp == c. Na przykład:

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

wskazywałoby, że nie spodziewamy się zadzwonić foo, ponieważ spodziewamy xsię, że będzie zero.

Dlaczego więc nie użyć bezpośrednio:

if (x)
    foo ();

zamiast skomplikowanej składni z __builtin_expect?

kingsmasher1
źródło
2
możliwy duplikat prawdopodobnych () / mało prawdopodobnych () makr w jądrze Linuksa - jak one działają? Jaka jest ich korzyść?
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
3
Myślę, że twój bezpośredni kod powinien był być if ( x == 0) {} else foo();... lub po prostu if ( x != 0 ) foo();odpowiednikiem kodu z dokumentacji GCC.
Nawaz

Odpowiedzi:

187

Wyobraź sobie kod asemblera, który zostałby wygenerowany z:

if (__builtin_expect(x, 0)) {
    foo();
    ...
} else {
    bar();
    ...
}

Myślę, że powinno to być coś takiego:

  cmp   $x, 0
  jne   _foo
_bar:
  call  bar
  ...
  jmp   after_if
_foo:
  call  foo
  ...
after_if:

Widać, że instrukcje są ułożone w takiej kolejności, że barsprawa poprzedza foosprawę (w przeciwieństwie do kodu C). Może to lepiej wykorzystywać potok procesora, ponieważ skok odrzuca już pobrane instrukcje.

Przed wykonaniem skoku instrukcje znajdujące się pod nim ( barobudowa) są umieszczane w potoku. Ponieważ foosprawa jest mało prawdopodobna, skakanie również jest mało prawdopodobne, dlatego też jest mało prawdopodobne, aby uderzyć rurociąg.

Blagovest Buyukliev
źródło
1
Czy to naprawdę tak działa? Dlaczego definicja foo nie może być pierwsza? Kolejność definicji funkcji nie ma znaczenia, o ile masz prototyp, prawda?
kingsmasher1
63
Tu nie chodzi o definicje funkcji. Chodzi o przestawienie kodu maszynowego w sposób, który powoduje mniejsze prawdopodobieństwo, że CPU pobierze instrukcje, które nie zostaną wykonane.
Blagovest Buyukliev,
4
Och, rozumiem. Więc masz na myśli, że istnieje duże prawdopodobieństwo, x = 0więc słupek jest podawany jako pierwszy. I foo, jest zdefiniowane później, ponieważ jego szanse (raczej prawdopodobieństwo użycia) są mniejsze, prawda?
kingsmasher1
1
Ahhh ... dzięki. To najlepsze wyjaśnienie. Kod asemblera naprawdę
załatwił sprawę
5
Może to również zawierać wskazówki dotyczące predyktora gałęzi procesora , poprawiając przetwarzanie potokowe
Hasturkun,
50

Zdekompilujmy, aby zobaczyć, co robi z tym GCC 4.8

Blagovest wspomniał o inwersji gałęzi w celu ulepszenia potoku, ale czy obecne kompilatory naprawdę to robią? Dowiedzmy Się!

Bez __builtin_expect

#include "stdio.h"
#include "time.h"

int main() {
    /* Use time to prevent it from being optimized away. */
    int i = !time(NULL);
    if (i)
        puts("a");
    return 0;
}

Kompiluj i dekompiluj z GCC 4.8.2 x86_64 Linux:

gcc -c -O3 -std=gnu11 main.c
objdump -dr main.o

Wynik:

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       75 0a                   jne    1a <main+0x1a>
  10:       bf 00 00 00 00          mov    $0x0,%edi
                    11: R_X86_64_32 .rodata.str1.1
  15:       e8 00 00 00 00          callq  1a <main+0x1a>
                    16: R_X86_64_PC32       puts-0x4
  1a:       31 c0                   xor    %eax,%eax
  1c:       48 83 c4 08             add    $0x8,%rsp
  20:       c3                      retq

Kolejność instrukcji w pamięci pozostała niezmieniona: najpierw the, putsa następnie retqpowrót.

Z __builtin_expect

Teraz zamień na if (i):

if (__builtin_expect(i, 0))

i otrzymujemy:

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       74 07                   je     17 <main+0x17>
  10:       31 c0                   xor    %eax,%eax
  12:       48 83 c4 08             add    $0x8,%rsp
  16:       c3                      retq
  17:       bf 00 00 00 00          mov    $0x0,%edi
                    18: R_X86_64_32 .rodata.str1.1
  1c:       e8 00 00 00 00          callq  21 <main+0x21>
                    1d: R_X86_64_PC32       puts-0x4
  21:       eb ed                   jmp    10 <main+0x10>

putsZostała przeniesiona do samego końca funkcji, w retqzamian!

Nowy kod jest w zasadzie taki sam jak:

int i = !time(NULL);
if (i)
    goto puts;
ret:
return 0;
puts:
puts("a");
goto ret;

Ta optymalizacja nie została wykonana -O0.

Ale powodzenia w pisaniu przykładu, który działa szybciej z procesorami__builtin_expect niż bez nich, w dzisiejszych czasach są naprawdę inteligentne . Moje naiwne próby są tutaj .

C ++ 20 [[likely]]i[[unlikely]]

C ++ 20 ustandaryzował te wbudowane C ++: Jak używać atrybutu prawdopodobny / mało prawdopodobny C ++ 20 w instrukcji if-else Prawdopodobnie (gra słów!) Zrobią to samo.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
źródło
1
Sprawdź funkcję dispatch_once libdispatch, która używa __builtin_expect do praktycznej optymalizacji. Wolna ścieżka działa jednorazowo i wykorzystuje __builtin_expect, aby wskazać predyktorowi gałęzi, że należy obrać szybką ścieżkę. Szybka ścieżka przebiega bez żadnych blokad! mikeash.com/pyblog/…
Adam Kaplan,
Wydaje się, że nie robi żadnej różnicy w GCC 9.2: gcc.godbolt.org/z/GzP6cx (właściwie już w 8.1)
Ruslan
40

Pomysł __builtin_expectpolega na tym, aby powiedzieć kompilatorowi, że zwykle okaże się, że wyrażenie ma wartość c, aby kompilator mógł zoptymalizować ten przypadek.

Domyślam się, że ktoś myślał, że jest sprytny i że robiąc to, przyspiesza.

Niestety, jeśli sytuacja nie jest dobrze zrozumiana (prawdopodobnie nie zrobili czegoś takiego), mogło to pogorszyć sytuację. Dokumentacja mówi nawet:

Ogólnie rzecz biorąc, do tego ( -fprofile-arcs) należy używać rzeczywistych opinii o profilu , ponieważ programiści są notorycznie słabi w przewidywaniu rzeczywistego działania ich programów. Są jednak aplikacje, w których trudno jest zebrać te dane.

Ogólnie rzecz biorąc, nie powinieneś używać, __builtin_expectchyba że:

  • Masz bardzo realny problem z wydajnością
  • Odpowiednio zoptymalizowałeś już algorytmy w systemie
  • Masz dane dotyczące wydajności, aby potwierdzić swoje twierdzenie, że dany przypadek jest najbardziej prawdopodobny
Michael Kohne
źródło
7
@Michael: To nie jest tak naprawdę opis przewidywania gałęzi.
Oliver Charlesworth
3
„większość programistów jest ZŁY” lub w każdym razie nie lepszy niż kompilator. Każdy idiota może stwierdzić, że w pętli for warunek kontynuacji prawdopodobnie będzie prawdziwy, ale kompilator też to wie, więc nie ma żadnej korzyści z powiedzenia tego. Jeśli z jakiegoś powodu napisałem pętlę, która prawie zawsze przerwać natychmiast, a jeśli nie może dostarczyć danych profilu do kompilatora dla PGO, wtedy może programista wie coś kompilator nie.
Steve Jessop
15
W niektórych sytuacjach nie ma znaczenia, która gałąź jest bardziej prawdopodobna, ale raczej która ma znaczenie. Jeśli nieoczekiwana gałąź prowadzi do abort (), prawdopodobieństwo nie ma znaczenia, a oczekiwana gałąź powinna mieć priorytet wydajności podczas optymalizacji.
Neowizard
1
Problem z twoim twierdzeniem polega na tym, że optymalizacje, które procesor może wykonać w odniesieniu do prawdopodobieństwa rozgałęzienia, są w zasadzie ograniczone do jednego: przewidywania gałęzi, a ta optymalizacja ma miejsce niezależnie od tego, czy używasz, __builtin_expectczy nie . Z drugiej strony kompilator może przeprowadzić wiele optymalizacji na podstawie prawdopodobieństwa rozgałęzienia, takich jak zorganizowanie kodu tak, aby gorąca ścieżka była ciągła, przenoszenie kodu prawdopodobnie nie było zoptymalizowane dalej lub zmniejszenie jego rozmiaru, podejmowanie decyzji o tym, które gałęzie mają być wektoryzowane, lepsze planowanie gorącej ścieżki i tak dalej.
BeeOnRope
1
... bez informacji od dewelopera jest ślepy i wybiera neutralną strategię. Jeśli deweloper ma rację co do prawdopodobieństw (aw wielu przypadkach banalne jest zrozumienie, że gałąź jest zwykle zajęta / nie) - uzyskasz te korzyści. Jeśli nie, otrzymujesz jakąś karę, ale nie jest ona w jakiś sposób większa niż korzyści, a co najważniejsze, żadna z tych rzeczy w żaden sposób nie zastępuje prognozy gałęzi procesora.
BeeOnRope
13

Cóż, jak jest napisane w opisie, pierwsza wersja dodaje do konstrukcji element predykcyjny, mówiąc kompilatorowi, że x == 0gałąź jest bardziej prawdopodobna - to znaczy jest to gałąź, która będzie częściej pobierana przez twój program.

Mając to na uwadze, kompilator może zoptymalizować warunek tak, aby wymagał najmniejszego nakładu pracy, gdy jest spełniony oczekiwany warunek, kosztem być może konieczności wykonania większej ilości pracy w przypadku nieoczekiwanego stanu.

Przyjrzyj się, jak warunkowe są implementowane podczas fazy kompilacji, a także w wynikowym asemblacji, aby zobaczyć, jak jedna gałąź może być mniej obciążona niż druga.

Jednak spodziewałbym się, że ta optymalizacja przyniesie zauważalny efekt tylko wtedy, gdy dany warunek jest częścią ścisłej wewnętrznej pętli, która jest często wywoływana , ponieważ różnica w wynikowym kodzie jest stosunkowo niewielka. A jeśli zoptymalizujesz go w niewłaściwy sposób, możesz zmniejszyć wydajność.

Kerrek SB
źródło
Ale na końcu chodzi o sprawdzenie warunku przez kompilator, czy masz na myśli powiedzieć, że kompilator zawsze zakłada tę gałąź i kontynuuje, a później, jeśli nie ma dopasowania, to? Co się dzieje? Myślę, że jest coś więcej na temat przewidywania gałęzi w projektowaniu kompilatora i jak to działa.
kingsmasher1
2
To naprawdę mikro-optymalizacja. Sprawdź, jak zaimplementowano warunki warunkowe, istnieje niewielkie odchylenie w kierunku jednej gałęzi. Jako hipotetyczny przykład załóżmy, że warunek staje się testem plus skok w zestawie. Wtedy gałąź skacząca jest wolniejsza niż ta, która nie skacze, więc wolałbyś, aby oczekiwana gałąź była nieskacząca.
Kerrek SB,
Dziękuję, myślę, że twój i Michael mają podobne poglądy, ale
używając
Bardzo łatwo się ich też nauczyć, przeszukując internet :-)
Kerrek SB,
Lepiej wrócę do mojej uczelnianej książki compiler design - Aho, Ullmann, Sethi:-)
kingsmasher1
1

Nie widzę żadnej odpowiedzi odnoszącej się do pytania, o które myślę, że zadawałeś, parafrazując:

Czy istnieje bardziej przenośny sposób podpowiadania kompilatorowi predykcji gałęzi?

Tytuł twojego pytania skłonił mnie do zrobienia tego w ten sposób:

if ( !x ) {} else foo();

Jeśli kompilator przyjmie, że „prawda” jest bardziej prawdopodobna, może zoptymalizować, aby nie wywoływać foo().

Problem polega na tym, że generalnie nie wiesz, co przyjmie kompilator - więc każdy kod, który używa tego rodzaju techniki, musiałby być dokładnie zmierzony (i prawdopodobnie monitorowany w czasie, jeśli zmieni się kontekst).

Brent Bradburn
źródło
W rzeczywistości mogło to być dokładnie to, co pierwotnie zamierzał wpisać PO (jak wskazuje tytuł) - ale z jakiegoś powodu użycie elsezostało pominięte w treści postu.
Brent Bradburn
1

Testuję to na Macu zgodnie z @Blagovest Buyukliev i @Ciro. Zestawy wyglądają przejrzyście i dodaję komentarze;

Polecenia są gcc -c -O3 -std=gnu11 testOpt.c; otool -tVI testOpt.o

Kiedy używam -O3 ,, wygląda to tak samo, niezależnie od tego, czy __builtin_expect (i, 0) istnieje, czy nie.

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp     
0000000000000001    movq    %rsp, %rbp    // open function stack
0000000000000004    xorl    %edi, %edi       // set time args 0 (NULL)
0000000000000006    callq   _time      // call time(NULL)
000000000000000b    testq   %rax, %rax   // check time(NULL)  result
000000000000000e    je  0x14           //  jump 0x14 if testq result = 0, namely jump to puts
0000000000000010    xorl    %eax, %eax   //  return 0   ,  return appear first 
0000000000000012    popq    %rbp    //  return 0
0000000000000013    retq                     //  return 0
0000000000000014    leaq    0x9(%rip), %rdi  ## literal pool for: "a"  // puts  part, afterwards
000000000000001b    callq   _puts
0000000000000020    xorl    %eax, %eax
0000000000000022    popq    %rbp
0000000000000023    retq

Przy kompilacji z -O2 , wygląda inaczej zi bez __builtin_expect (i, 0)

Po pierwsze bez

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp
0000000000000001    movq    %rsp, %rbp
0000000000000004    xorl    %edi, %edi
0000000000000006    callq   _time
000000000000000b    testq   %rax, %rax
000000000000000e    jne 0x1c       //   jump to 0x1c if not zero, then return
0000000000000010    leaq    0x9(%rip), %rdi ## literal pool for: "a"   //   put part appear first ,  following   jne 0x1c
0000000000000017    callq   _puts
000000000000001c    xorl    %eax, %eax     // return part appear  afterwards
000000000000001e    popq    %rbp
000000000000001f    retq

Teraz z __builtin_expect (i, 0)

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp
0000000000000001    movq    %rsp, %rbp
0000000000000004    xorl    %edi, %edi
0000000000000006    callq   _time
000000000000000b    testq   %rax, %rax
000000000000000e    je  0x14   // jump to 0x14 if zero  then put. otherwise return 
0000000000000010    xorl    %eax, %eax   // return appear first 
0000000000000012    popq    %rbp
0000000000000013    retq
0000000000000014    leaq    0x7(%rip), %rdi ## literal pool for: "a"
000000000000001b    callq   _puts
0000000000000020    jmp 0x10

Podsumowując, __builtin_expect działa w tym ostatnim przypadku.

Victor Choy
źródło