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

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?

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

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

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 .

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.

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 .

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

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

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