Wie funktionieren die wahrscheinlich/unwahrscheinlich-Makros im Linux-Kernel und was ist ihr Nutzen?

Question

Ich habe mich durch einige Teile des Linux-Kernels gewühlt und dabei Aufrufe wie diesen gefunden:

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

o

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 der Optimierung dienen, aber wie funktionieren sie? Und wie viel Leistungs-/Größenverlust kann man von ihrer Verwendung erwarten? Und ist es die Mühe wert (und verlieren die Portabilität wahrscheinlich) zumindest in Engpass-Code (in Userspace, natürlich).

Answer 1

Sie sind ein Hinweis an den Compiler, Anweisungen auszugeben, die dazu führen, dass die Verzweigungsvorhersage die "wahrscheinliche" Seite einer Sprunganweisung bevorzugt. Dies kann ein großer Gewinn sein, denn wenn die Vorhersage korrekt ist, bedeutet dies, dass der Sprungbefehl im Grunde kostenlos ist und keine Zyklen benötigt. Ist die Vorhersage hingegen falsch, bedeutet dies, dass die Pipeline des Prozessors geleert werden muss, was mehrere Zyklen kosten kann. Solange die Vorhersage die meiste Zeit über richtig ist, ist dies in der Regel gut für die Leistung.

Wie bei allen derartigen Leistungsoptimierungen sollten Sie dies nur nach einer ausführlichen Profilerstellung tun, um sicherzustellen, dass der Code wirklich in einem Engpass steckt, und angesichts der Mikro-Natur wahrscheinlich in einer engen Schleife ausgeführt wird. Im Allgemeinen sind die Linux-Entwickler ziemlich erfahren, so dass ich mir vorstellen kann, dass sie das getan haben. Sie kümmern sich nicht wirklich um die Portabilität, da sie nur gcc verwenden und eine genaue Vorstellung von der Assemblerdatei haben, die sie erzeugen wollen.

Answer 2

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 mit GCC 4.8.2 x86_64 Linux:

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

Salida:

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 Reihenfolge der Befehle im Speicher blieb unverändert: zuerst die printf und dann puts et le retq Rückkehr.

Avec __builtin_expect

Jetzt ersetzen if (i) mit:

if (__builtin_expect(i, 0))

und wir erhalten:

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>

En printf (zusammengestellt zu __printf_chk ) wurde ganz ans Ende der Funktion verschoben, nach puts und die Rückkehr zur Verbesserung der Zweigvorhersage, wie in anderen Antworten erwähnt.

Es ist also im Grunde das Gleiche 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 mit -O0 .

Aber viel Glück beim Schreiben eines Beispiels, das schneller läuft mit __builtin_expect als ohne, CPUs sind heutzutage wirklich intelligent . Meine naiven Versuche sind hier .

C++20 [[likely]] y [[unlikely]]

C++20 hat diese C++-Build-Ins standardisiert: Verwendung des C++20-Attributs wahrscheinlich/unwahrscheinlich in der if-else-Anweisung Sie werden wahrscheinlich (ein Wortspiel!) das Gleiche tun.

Answer 3

Dies sind Makros, die dem Compiler Hinweise geben, in welche Richtung eine Verzweigung gehen kann. Die Makros erweitern sich zu GCC-spezifischen Erweiterungen, wenn sie 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 er diesen Code so umstrukturieren, dass er in etwa so aussieht:

if (!x) {
  return x;
}

dosomething();
return x;

Dies hat den Vorteil, dass der Prozessor beim ersten Mal, wenn er eine Verzweigung vornimmt, einen erheblichen Mehraufwand hat, da er den Code möglicherweise spekulativ weiter vorne geladen und ausgeführt hat. Wenn er feststellt, dass er die Verzweigung ausführen wird, muss er diese ungültig machen und mit dem Verzweigungsziel beginnen.

Die meisten modernen Prozessoren verfügen heute über eine Art von Verzweigungsvorhersage, die aber nur hilft, wenn man die Verzweigung schon einmal durchlaufen hat und sie sich noch im Cache für die Verzweigungsvorhersage befindet.

Es gibt eine Reihe anderer Strategien, die der Compiler und der Prozessor in diesen Szenarien anwenden können. Weitere Einzelheiten über die Funktionsweise von Verzweigungsvorhersagen finden Sie bei Wikipedia: http://en.wikipedia.org/wiki/Branch_predictor

Answer 4

Sie veranlassen den Compiler, die entsprechenden Verzweigungshinweise auszugeben, sofern die Hardware sie unterstützt. Dies bedeutet in der Regel nur, dass ein paar Bits im Befehls-Opcode verändert werden, so dass sich die Codegröße nicht ändert. Die CPU beginnt mit dem Abrufen von Befehlen von der vorhergesagten Stelle und spült die Pipeline und beginnt von vorne, wenn sich herausstellt, dass der Hinweis falsch ist, wenn die Verzweigung erreicht wird; in dem Fall, in dem der Hinweis korrekt ist, wird die Verzweigung dadurch viel schneller - wie viel schneller genau, hängt von der Hardware ab; und wie sehr dies die Leistung des Codes beeinflusst, hängt davon ab, wie viel Prozent der Zeit der Hinweis korrekt ist.

Auf einer PowerPC-CPU kann beispielsweise eine Verzweigung ohne Hint 16 Zyklen dauern, eine mit korrektem Hint 8 und eine mit falschem Hint 24. In innersten Schleifen kann gutes Hinting einen enormen Unterschied ausmachen.

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

Answer 5

long __builtin_expect(long EXP, long C);

Dieses Konstrukt teilt dem Compiler mit, dass der Ausdruck EXP höchstwahrscheinlich den Wert C haben wird. Der Rückgabewert ist EXP. __Bau_erwarten ist für die Verwendung in einem bedingten Ausdruck. In fast allen Fällen wird er im Zusammenhang mit booleschen Ausdrücken verwendet, in denen es viel 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 verwendet werden wie in

if (likely(a > 1))

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