Gibt es einen Compiler-Hinweis für GCC, um die Verzweigungsvorhersage zu zwingen, immer einen bestimmten Weg zu gehen?

118

Gibt es für die Intel-Architekturen eine Möglichkeit, den GCC-Compiler anzuweisen, Code zu generieren, der die Verzweigungsvorhersage in meinem Code immer auf eine bestimmte Weise erzwingt? Unterstützt die Intel-Hardware dies überhaupt? Was ist mit anderen Compilern oder Hardware?

Ich würde dies in C ++ - Code verwenden, wo ich den Fall kenne, in dem ich schnell laufen möchte, und mich nicht um die Verlangsamung kümmern, wenn der andere Zweig genommen werden muss, selbst wenn er kürzlich diesen Zweig genommen hat.

for (;;) {
  if (normal) { // How to tell compiler to always branch predict true value?
    doSomethingNormal();
  } else {
    exceptionalCase();
  }
}

Kann der Hinweis als Folgefrage für Evdzhan Mustafa nur einen Hinweis angeben, wenn der Prozessor zum ersten Mal auf die Anweisung trifft, wobei alle nachfolgenden Verzweigungsvorhersagen normal funktionieren?

WilliamKF
quelle
könnte auch eine Ausnahme auslösen, wenn etwas abnormal wird (was vom Compiler unabhängig ist)
Shep

Antworten:

9

Ab C ++ 20 sollten die wahrscheinlichen und unwahrscheinlichen Attribute standardisiert sein und werden bereits in g ++ 9 unterstützt . Wie hier beschrieben , können Sie also schreiben

if (a>b) {
  /* code you expect to run often */
  [[likely]] /* last statement */
}

zB im folgenden Code wird der else-Block dank des [[unlikely]]im if-Block eingefügt

int oftendone( int a, int b );
int rarelydone( int a, int b );
int finaltrafo( int );

int divides( int number, int prime ) {
  int almostreturnvalue;
  if ( ( number % prime ) == 0 ) {
    auto k                         = rarelydone( number, prime );
    auto l                         = rarelydone( number, k );
    [[unlikely]] almostreturnvalue = rarelydone( k, l );
  } else {
    auto a            = oftendone( number, prime );
    almostreturnvalue = oftendone( a, a );
  }
  return finaltrafo( almostreturnvalue );
}

Godbolt-Link zum Vergleich der Anwesenheit / Abwesenheit des Attributs

pseyfert
quelle
Warum [[unlikely]]in ifvs [[likely]]in der verwenden else?
WilliamKF
Kein Grund, bin gerade in dieser Konstellation gelandet, nachdem ich versucht habe, wohin das Attribut gehen muss.
pseyfert
Ziemlich cool. Schade, dass die Methode nicht auf ältere C ++ - Versionen anwendbar ist.
Maxim Egorushkin
Fantastischer Godbolt Link
Lewis Kelsey
87

GCC unterstützt die Funktion __builtin_expect(long exp, long c), um diese Art von Funktion bereitzustellen. Sie können die Dokumentation hier überprüfen .

Wo expwird die Bedingung verwendet und cist der erwartete Wert. Zum Beispiel in Ihrem Fall möchten Sie

if (__builtin_expect(normal, 1))

Aufgrund der umständlichen Syntax wird dies normalerweise verwendet, indem zwei benutzerdefinierte Makros wie definiert werden

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

nur um die Aufgabe zu erleichtern.

Beachten Sie, dass:

  1. Dies ist nicht Standard
  2. Ein Compiler / CPU-Verzweigungsprädiktor ist wahrscheinlich geschickter als Sie, wenn es darum geht, solche Dinge zu entscheiden, sodass dies eine vorzeitige Mikrooptimierung sein könnte
Jack
quelle
3
Gibt es einen Grund, warum Sie ein Makro und keine constexprFunktion anzeigen?
Columbo
22
@Columbo: Ich glaube nicht, dass eine constexprFunktion dieses Makro ersetzen kann . Es muss in der ifAussage direkt sein, glaube ich. Der gleiche Grund assertkönnte niemals eine constexprFunktion sein.
Mooing Duck
1
@MooingDuck Ich stimme zu, obwohl es weitere Gründe für die Behauptung gibt .
Shafik Yaghmour
7
@Columbo Ein Grund für die Verwendung eines Makros wäre, dass dies eine der wenigen Stellen in C oder C ++ ist, an denen ein Makro semantisch korrekter ist als eine Funktion. Die Funktion scheint nur aufgrund der Optimierung zu funktionieren (es handelt sich um eine Optimierung: constexprspricht nur über Wertesemantik, nicht über das Inlining implementierungsspezifischer Assemblys); Die einfache Interpretation (kein Inline) des Codes ist bedeutungslos. Es gibt überhaupt keinen Grund, eine Funktion dafür zu verwenden.
Leushenko
2
@Leushenko Betrachten Sie, dass es __builtin_expectsich um einen Optimierungshinweis handelt. Daher ist es nicht überzeugend zu argumentieren, dass eine Methode, die ihre Verwendung vereinfacht, von der Optimierung abhängt. Außerdem habe ich den constexprBezeichner nicht hinzugefügt , damit er überhaupt funktioniert, sondern damit er in konstanten Ausdrücken funktioniert. Und ja, es gibt Gründe, eine Funktion zu verwenden. Zum Beispiel möchte ich nicht meinen gesamten Namespace mit einem niedlichen kleinen Namen wie verschmutzen likely. Ich müsste zB verwenden LIKELY, um zu betonen, dass es sich um ein Makro handelt, und Kollisionen vermeiden, aber das ist einfach hässlich.
Columbo
46

gcc hat long __builtin_expect (long exp, long c) ( Hervorhebung von mir ):

Sie können __builtin_expect verwenden, um dem Compiler Informationen zur Verzweigungsvorhersage bereitzustellen. Im Allgemeinen sollten Sie es vorziehen, dafü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 erwartet wird, dass exp == c. Beispielsweise:

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

gibt an, dass wir nicht erwarten, foo aufzurufen, da wir erwarten, dass x Null ist. Da Sie für exp auf integrale Ausdrücke beschränkt sind, sollten Sie Konstruktionen wie verwenden

if (__builtin_expect (ptr != NULL, 1))
   foo (*ptr);

beim Testen von Zeiger- oder Gleitkommawerten.

Wie in der Dokumentation erwähnt, sollten Sie lieber das tatsächliche Profilfeedback verwenden. Dieser Artikel zeigt ein praktisches Beispiel dafür und wie es in ihrem Fall zumindest zu einer Verbesserung gegenüber der Verwendung kommt __builtin_expect. Siehe auch Verwenden von profilgesteuerten Optimierungen in g ++. .

Wir können auch einen Artikel über Linux-Kernel-Neulinge zu den Kernal-Makros wahrscheinlich () und unwahrscheinlich () finden, die diese Funktion verwenden:

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

Beachten Sie die !!im Makro verwendeten. Die Erklärung hierfür finden Sie unter Warum verwenden Sie !! (Bedingung) anstelle von (Bedingung)? .

Nur weil diese Technik im Linux-Kernel verwendet wird, bedeutet dies nicht, dass es immer sinnvoll ist, sie zu verwenden. Aus dieser Frage können wir ersehen, dass ich kürzlich den Unterschied zwischen der Funktionsleistung beim Übergeben von Parametern als Kompilierungszeitkonstante oder -variable beantwortet habe , dass viele handgerollte Optimierungstechniken im allgemeinen Fall nicht funktionieren. Wir müssen den Code sorgfältig profilieren, um zu verstehen, ob eine Technik effektiv ist. Viele alte Techniken sind bei modernen Compiler-Optimierungen möglicherweise nicht einmal relevant.

Hinweis: Obwohl Builtins nicht portabel sind, unterstützt Clang auch __builtin_expect .

Auch bei einigen Architekturen macht es möglicherweise keinen Unterschied .

Shafik Yaghmour
quelle
Was für den Linux-Kernel gut genug ist, reicht für C ++ 11 nicht aus.
Maxim Egorushkin
@ MaximEgorushkin Hinweis, ich empfehle seine Verwendung nicht wirklich, in der Tat verwendet die von mir zitierte gcc-Dokumentation, die mein erstes Zitat ist, nicht einmal diese Technik. Ich würde sagen, der Hauptschwerpunkt meiner Antwort besteht darin, Alternativen sorgfältig zu prüfen, bevor ich diesen Weg beschreite.
Shafik Yaghmour
44

Nein, da ist kein. (Zumindest auf modernen x86-Prozessoren.)

__builtin_expectDie in anderen Antworten erwähnten Faktoren beeinflussen die Art und Weise, wie gcc den Assembler-Code anordnet. Es hat keinen direkten Einfluss auf den Verzweigungsprädiktor der CPU. Natürlich wird es indirekte Auswirkungen auf die Verzweigungsvorhersage geben, die durch die Neuordnung des Codes verursacht werden. Auf modernen x86-Prozessoren gibt es jedoch keine Anweisung, die der CPU mitteilt, dass "angenommen wird, dass dieser Zweig verwendet wird / nicht".

Weitere Informationen finden Sie in dieser Frage: Intel x86 0x2E / 0x3E Präfix Branch Prediction wird tatsächlich verwendet?

Um klar zu sein __builtin_expectund / oder die Verwendung von -fprofile-arcs kann die Leistung Ihres Codes verbessern, indem Sie dem Verzweigungsprädiktor durch das Codelayout Hinweise geben (siehe Leistungsoptimierungen der x86-64-Assembly - Ausrichtung und Verzweigungsvorhersage ) und das Cache-Verhalten verbessern indem "unwahrscheinlicher" Code von "wahrscheinlichem" Code ferngehalten wird.

Artelius
quelle
9
Das ist falsch. Bei allen modernen Versionen von x86 besteht der Standardvorhersagealgorithmus darin, vorherzusagen, dass keine Vorwärtsverzweigungen und keine Rückwärtsverzweigungen verwendet werden (siehe software.intel.com/en-us/articles/… ). Also von Ihrem Code neu anordnen Sie können effektiv einen Hinweis auf die CPU geben. Genau das macht GCC, wenn Sie es verwenden __builtin_expect.
Nemo
6
@Nemo, hast du nach dem ersten Satz meiner Antwort gelesen? Alles, was Sie gesagt haben, wird durch meine Antwort oder die angegebenen Links abgedeckt. Die Frage, ob Sie "die Verzweigungsvorhersage zwingen können, immer einen bestimmten Weg zu gehen", auf den die Antwort "Nein" lautet, und ich hatte nicht das Gefühl, dass andere Antworten diesbezüglich klar genug waren.
Artelius
4
OK, ich hätte genauer lesen sollen. Es scheint mir, dass diese Antwort technisch korrekt, aber nutzlos ist, da der Fragesteller offensichtlich sucht __builtin_expect. Das sollte also nur ein Kommentar sein. Aber es ist nicht falsch, also habe ich meine Ablehnung entfernt.
Nemo
IMO ist es nicht nutzlos; Dies ist eine nützliche Erläuterung der tatsächlichen Funktionsweise von CPUs und Compilern, die für die Leistungsanalyse mit / ohne diese Optionen relevant sein kann. Beispielsweise können Sie normalerweise nicht __builtin_expecttrivial einen Testfall erstellen, mit dem Sie messen können perf stat, der eine sehr hohe Rate von Verzweigungsfehlvorhersagen aufweist. Es wirkt sich nur auf das Zweiglayout aus . Und übrigens, Intel verwendet seit Sandybridge oder zumindest Haswell nicht viel / überhaupt keine statische Vorhersage; Es gibt immer eine Vorhersage in der BHT, ob es sich um einen veralteten Alias ​​handelt oder nicht. xania.org/201602/bpu-part-two
Peter Cordes
24

Der richtige Weg, um wahrscheinliche / unwahrscheinliche Makros in C ++ 11 zu definieren, ist folgender:

#define LIKELY(condition) __builtin_expect(static_cast<bool>(condition), 1)
#define UNLIKELY(condition) __builtin_expect(static_cast<bool>(condition), 0)

Diese Methode ist im Gegensatz zu allen C ++ - Versionen kompatibel, basiert [[likely]]jedoch auf einer nicht standardmäßigen Erweiterung __builtin_expect.


Wenn diese Makros folgendermaßen definiert wurden:

#define LIKELY(condition) __builtin_expect(!!(condition), 1)

Dies kann die Bedeutung von ifAnweisungen ändern und den Code beschädigen. Betrachten Sie den folgenden Code:

#include <iostream>

struct A
{
    explicit operator bool() const { return true; }
    operator int() const { return 0; }
};

#define LIKELY(condition) __builtin_expect((condition), 1)

int main() {
    A a;
    if(a)
        std::cout << "if(a) is true\n";
    if(LIKELY(a))
        std::cout << "if(LIKELY(a)) is true\n";
    else
        std::cout << "if(LIKELY(a)) is false\n";
}

Und seine Ausgabe:

if(a) is true
if(LIKELY(a)) is false

Wie Sie sehen können, bricht die Definition von LIKELY !!als Besetzung, um booldie Semantik von zu brechen if.

Der Punkt hier ist nicht das operator int()und operator bool()sollte verwandt sein. Welches ist eine gute Praxis.

Vielmehr verliert die Verwendung !!(x)anstelle von static_cast<bool>(x)den Kontext für kontextbezogene C ++ 11-Konvertierungen .

Maxim Egorushkin
quelle
Beachten Sie, dass kontextbezogene Konvertierungen 2012 über einen Fehler eingegangen sind und selbst Ende 2014 noch Abweichungen bei der Implementierung aufgetreten sind. Eigentlich sieht es so aus, als ob der Fall, mit dem ich verlinkt habe, für gcc immer noch nicht funktioniert.
Shafik Yaghmour
@ShafikYaghmour Das ist eine interessante Beobachtung in Bezug auf die kontextbezogene Konvertierung switch, danke. Die hier involvierte kontextbezogene Konvertierung ist partucluar to type boolund die fünf dort aufgeführten spezifischen Kontexte , die keinen switchKontext enthalten.
Maxim Egorushkin
Dies betrifft nur C ++, oder? Es gibt also keinen Grund, vorhandene C-Projekte zu ändern (_Bool)(condition), da C keine Operatorüberladung aufweist.
Peter Cordes
2
In Ihrem Beispiel haben Sie nur verwendet (condition), nicht !!(condition). Beide sind truenach dem Ändern (getestet mit g ++ 7.1). Können Sie ein Beispiel !!erstellen, das das Problem demonstriert, über das Sie beim Booleschen Vorgang sprechen?
Peter Cordes
3
Wie Peter Cordes betonte, sagen Sie "Wenn diese Makros wie folgt definiert sind:" und zeigen dann ein Makro mit '!!' "," kann die Bedeutung von if-Anweisungen ändern und den Code brechen. Betrachten Sie den folgenden Code: " ... und dann zeigen Sie Code, der nicht '!!' verwendet. überhaupt - was schon vor C ++ 11 bekanntermaßen kaputt war. Bitte ändern Sie die Antwort, um ein Beispiel zu zeigen, in dem das angegebene Makro (mit !!) schief geht.
Carlo Wood
18

Wie die anderen Antworten alle angemessen vorgeschlagen haben, können Sie __builtin_expectdem Compiler einen Hinweis geben, wie der Assemblycode angeordnet werden soll. Wie die offiziellen Dokumente hervorheben , ist der in Ihr Gehirn eingebaute Assembler in den meisten Fällen nicht so gut wie der vom GCC-Team erstellte. Es ist immer am besten, tatsächliche Profildaten zu verwenden, um Ihren Code zu optimieren, anstatt zu raten.

In ähnlicher Weise, aber noch nicht erwähnt, ist eine GCC-spezifische Methode, um den Compiler zu zwingen, Code auf einem "kalten" Pfad zu generieren. Dies beinhaltet die Verwendung der Attribute noinlineund cold, die genau das tun, wie sie klingen. Diese Attribute können nur auf Funktionen angewendet werden. Mit C ++ 11 können Sie jedoch Inline-Lambda-Funktionen deklarieren, und diese beiden Attribute können auch auf Lambda-Funktionen angewendet werden.

Obwohl dies immer noch in die allgemeine Kategorie einer Mikrooptimierung fällt und daher die Standardempfehlung gilt - Test nicht erraten -, halte ich es für allgemeiner nützlich als __builtin_expect. Kaum eine Generation des x86-Prozessors verwendet Hinweise zur Verzweigungsvorhersage ( Referenz ). Das einzige, was Sie ohnehin beeinflussen können, ist die Reihenfolge des Assembler-Codes. Da Sie wissen, was Fehlerbehandlungs- oder "Edge-Case" -Code ist, können Sie diese Anmerkung verwenden, um sicherzustellen, dass der Compiler niemals einen Zweig dazu vorhersagt und ihn bei der Größenoptimierung vom "heißen" Code weg verknüpft.

Beispielnutzung:

void FooTheBar(void* pFoo)
{
    if (pFoo == nullptr)
    {
        // Oh no! A null pointer is an error, but maybe this is a public-facing
        // function, so we have to be prepared for anything. Yet, we don't want
        // the error-handling code to fill up the instruction cache, so we will
        // force it out-of-line and onto a "cold" path.
        [&]() __attribute__((noinline,cold)) {
            HandleError(...);
        }();
    }

    // Do normal stuff
    
}

Noch besser ist, dass GCC dies automatisch zugunsten von Profil-Feedback ignoriert, wenn es verfügbar ist (z. B. beim Kompilieren mit -fprofile-use).

Die offizielle Dokumentation finden Sie hier: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes

Cody Grey
quelle
2
Die Präfixe für Verzweigungsvorhersagehinweise werden ignoriert, da sie nicht benötigt werden. Sie können genau den gleichen Effekt erzielen, indem Sie Ihren Code neu anordnen. (Der Standardalgorithmus für die Verzweigungsvorhersage besteht darin, zu erraten, dass Rückwärtsverzweigungen verwendet werden und Vorwärtsverzweigungen nicht.) Sie können der CPU also tatsächlich einen Hinweis geben, und dies ist der __builtin_expectFall. Es ist überhaupt nicht nutzlos. Sie haben Recht, dass das coldAttribut auch nützlich ist, aber Sie unterschätzen den Nutzen von __builtin_expectIch denke.
Nemo
Moderne Intel-CPUs verwenden keine statische Verzweigungsvorhersage. Der von Ihnen beschriebene Algorithmus @Nemo, bei dem Rückwärtsverzweigungen als genommen und Vorwärtsverzweigungen als nicht genommen vorhergesagt werden, wurde in früheren Prozessoren und über den Pentium M oder so verwendet, aber moderne Designs raten im Grunde genommen nur zufällig und indizieren in ihren Zweig Tabellen, in denen erwartet wird , dass Informationen zu diesem Zweig gefunden werden und welche Informationen auch immer vorhanden sind (auch wenn es sich im Wesentlichen um Müll handelt). Hinweise zur Verzweigungsvorhersage wären theoretisch nützlich, in der Praxis jedoch möglicherweise nicht, weshalb Intel sie entfernt hat.
Cody Gray
Um klar zu sein, ist die Implementierung der Verzweigungsvorhersage äußerst kompliziert, und Platzbeschränkungen in Kommentaren zwangen mich zu einer starken Vereinfachung. Dies wäre wirklich eine vollständige Antwort für sich. In modernen Mikroarchitekturen wie Haswell gibt es möglicherweise noch Spuren statischer Verzweigungsvorhersagen, aber es ist bei weitem nicht mehr so ​​einfach wie früher.
Cody Gray
Haben Sie eine Referenz für "Moderne Intel-CPUs verwenden keine statische Verzweigungsvorhersage"? Intels eigener Artikel ( software.intel.com/en-us/articles/… ) sagt etwas anderes ... Aber das ist von 2011
Nemo
Ich habe keine offizielle Referenz, @Nemo. Intel ist äußerst gespannt auf die in seinen Chips verwendeten Algorithmen zur Vorhersage von Verzweigungen und behandelt sie als Geschäftsgeheimnisse. Das meiste, was bekannt ist, wurde durch empirische Tests herausgefunden. Wie immer sind die Materialien von Agner Fog die besten Ressourcen, aber selbst er sagt: "Der Branchenprädiktor scheint im Haswell neu gestaltet worden zu sein, aber über seine Konstruktion ist nur sehr wenig bekannt." Ich kann mich nicht erinnern, wo ich die Benchmarks zum ersten Mal gesehen habe, die zeigen, dass statischer Blutdruck leider nicht mehr verwendet wurde.
Cody Gray
5

__builtin_expect kann verwendet werden, um dem Compiler mitzuteilen, in welche Richtung ein Zweig gehen soll. Dies kann Einfluss darauf haben, wie der Code generiert wird. Typische Prozessoren führen Code nacheinander schneller aus. Also wenn du schreibst

if (__builtin_expect (x == 0, 0)) ++count;
if (__builtin_expect (y == 0, 0)) ++count;
if (__builtin_expect (z == 0, 0)) ++count;

Der Compiler generiert Code wie

if (x == 0) goto if1;
back1: if (y == 0) goto if2;
back2: if (z == 0) goto if3;
back3: ;
...
if1: ++count; goto back1;
if2: ++count; goto back2;
if3: ++count; goto back3;

Wenn Ihr Hinweis korrekt ist, wird der Code ausgeführt, ohne dass tatsächlich Verzweigungen ausgeführt werden. Es wird schneller als die normale Sequenz ausgeführt, wobei jede if-Anweisung um den bedingten Code verzweigt und drei Verzweigungen ausführt.

Neuere x86-Prozessoren verfügen über Anweisungen für Zweige, von denen erwartet wird, dass sie genommen werden, oder für Zweige, von denen erwartet wird, dass sie nicht genommen werden (es gibt ein Befehlspräfix; die Details sind nicht sicher). Ich bin mir nicht sicher, ob der Prozessor das verwendet. Dies ist nicht sehr nützlich, da die Verzweigungsvorhersage dies problemlos handhaben kann. Also ich glaube nicht , dass Sie tatsächlich den Zweig beeinflussen können Vorhersage .

gnasher729
quelle
2

In Bezug auf das OP gibt es in GCC keine Möglichkeit, den Prozessor anzuweisen, immer anzunehmen, dass die Verzweigung genommen wird oder nicht. Was Sie haben, ist __builtin_expect, das tut, was andere sagen. Außerdem denke ich, dass Sie dem Prozessor nicht immer mitteilen möchten, ob der Zweig belegt ist oder nicht . Heutige Prozessoren wie die Intel-Architektur können ziemlich komplexe Muster erkennen und sich effektiv anpassen.

Es gibt jedoch Situationen, in denen Sie die Kontrolle darüber übernehmen möchten, ob standardmäßig eine Verzweigung angenommen wird oder nicht: Wenn Sie wissen, dass der Code in Bezug auf Verzweigungsstatistiken als "kalt" bezeichnet wird.

Ein konkretes Beispiel: Ausnahmeverwaltungscode. Per Definition tritt der Verwaltungscode in Ausnahmefällen auf, aber wenn er auftritt, ist möglicherweise maximale Leistung erwünscht (es kann ein kritischer Fehler vorliegen, der so schnell wie möglich behoben werden muss). Daher möchten Sie möglicherweise die Standardvorhersage steuern.

Ein weiteres Beispiel: Sie können Ihre Eingabe klassifizieren und in den Code springen, der das Ergebnis Ihrer Klassifizierung verarbeitet. Wenn es viele Klassifizierungen gibt, kann der Prozessor Statistiken sammeln, diese jedoch verlieren, da dieselbe Klassifizierung nicht früh genug erfolgt und die Vorhersageressourcen für kürzlich aufgerufenen Code verwendet werden. Ich wünschte, es gäbe ein Grundelement, das dem Prozessor mitteilt, "bitte widmen Sie diesem Code keine Vorhersageressourcen", wie Sie manchmal sagen können, "dies nicht zwischenspeichern".

TheCppZoo
quelle