Wie funktionieren die wahrscheinlichen / unwahrscheinlichen Makros im Linux-Kernel und welchen Nutzen haben sie?

348

Ich habe einige Teile des Linux-Kernels durchsucht und Aufrufe wie diesen 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 zur Optimierung dienen, aber wie funktionieren sie? Und wie viel Leistungs- / Größenabnahme kann von ihrer Verwendung erwartet werden? Und ist es den Aufwand wert (und wahrscheinlich die Portabilität zu verlieren), zumindest im Engpasscode (natürlich im Userspace).

Ende
quelle
7
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
11
Das Papier Was jeder Programmierer über Speicher wissen sollte (S. 57), enthält eine ausführliche Erklärung.
Torsten Marek
2
siehe auchBOOST_LIKELY
Ruggero Turra
4
Verwandte: ein Benchmark für die Verwendung__builtin_expect auf eine andere Frage.
YSC
13
Es gibt kein Portabilitätsproblem. Sie können trivial Dinge wie #define likely(x) (x)und #define unlikely(x) (x)auf Plattformen tun, die diese Art von Hinweisen nicht unterstützen.
David Schwartz

Antworten:

328

Sie weisen den Compiler an, Anweisungen auszugeben, die dazu führen, dass die Verzweigungsvorhersage die "wahrscheinliche" Seite einer Sprunganweisung begünstigt. Dies kann ein großer Gewinn sein. Wenn die Vorhersage korrekt ist, bedeutet dies, dass die Sprunganweisung grundsätzlich frei ist und keine Zyklen benötigt. Wenn andererseits die Vorhersage falsch ist, bedeutet dies, dass die Prozessor-Pipeline geleert werden muss und mehrere Zyklen kosten kann. 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 Mikronatur, dass er in einer engen Schleife ausgeführt wird. Im Allgemeinen sind die Linux-Entwickler ziemlich erfahren, daher würde ich mir vorstellen, dass sie das getan hätten. Sie kümmern sich nicht wirklich um Portabilität, da sie nur auf gcc abzielen, und sie haben eine sehr genaue Vorstellung von der Assembly, die sie generieren sollen.

1800 INFORMATIONEN
quelle
3
Diese Makros wurden hauptsächlich zur Fehlerprüfung verwendet. Weil der Fehler weniger wahrscheinlich als der normale Betrieb bleibt. Einige Leute machen Profiling oder Berechnung, um das am häufigsten verwendete Blatt zu entscheiden ...
Gavenkoa
51
In Bezug auf das Fragment "[...]that it is being run in a tight loop"verfügen viele CPUs über einen Verzweigungsprädiktor. Die Verwendung dieser Makros hilft daher nur beim ersten Ausführen von Code oder wenn die Verlaufstabelle von einer anderen Verzweigung mit demselben Index in die Verzweigungstabelle überschrieben wird. In einer engen Schleife und unter der Annahme, dass eine Verzweigung die meiste Zeit in eine Richtung verläuft, wird der Verzweigungsprädiktor wahrscheinlich sehr schnell beginnen, die richtige Verzweigung zu erraten. - Dein Freund in Pedanterie.
Ross Rogers
8
@ RossRogers: Was wirklich passiert, ist, dass der Compiler die Zweige so anordnet, dass der häufigste Fall der nicht genommene ist. Dies ist schneller, selbst wenn die Verzweigungsvorhersage funktioniert. Aufgenommene Zweige sind problematisch für das Abrufen und Dekodieren von Anweisungen, selbst wenn sie perfekt vorhergesagt werden. Einige CPUs sagen statisch Zweige voraus, die nicht in ihrer Verlaufstabelle enthalten sind, normalerweise mit der Annahme, dass sie nicht für Vorwärtszweige verwendet werden. Intel-CPUs funktionieren nicht so: Sie versuchen nicht zu überprüfen, ob der Eintrag in der Prädiktortabelle für diesen Zweig bestimmt ist, sondern verwenden ihn trotzdem. Ein heißer Zweig und ein kalter Zweig könnten den gleichen Eintrag haben ...
Peter Cordes
12
Diese Antwort ist größtenteils veraltet, da die Hauptbehauptung darin besteht, 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 "jede andere Optimierung", die wichtig ist, z. B. das Zusammenführen heißer Pfade, das bessere Planen des heißen Pfads, das Minimieren der Größe des langsamen Pfads, das Vektorisieren nur des erwarteten Pfads usw. usw.
BeeOnRope
3
@BeeOnRope Aufgrund des Cache-Prefetch und der Wortgröße ist es immer noch von Vorteil, ein Programm linear auszuführen. Der nächste Speicherort wird bereits abgerufen und im Cache das Verzweigungsziel möglicherweise oder möglicherweise nicht. Mit einer 64-Bit-CPU greifen Sie mindestens 64 Bit gleichzeitig zu. Abhängig von der DRAM-Verschachtelung können 2x 3x oder mehr Bits erfasst werden.
Bryce
88

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 Befehlsreihenfolge im Speicher blieb unverändert: zuerst die printfund dann putsund die retqRückgabe.

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

Das printf(kompiliert zu __printf_chk) wurde nach putsund nach der Rückkehr an das Ende der Funktion verschoben, um die Verzweigungsvorhersage zu verbessern, wie in anderen Antworten erwähnt.

Es ist also im Grunde dasselbe wie:

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

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
71

Dies sind Makros, 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 so etwas wie das Folgende haben

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

return x;

Dann kann es diesen Code so umstrukturieren, dass er eher so aussieht wie:

if (!x) {
  return x;
}

dosomething();
return x;

Dies hat den Vorteil, dass der Prozessor beim ersten Verzweigen einen erheblichen Overhead verursacht, da er möglicherweise spekulativ Code geladen und weiter ausgeführt hat. Wenn es feststellt, dass es den Zweig nehmen wird, muss es diesen ungültig machen und am Zweigziel beginnen.

Die meisten modernen Prozessoren haben jetzt eine Art Verzweigungsvorhersage, aber das hilft nur, wenn Sie die Verzweigung zuvor 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 Zweigprädiktoren finden Sie unter Wikipedia: http://en.wikipedia.org/wiki/Branch_predictor

dvorak
quelle
3
Außerdem wirkt es sich auf den Icache-Footprint aus, indem unwahrscheinliche Codeausschnitte aus dem Hot Path entfernt werden.
fche
2
Genauer gesagt, es kann mit gotos gemacht werden, ohne das zu wiederholen return x: stackoverflow.com/a/31133787/895245
Ciro Santilli 法轮功 冠状 病. 事件 30
7

Sie veranlassen den Compiler, die entsprechenden Verzweigungshinweise auszugeben, wo die Hardware sie unterstützt. Dies bedeutet normalerweise nur, ein paar Bits im Befehls-Opcode zu drehen, damit sich die Codegröße nicht ändert. Die CPU beginnt mit dem Abrufen von Anweisungen vom vorhergesagten Speicherort, spült die Pipeline und beginnt von vorne, wenn sich herausstellt, dass dies bei Erreichen der Verzweigung falsch ist. Wenn der Hinweis korrekt ist, wird der Zweig dadurch viel schneller - genau wie viel schneller, hängt von der Hardware ab. und wie sehr dies die Leistung des Codes beeinflusst, hängt davon ab, welcher Anteil des Zeithinweises korrekt ist.

Beispielsweise kann auf einer PowerPC-CPU ein nicht angezeigter Zweig 16 Zyklen dauern, ein korrekt angedeuteter 8 und ein falsch angedeuteter 24. In innersten Schleifen kann ein guter Hinweis einen enormen Unterschied machen.

Portabilität ist nicht wirklich ein Problem - vermutlich befindet sich die Definition in einem plattformübergreifenden Header. Sie können einfach "wahrscheinlich" und "unwahrscheinlich" für Plattformen definieren, die keine statischen Verzweigungshinweise unterstützen.

Mondschatten
quelle
3
Für den Datensatz benötigt x86 zusätzlichen Platz für Verzweigungshinweise. Sie müssen ein 1-Byte-Präfix für Zweige haben, um den entsprechenden Hinweis anzugeben. Einverstanden, dass Andeutungen eine gute Sache (TM) sind.
Cody Brocious
2
Dang CISC-CPUs und ihre Anweisungen mit variabler Länge;)
Mondschatten
3
Dang RISC CPUs - Halten Sie sich von meinen 15-Byte-Anweisungen fern;)
Cody Brocious
7
@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 Makros bewirken nicht, dass gcc auf x86 tatsächlich Verzweigungshinweispräfixe ausgibt. Sie helfen Ihnen dabei, gcc dazu zu bringen, Ihre Funktion mit weniger genommenen Zweigen auf dem schnellen Weg zu gestalten.
Peter Cordes
5
long __builtin_expect(long EXP, long C);

Dieses Konstrukt teilt dem Compiler mit, dass der Ausdruck EXP höchstwahrscheinlich den Wert C hat. Der Rückgabewert ist EXP. __builtin_expect soll in einem bedingten Ausdruck verwendet werden. In fast allen Fällen wird es im Zusammenhang mit booleschen Ausdrücken verwendet. In diesem Fall ist es viel bequemer, 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

Ashish Maurya
quelle
1
Wie in einem Kommentar zu einer anderen Antwort gefragt wurde - was ist der Grund für die doppelte Inversion in den Makros (dh warum __builtin_expect(!!(expr),0)statt nur verwenden __builtin_expect((expr),0)?
Michael Firth
1
@MichaelFirth "doppelte Inversion" !!ist gleichbedeutend mit dem Casting von etwas zu a bool. Manche Leute schreiben es gerne so.
Ben XO
2

(allgemeiner Kommentar - andere Antworten decken die Details ab)

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.

Sie profitieren einfach nicht von der Optimierung, wenn Sie sich auf anderen Plattformen befinden.

Andrew Edgecombe
quelle
1
Sie verwenden keine Portabilität - die Plattformen, die sie nicht unterstützen, definieren sie nur, um sie auf leere Zeichenfolgen zu erweitern.
Scharfzahn
2
Ich denke, ihr zwei seid euch tatsächlich einig - es ist nur verwirrend formuliert. (Wie es aussieht, sagt Andrews Kommentar: "Sie können sie verwenden, ohne die Portabilität zu verlieren", aber Sharptooth dachte, dass er sagte: "Verwenden Sie sie nicht, da sie nicht tragbar sind" und widersprach.)
Miral
2

Laut dem Kommentar von Cody hat dies nichts mit Linux zu tun, sondern ist ein Hinweis auf den Compiler. Was passiert, hängt von der Architektur und der Compilerversion ab.

Diese spezielle Funktion unter Linux wird in Treibern etwas missbraucht. Wie osgx in der Semantik des Hot-Attributs hervorhebt , kann jede hotoder jede coldFunktion, die in einem Block aufgerufen wird, automatisch darauf hinweisen, dass die Bedingung wahrscheinlich ist oder nicht. Zum Beispiel dump_stack()ist markiert, coldso dass dies redundant ist,

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

Zukünftige Versionen von gcckönnen eine Funktion basierend auf diesen Hinweisen selektiv inline einbinden. Es gab auch Vorschläge, dass dies nicht der Fall ist boolean, aber eine Punktzahl wie höchstwahrscheinlich usw. Im Allgemeinen sollte es bevorzugt werden, einen alternativen Mechanismus wie zu verwenden cold. Es gibt keinen Grund, es an einem anderen Ort als auf heißen Wegen zu verwenden. Was ein Compiler auf einer Architektur macht, kann auf einer anderen völlig anders sein.

Kunstloser Lärm
quelle
2

In vielen Linux-Versionen finden Sie complier.h in / usr / linux /. Sie können es einfach zur Verwendung hinzufügen. Und eine andere Meinung, unwahrscheinlich (), ist eher nützlich 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, Sie können die Antwort finden.

Finaldie
quelle
1

Sie sind Hinweise für den Compiler, 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 ignoriert der Verzweigungsprädiktor auf dem Prozessor diese heutzutage.

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

Cody Brocious
quelle
10
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 das Abrollen von Schleifen vermieden werden.
Alex seltsam
1

Dies sind GCC-Funktionen, mit denen der Programmierer dem Compiler einen Hinweis darauf geben kann, welche Verzweigungsbedingung in einem bestimmten Ausdruck am wahrscheinlichsten ist. Auf diese Weise kann der Compiler die Verzweigungsbefehle so erstellen, dass im häufigsten Fall die geringste Anzahl von Befehlen ausgeführt wird.

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

dcgibbons
quelle