Was ist der Vorteil von GCCs __builtin_expect in if else-Anweisungen?

144

Ich bin auf eine gestoßen, #definein der sie verwenden __builtin_expect.

Die Dokumentation sagt:

Eingebaute Funktion: long __builtin_expect (long exp, long c)

Sie können verwenden __builtin_expect, um dem Compiler Informationen zur Verzweigungsvorhersage bereitzustellen. Im Allgemeinen sollten Sie es vorziehen, hierfür das tatsächliche Profil-Feedback zu verwenden ( -fprofile-arcs), da Programmierer bekanntermaßen schlecht in der Vorhersage der tatsächlichen Leistung ihrer Programme sind. Es gibt jedoch Anwendungen, in denen diese Daten schwer zu erfassen sind.

Der Rückgabewert ist der Wert von exp, der ein integraler Ausdruck sein sollte. Die Semantik des eingebauten ist, dass es erwartet wird, dass exp == c. Beispielsweise:

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

würde anzeigen, dass wir nicht erwarten, anzurufen foo, da wir erwarten x, Null zu sein.

Warum also nicht direkt verwenden:

if (x)
    foo ();

anstelle der komplizierten Syntax mit __builtin_expect?

kingsmasher1
quelle
2
mögliches Duplikat von wahrscheinlichen () / unwahrscheinlichen () Makros im Linux-Kernel - wie funktionieren sie? Was ist ihr Vorteil?
Ciro Santilli 法轮功 冠状 病 六四 事件 30
3
Ich denke, Ihr direkter Code hätte sein sollen if ( x == 0) {} else foo();... oder einfach, if ( x != 0 ) foo();was dem Code aus der GCC-Dokumentation entspricht.
Nawaz

Antworten:

186

Stellen Sie sich den Assemblycode vor, der generiert werden würde aus:

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

Ich denke, es sollte so etwas sein wie:

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

Sie können sehen, dass die Anweisungen in einer solchen Reihenfolge angeordnet sind, dass der barFall dem Fall vorausgeht foo(im Gegensatz zum C-Code). Dies kann die CPU-Pipeline besser nutzen, da ein Sprung die bereits abgerufenen Anweisungen zerstört.

Bevor der Sprung ausgeführt wird, werden die Anweisungen darunter (der barFall) in die Pipeline verschoben. Da der fooFall unwahrscheinlich ist, ist auch ein Springen unwahrscheinlich, weshalb ein Verprügeln der Pipeline unwahrscheinlich ist.

Blagovest Buyukliev
quelle
1
Funktioniert das wirklich so? Warum kann die foo-Definition nicht an erster Stelle stehen? Die Reihenfolge der Funktionsdefinitionen ist für einen Prototyp irrelevant, oder?
Kingsmasher1
63
Hier geht es nicht um Funktionsdefinitionen. Es geht darum, den Maschinencode so neu anzuordnen, dass die CPU mit geringerer Wahrscheinlichkeit Anweisungen abruft, die nicht ausgeführt werden sollen.
Blagovest Buyukliev
4
Ohh ich verstehe. Sie meinen also, da es eine hohe Wahrscheinlichkeit dafür gibt, wird x = 0der Balken zuerst gegeben. Und foo, wird später definiert, da die Chancen (eher die Wahrscheinlichkeit nutzen) geringer sind, oder?
Kingsmasher1
1
Ahhh ... danke. Das ist die beste Erklärung. Der Assembler-Code hat es wirklich geschafft :)
kingsmasher1
5
Dies kann auch Hinweise für den CPU- Verzweigungsprädiktor einbetten und das Pipelining verbessern
Hasturkun
50

Lassen Sie uns dekompilieren, um zu sehen, was GCC 4.8 damit macht

Blagovest erwähnte die Inversion von Zweigen, um die Pipeline zu verbessern, aber tun es aktuelle Compiler wirklich? Lass es uns herausfinden!

Ohne __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;
}

Kompilieren und dekompilieren Sie mit GCC 4.8.2 x86_64 Linux:

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

Ausgabe:

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

Die Befehlsreihenfolge im Speicher blieb unverändert: zuerst die putsund dann die retqRückkehr.

Mit __builtin_expect

Ersetzen Sie nun durch if (i):

if (__builtin_expect(i, 0))

und wir bekommen:

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>

Das putswurde bis zum Ende der Funktion verschoben, die retqRückkehr!

Der neue Code ist im Grunde der gleiche wie:

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

Diese Optimierung wurde nicht durchgeführt -O0.

Aber viel Glück beim Schreiben eines Beispiels, das mit und __builtin_expectohne schneller läuft. CPUs sind heutzutage wirklich schlau . Meine naiven Versuche sind hier .

C ++ 20 [[likely]]und[[unlikely]]

C ++ 20 hat diese C ++ - Integrationen standardisiert: Verwendung des wahrscheinlichen / unwahrscheinlichen Attributs von C ++ 20 in der if-else-Anweisung Sie werden wahrscheinlich (ein Wortspiel!) Dasselbe tun.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
quelle
1
Schauen Sie sich die dispatch_once-Funktion von libdispatch an, die __builtin_expect für eine praktische Optimierung verwendet. Der langsame Pfad wird einmal ausgeführt und nutzt __builtin_expect, um den Verzweigungsprädiktor darauf hinzuweisen, dass der schnelle Pfad verwendet werden sollte. Der schnelle Weg verläuft ohne Sperren! mikeash.com/pyblog/…
Adam Kaplan
Scheint in GCC 9.2 keinen Unterschied zu machen: gcc.godbolt.org/z/GzP6cx (tatsächlich bereits in 8.1)
Ruslan
40

Die Idee von __builtin_expectist, dem Compiler mitzuteilen, dass der Ausdruck normalerweise c ergibt, damit der Compiler für diesen Fall optimieren kann.

Ich würde vermuten, dass jemand dachte, sie wären schlau und sie würden die Dinge dadurch beschleunigen.

Leider kann es die Situation verschlimmert haben, es sei denn, die Situation ist sehr gut verstanden (es ist wahrscheinlich, dass sie so etwas nicht getan haben). Die Dokumentation sagt sogar:

Im Allgemeinen sollten Sie es vorziehen, hierfür das tatsächliche Profil-Feedback zu verwenden ( -fprofile-arcs), da Programmierer bekanntermaßen schlecht in der Vorhersage der tatsächlichen Leistung ihrer Programme sind. Es gibt jedoch Anwendungen, in denen diese Daten schwer zu erfassen sind.

Im Allgemeinen sollten Sie nur verwenden, __builtin_expectwenn:

  • Sie haben ein sehr reales Leistungsproblem
  • Sie haben die Algorithmen im System bereits entsprechend optimiert
  • Sie haben Leistungsdaten, um Ihre Behauptung zu untermauern, dass ein bestimmter Fall am wahrscheinlichsten ist
Michael Kohne
quelle
7
@ Michael: Das ist nicht wirklich eine Beschreibung der Verzweigungsvorhersage.
Oliver Charlesworth
3
"Die meisten Programmierer sind SCHLECHT" oder sowieso nicht besser als der Compiler. Jeder Idiot kann sagen, dass in einer for-Schleife die Fortsetzungsbedingung wahrscheinlich wahr ist, aber der Compiler weiß das auch, so dass es keinen Vorteil hat, dies zu sagen. Wenn aus irgendeinem Grund schrieb Sie eine Schleife , die fast immer sofort brechen würde, und wenn Sie nicht Profildaten an den Compiler für PGO, zur Verfügung stellen kann dann vielleicht der Programmierer weiß , was der Compiler nicht der Fall ist.
Steve Jessop
15
In einigen Situationen spielt es keine Rolle, welcher Zweig wahrscheinlicher ist, sondern welcher Zweig wichtig ist. Wenn der unerwartete Zweig zu abort () führt, spielt die Wahrscheinlichkeit keine Rolle, und dem erwarteten Zweig sollte bei der Optimierung Leistungspriorität zugewiesen werden.
Neowizard
1
Das Problem mit Ihrer Behauptung ist, dass die Optimierungen, die die CPU in Bezug auf die Verzweigungswahrscheinlichkeit durchführen kann, weitgehend auf eine beschränkt sind: Verzweigungsvorhersage, und diese Optimierung erfolgt unabhängig davon, ob Sie sie verwenden __builtin_expectoder nicht . Auf der anderen Seite kann der Compiler viele Optimierungen basierend auf der Verzweigungswahrscheinlichkeit durchführen, z. B. das Organisieren des Codes so, dass der Hot Path zusammenhängend ist, das Verschieben von Code, der wahrscheinlich nicht weiter entfernt wird, oder das Verringern seiner Größe, um Entscheidungen darüber zu treffen, welche Zweige vektorisiert werden sollen. Bessere Planung des Hot Path und so weiter.
BeeOnRope
1
... ohne Informationen des Entwicklers ist es blind und wählt eine neutrale Strategie. Wenn der Entwickler mit den Wahrscheinlichkeiten Recht hat (und in vielen Fällen ist es trivial zu verstehen, dass ein Zweig normalerweise genommen / nicht genommen wird), erhalten Sie diese Vorteile. Wenn Sie dies nicht tun, erhalten Sie eine Strafe, die jedoch nicht viel größer ist als die Vorteile, und am kritischsten ist, dass nichts davon die Vorhersage der CPU-Verzweigung überschreibt .
BeeOnRope
13

Nun, wie es in der Beschreibung heißt, fügt die erste Version der Konstruktion ein Vorhersageelement hinzu, das dem Compiler mitteilt, dass der x == 0Zweig der wahrscheinlichere ist - das heißt, es ist der Zweig, der von Ihrem Programm häufiger verwendet wird.

In diesem Sinne kann der Compiler die Bedingung so optimieren, dass er den geringsten Arbeitsaufwand erfordert, wenn die erwartete Bedingung erfüllt ist, auf Kosten der Notwendigkeit, im Falle einer unerwarteten Bedingung möglicherweise mehr Arbeit zu leisten.

Sehen Sie sich an, wie Bedingungen während der Kompilierungsphase und auch in der resultierenden Assembly implementiert werden, um festzustellen, wie ein Zweig möglicherweise weniger Arbeit als der andere hat.

Allerdings würde ich nur diese Optimierung erwarte spürbare Wirkung zu haben , wenn die bedingte betreffenden Teil einer engen inneren Schleife ist , dass ein aufgerufen wird viel , da der Unterschied in dem resultierenden Code relativ klein ist. Und wenn Sie es falsch herum optimieren, können Sie Ihre Leistung verringern.

Kerrek SB
quelle
Aber am Ende geht es darum, die Bedingung durch den Compiler zu überprüfen. Wollen Sie damit sagen, dass der Compiler immer diesen Zweig übernimmt und fortfährt, und später, wenn es keine Übereinstimmung gibt? Was geschieht? Ich denke, es gibt etwas mehr über dieses Zweigvorhersage-Zeug im Compiler-Design und wie es funktioniert.
Kingsmasher1
2
Dies ist wirklich eine Mikrooptimierung. Schauen Sie nach, wie Bedingungen implementiert werden. Es gibt eine kleine Tendenz zu einem Zweig. Nehmen wir als hypothetisches Beispiel an, eine Bedingung wird zu einem Test plus einem Sprung in der Baugruppe. Dann ist der springende Zweig langsamer als der nicht springende, sodass Sie es vorziehen, den erwarteten Zweig zum nicht springenden Zweig zu machen.
Kerrek SB
Danke, du und Michael, ich denke, sie haben ähnliche Ansichten, aber in anderen Worten :-) Ich verstehe, dass die genauen Compiler-Interna über Test-and-Branch hier nicht zu erklären sind :)
kingsmasher1
Sie sind auch sehr einfach zu lernen, indem Sie im Internet suchen :-)
Kerrek SB
Ich gehe besser zurück zu meinem College-Buch von compiler design - Aho, Ullmann, Sethi:-)
kingsmasher1
1

Ich sehe keine der Antworten auf die Frage, die Sie meiner Meinung nach gestellt haben, umschrieben:

Gibt es eine portablere Möglichkeit, dem Compiler eine Verzweigungsvorhersage anzuzeigen?

Der Titel Ihrer Frage hat mich dazu gebracht, es so zu machen:

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

Wenn der Compiler davon ausgeht, dass 'true' wahrscheinlicher ist, kann er für das Nichtaufrufen optimieren foo().

Das Problem hierbei ist nur, dass Sie im Allgemeinen nicht wissen, was der Compiler annehmen wird. Daher muss jeder Code, der diese Art von Technik verwendet, sorgfältig gemessen (und möglicherweise im Laufe der Zeit überwacht werden, wenn sich der Kontext ändert).

Brent Bradburn
quelle
Dies mag tatsächlich genau das gewesen sein, was das OP ursprünglich tippen wollte (wie im Titel angegeben) - aber aus irgendeinem Grund wurde die Verwendung von elseaus dem Hauptteil des Beitrags herausgelassen.
Brent Bradburn
1

Ich teste es auf einem Mac gemäß @Blagovest Buyukliev und @Ciro. Die Assemblierungen sehen klar aus und ich füge Kommentare hinzu.

Befehle sind gcc -c -O3 -std=gnu11 testOpt.c; otool -tVI testOpt.o

Wenn ich -O3 , benutze, sieht es gleich aus, egal ob __builtin_expect (i, 0) existiert oder nicht.

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

Beim Kompilieren mit -O2 , sieht es mit und ohne __builtin_expect (i, 0) anders aus.

Zuerst ohne

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

Jetzt mit __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

Zusammenfassend funktioniert __builtin_expect im letzten Fall.

Victor Choy
quelle