Jaka jest zaleta __builtin_expect GCC w instrukcjach if else?

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?

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.

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.

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

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ść.

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).

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.