Ich bin auf eine gestoßen, #define
in 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, dassexp == c
. Beispielsweise:if (__builtin_expect (x, 0)) foo ();
würde anzeigen, dass wir nicht erwarten, anzurufen
foo
, da wir erwartenx
, Null zu sein.
Warum also nicht direkt verwenden:
if (x)
foo ();
anstelle der komplizierten Syntax mit __builtin_expect
?
if ( x == 0) {} else foo();
... oder einfach,if ( x != 0 ) foo();
was dem Code aus der GCC-Dokumentation entspricht.Antworten:
Stellen Sie sich den Assemblycode vor, der generiert werden würde aus:
Ich denke, es sollte so etwas sein wie:
Sie können sehen, dass die Anweisungen in einer solchen Reihenfolge angeordnet sind, dass der
bar
Fall dem Fall vorausgehtfoo
(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
bar
Fall) in die Pipeline verschoben. Da derfoo
Fall unwahrscheinlich ist, ist auch ein Springen unwahrscheinlich, weshalb ein Verprügeln der Pipeline unwahrscheinlich ist.quelle
x = 0
der Balken zuerst gegeben. Und foo, wird später definiert, da die Chancen (eher die Wahrscheinlichkeit nutzen) geringer sind, oder?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
Kompilieren und dekompilieren Sie mit GCC 4.8.2 x86_64 Linux:
Ausgabe:
Die Befehlsreihenfolge im Speicher blieb unverändert: zuerst die
puts
und dann dieretq
Rückkehr.Mit
__builtin_expect
Ersetzen Sie nun durch
if (i)
:und wir bekommen:
Das
puts
wurde bis zum Ende der Funktion verschoben, dieretq
Rückkehr!Der neue Code ist im Grunde der gleiche wie:
Diese Optimierung wurde nicht durchgeführt
-O0
.Aber viel Glück beim Schreiben eines Beispiels, das mit und
__builtin_expect
ohne 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.
quelle
Die Idee von
__builtin_expect
ist, 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 nur verwenden,
__builtin_expect
wenn:quelle
__builtin_expect
oder 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.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 == 0
Zweig 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.
quelle
compiler design - Aho, Ullmann, Sethi
:-)Ich sehe keine der Antworten auf die Frage, die Sie meiner Meinung nach gestellt haben, umschrieben:
Der Titel Ihrer Frage hat mich dazu gebracht, es so zu machen:
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).
quelle
else
aus dem Hauptteil des Beitrags herausgelassen.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.
Beim Kompilieren mit -O2 , sieht es mit und ohne __builtin_expect (i, 0) anders aus.
Zuerst ohne
Jetzt mit __builtin_expect (i, 0)
Zusammenfassend funktioniert __builtin_expect im letzten Fall.
quelle