Frage an likely-unlikely, gcc, linux-kernel, linux – Wie funktionieren die wahrscheinlichen / unwahrscheinlichen Makros im Linux-Kernel und was ist ihr Nutzen?

295

Ich habe einige Teile des Linux-Kernels durchgearbeitet und folgende Aufrufe gefunden:

if (unlikely(fd < 0))
{
    /* Do something */
}

oder

if (likely(!err))
{
    /* Do something */
}

Ich habe die Definition von ihnen gefunden:

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

Ich weiß, dass sie für die Optimierung sind, aber wie funktionieren sie? Und wie viel Leistung / Größenreduzierung ist mit ihrer Verwendung zu erwarten? Und ist es den Aufwand wert (und die Portabilität wahrscheinlich zu verlieren), zumindest im Engpass-Code (natürlich im User-Bereich)?

Lautkernelnewbies FAQ (und der neuesten 3.11-Kernelquelle) unterscheiden sich die Makrodefinitionen jetzt geringfügig: #define probably (x) __builtin_expect (!! (x), 1) #define unwahrscheinlich (x) __builtin_expect (!! (x), 0) I Vermutlich trägt dies etwas mehr zur Verwirrung bei !? :) Ich brauche kein doppeltes NOT (<code> !! </ code>). Mandeep Sandhu
Dies ist wirklich nicht spezifisch für den Linux-Kernel oder für Makros, sondern eine Compiler-Optimierung. Sollte dies neu markiert werden, um dies widerzuspiegeln? Cody Brocious
Das PapierWas jeder Programmierer über Speicher wissen sollte (S. 57) enthält eine ausführliche Erklärung. Torsten Marek
Es gibt kein Portabilitätsproblem. Sie können Dinge wie trivial tun#define likely(x) (x) und#define unlikely(x) (x) auf Plattformen, die solche Hinweise nicht unterstützen. David Schwartz

Deine Antwort

10   die antwort
1

um die Hinweispräfixe für Zweige zu generieren. Unter x86 / x64 belegen sie ein Byte, sodass Sie für jeden Zweig höchstens eine Erhöhung um ein Byte erhalten. Die Leistung hängt vollständig von der Anwendung ab. In den meisten Fällen werden sie heutzutage von der Verzweigungsvorhersage des Prozessors ignoriert.

Bearbeiten: Sie haben einen Ort vergessen, bei dem sie wirklich helfen können. Dadurch kann der Compiler das Kontrollflussdiagramm neu anordnen, um die Anzahl der Verzweigungen zu verringern, die für den "wahrscheinlichen" Pfad verwendet werden. Dies kann zu einer deutlichen Verbesserung von Schleifen führen, in denen Sie mehrere Exit-Fälle prüfen.

gcc generiert niemals x86-Verzweigungshinweise - zumindest alle Intel-CPUs würden sie sowieso ignorieren. Es wird jedoch versucht, die Codegröße in unwahrscheinlichen Regionen zu begrenzen, indem Inlining und Loop-Unrolling vermieden werden. alex strange
277

Anweisungen auszugeben, die eine Verzweigungsvorhersage veranlassen, die "wahrscheinliche" Seite einer Sprunganweisung zu bevorzugen. Dies kann ein großer Gewinn sein. Wenn die Vorhersage korrekt ist, bedeutet dies, dass der Sprungbefehl im Grunde frei ist und Null Zyklen dauert. Wenn die Vorhersage jedoch falsch ist, muss die Prozessor-Pipeline gespült werden, und es können mehrere Zyklen entstehen. Solange die Vorhersage die meiste Zeit korrekt ist, ist dies in der Regel gut für die Leistung.

Wie bei allen derartigen Leistungsoptimierungen sollten Sie dies erst nach einer umfassenden Profilerstellung tun, um sicherzustellen, dass sich der Code tatsächlich in einem Engpass befindet und wahrscheinlich aufgrund der Tatsache, dass er in einer engen Schleife ausgeführt wird. Generell sind die Linux-Entwickler ziemlich erfahren, daher würde ich mir vorstellen, dass sie das getan hätten. Die Portabilität ist ihnen eigentlich egal, da sie nur auf gcc abzielen, und sie haben eine sehr genaue Vorstellung von der Assembly, die sie generieren möchten.

@ RossRogers: Mein wichtigster Punkt war, dass das Auslegen des schnellen Pfades mit meist nicht besetzten Zweigen gut ist und auch nach dem Aufwärmen der Zweigvorhersagen (z. B. in einer engen Schleife) ein Gewinn ist. Peter Cordes
re: prediction: Intel-CPUs haben seit einigen Generationen buchstäblich keine statische Verzweigungsvorhersage. Statt eines neuen Zweigs, der einen alten Eintrag im BTB löscht / überschreibt, wird dieser nur mit den veralteten Daten verwendet, die zuvor vorhanden waren. Ein kalter Zweig, der als Alias ​​für einen heißen Zweig fungiert, verliert also nicht den gesamten Vorhersageverlauf für den heißen Zweig (verschmutzt ihn nur ein wenig). Es gibt keine statische Vorhersage, da der Prädiktor nicht sagen kann, dass er zuvor noch keinen Zweig gesehen hat.Der Mikroarchitekt von Agner Fog enthält ein frühes Kapitel über die Verzweigungsvorhersage. Peter Cordes
Absolut, es gibt alle möglichen Pipeline-Gründe, warum linearer Code bevorzugt wird, und sie haben nichts mit statischen Verzweigungstreffern zu tun, die in den Befehl eingebettet sind. Moderne CPUs ignorieren diese im Allgemeinen, sodass die gesamte in dieser Antwort enthaltene Begründung überholt ist. @Bryce BeeOnRope
Diese Antwort ist größtenteils veraltet, da die Hauptbehauptung lautet, dass sie die Verzweigungsvorhersage unterstützt, und wie @PeterCordes hervorhebt, gibt es in der meisten modernen Hardware keine implizite oder explizite statische Verzweigungsvorhersage. Tatsächlich wird der Hinweis vom Compiler verwendet, um den Code zu optimieren, unabhängig davon, ob es sich um statische Verzweigungshinweise oder eine andere Art der Optimierung handelt. Für die meisten heutigen Architekturen ist es die "sonstige Optimierung", die wichtig ist, z. B. das Aneinanderreihen heißer Pfade, das bessere Planen des heißen Pfades, das Minimieren der Größe des langsamen Pfades, das Vektorisieren nur des erwarteten Pfades usw. BeeOnRope
5
long __builtin_expect(long EXP, long C);

dass der Ausdruck EXP höchstwahrscheinlich den Wert C haben wird. Der Rückgabewert ist EXP.__builtin_expect soll in einem bedingten Ausdruck verwendet werden. In fast allen Fällen wird es im Kontext von Booleschen Ausdrücken verwendet. In diesem Fall ist es wesentlich praktischer, zwei Hilfsmakros zu definieren:

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

Diese Makros können dann wie in verwendet werden

if (likely(a > 1))

Referenz:https://www.akkadia.org/drepper/cpumemory.pdf

Wie in einem Kommentar zu einer anderen Antwort gefragt wurde - Was ist der Grund für die doppelte Inversion in den Makros (d. H. Warum verwenden?)__builtin_expect(!!(expr),0) statt nur__builtin_expect((expr),0)? Michael Firth
1

mit denen der Programmierer dem Compiler einen Hinweis darauf gibt, welche Verzweigungsbedingung in einem bestimmten Ausdruck am wahrscheinlichsten ist. Auf diese Weise kann der Compiler die Verzweigungsanweisungen so erstellen, dass der häufigste Fall die geringste Anzahl von Anweisungen zur Ausführung benötigt.

Wie die Verzweigungsbefehle aufgebaut werden, hängt von der Prozessorarchitektur ab.

2

Es gibt keinen Grund, warum Sie die Portabilität verlieren sollten, wenn Sie sie verwenden.

Sie haben immer die Möglichkeit, ein einfaches Inline- oder Makro mit Null-Effekt zu erstellen, mit dem Sie auf anderen Plattformen mit anderen Compilern kompilieren können.

Wenn Sie sich auf anderen Plattformen befinden, können Sie die Optimierung nicht nutzen.

Sie verwenden keine Portabilität - die Plattformen, die sie nicht unterstützen, definieren sie lediglich, um sie zu leeren Zeichenfolgen zu erweitern. sharptooth
Ich denke, ihr zwei seid tatsächlich einverstanden - es ist nur verwirrend formuliert. (So ​​wie es aussieht, sagt Andrews Kommentar: "Sie können sie verwenden, ohne die Tragbarkeit zu verlieren", aber Sharptooth meinte, dass er sagte: "Verwenden Sie sie nicht, da sie nicht tragbar sind" und protestierte.) Miral
60

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

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)
        printf("%d\n", 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 14                   jne    24 <main+0x24>
  10:       ba 01 00 00 00          mov    $0x1,%edx
  15:       be 00 00 00 00          mov    $0x0,%esi
                    16: R_X86_64_32 .rodata.str1.1
  1a:       bf 01 00 00 00          mov    $0x1,%edi
  1f:       e8 00 00 00 00          callq  24 <main+0x24>
                    20: R_X86_64_PC32       __printf_chk-0x4
  24:       bf 00 00 00 00          mov    $0x0,%edi
                    25: R_X86_64_32 .rodata.str1.1+0x4
  29:       e8 00 00 00 00          callq  2e <main+0x2e>
                    2a: R_X86_64_PC32       puts-0x4
  2e:       31 c0                   xor    %eax,%eax
  30:       48 83 c4 08             add    $0x8,%rsp
  34:       c3                      retq

Die Anweisungsreihenfolge im Speicher war unverändertprintf und dannputs und dasretq Rückkehr.

Mit__builtin_expect

Jetzt ersetzenif (i) mit:

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 11                   je     21 <main+0x21>
  10:       bf 00 00 00 00          mov    $0x0,%edi
                    11: R_X86_64_32 .rodata.str1.1+0x4
  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
  21:       ba 01 00 00 00          mov    $0x1,%edx
  26:       be 00 00 00 00          mov    $0x0,%esi
                    27: R_X86_64_32 .rodata.str1.1
  2b:       bf 01 00 00 00          mov    $0x1,%edi
  30:       e8 00 00 00 00          callq  35 <main+0x35>
                    31: R_X86_64_PC32       __printf_chk-0x4
  35:       eb d9                   jmp    10 <main+0x10>

Dasprintf (zusammengestellt zu__printf_chk) wurde nach an das Ende der Funktion verschobenputs und die Rückkehr zur Verbesserung der Verzweigungsvorhersage, wie in anderen Antworten erwähnt.

Es ist also im Grunde dasselbe wie:

int i = !time(NULL);
if (i)
    goto printf;
puts:
puts("a");
return 0;
printf:
printf("%d\n", i);
goto puts;

Diese Optimierung wurde mit nicht durchgeführt-O0.

Aber viel Glück beim Schreiben eines Beispiels, das schneller läuft__builtin_expect als ohne,CPUs sind heutzutage wirklich schlau. Meine naiven Versuchesind hier.

2

Sie können es einfach zur Verwendung einbinden. Und eine andere Meinung, unwahrscheinlich () ist nützlicher als wahrscheinlich (), weil

if ( likely( ... ) ) {
     doSomething();
}

Es kann auch in vielen Compilern optimiert werden.

Übrigens, wenn Sie das Detailverhalten des Codes beobachten möchten, können Sie einfach Folgendes tun:

gcc -c test.c objdump -d test.o> obj.s

Dann öffnen Sie obj.s, um die Antwort zu finden.

6

dass der Compiler die entsprechenden Verzweigungshinweise ausgibt, sofern die Hardware sie unterstützt. Dies bedeutet normalerweise nur, dass ein paar Bits im Anweisungs-Opcode gedreht werden, damit sich die Codegröße nicht ändert. Die CPU beginnt, Anweisungen von der vorhergesagten Stelle abzurufen, die Pipeline zu leeren und neu zu beginnen, wenn sich herausstellt, dass dies falsch ist, wenn die Verzweigung erreicht ist. In dem Fall, in dem der Hinweis richtig ist, wird die Verzweigung viel schneller - genau wie viel schneller wird von der Hardware abhängen; und inwieweit sich dies auf die Leistung des Codes auswirkt, hängt davon ab, welcher Anteil des Zeithinweises korrekt ist.

Auf einer PowerPC-CPU kann ein nicht gedrückter Zweig beispielsweise 16 Zyklen dauern, ein korrekt angedeuteter 8 und ein falsch angedeuteter 24. In den innersten Schleifen kann ein guter Hinweis einen enormen Unterschied ausmachen.

Portabilität ist eigentlich kein Problem - vermutlich liegt die Definition in einem plattformspezifischen Header. Sie können einfach "wahrscheinlich" und "unwahrscheinlich" für Plattformen definieren, die keine statischen Verzweigungshinweise unterstützen.

Dang CISC-CPUs und ihre Anweisungen variabler Länge;) moonshadow
@CodyBrocious: Verzweigungshinweise wurden mit P4 eingeführt, aber zusammen mit P4 aufgegeben. Alle anderen x86-CPUs ignorieren diese Präfixe einfach (da Präfixe in Kontexten, in denen sie bedeutungslos sind, immer ignoriert werden). Diese Makrosnicht Bewirkt, dass gcc tatsächlich Verzweigungs-Hinweis-Präfixe auf x86 ausgibt. Sie helfen Ihnen, gcc dazu zu bringen, Ihre Funktion mit weniger belegten Zweigen auf dem Schnellweg zu gestalten. Peter Cordes
Für den Datensatz benötigt x86 zusätzlichen Platz für Verzweigungshinweise. Für Zweige muss ein Ein-Byte-Präfix angegeben werden, um den entsprechenden Hinweis anzugeben. Bin mir jedoch einig, dass Andeutungen eine gute Sache sind. Cody Brocious
Dang RISC-CPUs - Halte dich von meinen 15-Byte-Anweisungen fern;) Cody Brocious
66

die dem Compiler Hinweise geben, in welche Richtung ein Zweig gehen kann. Die Makros werden auf GCC-spezifische Erweiterungen erweitert, sofern diese verfügbar sind.

GCC verwendet diese, um die Verzweigungsvorhersage zu optimieren. Zum Beispiel, wenn Sie etwas wie das Folgende haben

if (unlikely(x)) {
  dosomething();
}

return x;

Dann kann dieser Code so umstrukturiert werden, dass er ungefähr so ​​aussieht:

if (!x) {
  return x;
}

dosomething();
return x;

Dies hat den Vorteil, dass beim erstmaligen Ausführen einer Verzweigung durch den Prozessor ein erheblicher Overhead entsteht, da möglicherweise spekulativer Code geladen und weiter ausgeführt wurde. Wenn es festlegt, dass es die Verzweigung übernehmen wird, muss es diese ungültig machen und am Verzweigungsziel beginnen.

Die meisten modernen Prozessoren verfügen jetzt über eine Art Verzweigungsvorhersage, die jedoch nur hilft, wenn Sie die Verzweigung bereits durchlaufen haben und sich die Verzweigung noch im Verzweigungsvorhersage-Cache befindet.

Es gibt eine Reihe anderer Strategien, die der Compiler und der Prozessor in diesen Szenarien verwenden können. Weitere Informationen zur Funktionsweise von Branch Predictors finden Sie bei Wikipedia:http://en.wikipedia.org/wiki/Branch_predictor

Außerdem wirkt es sich auf den Platzbedarf des Icaches aus, indem es unwahrscheinliche Codefragmente vom Hot Path fernhält. fche
Genauer gesagt kann es damit umgehengotos ohne das zu wiederholenreturn x: stackoverflow.com/a/31133787/895245 Ciro Santilli 新疆改造中心996ICU六四事件
2

CodyDies hat nichts mit Linux zu tun, ist aber ein Hinweis für den Compiler. Was passiert, hängt von der Architektur und der Compilerversion ab.

Diese besondere Funktion in Linux wird in Treibern etwas missbraucht. Wieosgx weist darauf hin, inSemantik des heißen Attributs, irgendeinhot odercold Eine in einem Block mit aufgerufene Funktion kann automatisch darauf hinweisen, dass die Bedingung wahrscheinlich ist oder nicht. Zum Beispiel,dump_stack() ist markiertcold das ist also überflüssig,

 if(unlikely(err)) {
     printk("Driver error found. %d\n", err);
     dump_stack();
 }

Zukünftige Versionen vongcc kann selektiv eine Funktion basierend auf diesen Hinweisen einbinden. Es hat auch Vorschläge gegeben, die es nicht sindboolean, aber eine Punktzahl wie inhöchstwahrscheinlichusw. Im Allgemeinen sollte es bevorzugt sein, einen alternativen Mechanismus zu verwenden, wie zcold. Es gibt keinen Grund, es an einem anderen Ort als auf heißen Pfaden zu benutzen. Was ein Compiler auf einer Architektur macht, kann auf einer anderen völlig anders sein.

Verwandte Fragen