webentwicklung-frage-antwort-db.com.de

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

Gibt es für die Intel-Architekturen eine Möglichkeit, den GCC-Compiler anzuweisen, Code zu generieren, der die Verzweigungsvorhersage immer auf eine bestimmte Weise in meinem Code 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, dass ich schnell laufen möchte und mich nicht um die Verlangsamung kümmere, 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 den Befehl stößt, wobei die gesamte nachfolgende Verzweigungsvorhersage normal funktioniert?

109
WilliamKF

Die richtige Methode zum Definieren von wahrscheinlichen/unwahrscheinlichen Makros in C++ 11 lautet wie folgt:

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

Wenn diese Makros folgendermaßen definiert wurden:

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

Das kann die Bedeutung von if -Anweisungen ä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, unterbricht die Definition von LIKELY, das !! Als Besetzung für bool verwendet, die Semantik von if.

Der Punkt hier ist nicht, dass operator int() und operator bool() in Beziehung stehen sollten. Welches ist eine gute Praxis.

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

21

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

Dabei ist exp die verwendete Bedingung und c der erwartete Wert. Zum Beispiel, wenn Sie möchten

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

  1. Dies ist kein Standard
  2. Ein Compiler/CPU-Verzweigungs-Prädiktor ist wahrscheinlich erfahrener als Sie, wenn es darum geht, solche Dinge zu entscheiden. Dies könnte eine vorzeitige Mikrooptimierung sein.
80
Jack

gcc hat long __builtin_expect (long exp, long c) ( Schwerpunkt meiner):

Sie können __builtin_expect verwenden, um dem Compiler Informationen zur Verzweigungsvorhersage bereitzustellen. Im Allgemeinen sollten Sie das tatsächliche Profilfeedback für dieses verwenden (-fprofile-arcs), da Programmierer bekanntermaßen schlecht vorhersagen können, wie ihre Programme tatsächlich funktionieren . . Es gibt jedoch Anwendungen, in denen es schwierig ist, diese Daten zu sammeln.

Der Rückgabewert ist der Wert von exp, der ein ganzzahliger 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 keinen Aufruf von foo erwarten, da wir erwarten, dass x Null ist. Da Sie sich bei exp auf ganzzahlige Ausdrücke beschränken, sollten Sie Konstruktionen wie

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

beim Testen von Zeiger- oder Gleitkommawerten.

Wie in der Dokumentation vermerkt, sollten Sie lieber tatsächliches Profilfeedback verwenden und dieser Artikel zeigt ein praktisches Beispiel dafür und wie es in diesem Fall zumindest zu einer Verbesserung gegenüber der Verwendung von __builtin_expect Führt. Siehe auch Wie verwende ich profilgeführte Optimierungen in g ++? .

Wir können auch einen Linux-Kernel-Neueinsteiger-Artikel über die Kernel-Makros "probably" () und "unwahrscheinlich" () finden, die diese Funktion verwenden:

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

Beachten Sie den im Makro verwendeten !!. Die Erklärung hierfür finden Sie in Warum wird !! (Bedingung) anstelle von (Bedingung) verwendet? .

Nur weil diese Technik im Linux-Kernel verwendet wird, ist es nicht immer sinnvoll, sie zu verwenden. Aus dieser Frage, die ich kürzlich beantwortet habe, können wir ersehen, dass nterschied zwischen der Funktionsleistung beim Übergeben von Parametern als Kompilierzeitkonstante oder Variable 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 relevant.

Beachten Sie, dass Builtins nicht portierbar sind clang unterstützt auch __builtin_expect .

Auch auf einigen Architekturen kann es keinen Unterschied machen .

42
Shafik Yaghmour

Nein, gibt es nicht. (Zumindest auf modernen x86-Prozessoren.)

__builtin_expect, das in anderen Antworten erwähnt wird, beeinflusst die Art und Weise, wie gcc den Assembly-Code anordnet. Beeinflusst nicht direkt den Branch Predictor der CPU. Natürlich gibt es indirekte Auswirkungen auf die Branch Prediction durch Neuordnung des Codes. Auf modernen x86-Prozessoren gibt es jedoch keine Anweisung, die der CPU mitteilt, dass "angenommen wird, dass dieser Zweig belegt ist/nicht belegt ist".

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

Deutlich sein, __builtin_expect und/oder die Verwendung von -fprofile-arcs can Verbessern Sie die Leistung Ihres Codes, indem Sie dem Zweigprädiktor über das Codelayout Hinweise geben (siehe Leistungsoptimierung von x86-64-Assembly - Ausrichtung und Zweigprädiktion =) und auch das Cache-Verhalten verbessern, indem "unwahrscheinlicher" Code von "wahrscheinlichem" Code ferngehalten wird.

38
Artelius

Wie die anderen Antworten alle ausreichend nahegelegt haben, können Sie __builtin_expect, um dem Compiler einen Hinweis zum Anordnen des Assembly-Codes zu geben. Wie in den offiziellen Dokumenten angegeben, 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, die tatsächlichen Profildaten zu verwenden, um Ihren Code zu optimieren, anstatt zu raten.

Ähnlich, aber noch nicht erwähnt, ist eine GCC-spezifische Methode, mit der der Compiler gezwungen wird, Code auf einem "kalten" Pfad zu generieren. Dies beinhaltet die Verwendung der Attribute noinline und cold, die genau das tun, wie sie klingen. Diese Attribute können nur auf Funktionen angewendet werden. In 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 zutrifft - Test raten Sie nicht -, halte ich es für allgemeiner nützlich als __builtin_expect. Kaum eine Generation des x86-Prozessors verwendet Hinweise zur Verzweigungsvorhersage ( Referenz ). Sie können also ohnehin nur die Reihenfolge des Assembly-Codes beeinflussen. Da Sie wissen, was Fehlerbehandlung oder "Randfall" -Code ist, können Sie mit dieser Annotation sicherstellen, dass der Compiler niemals eine Verzweigung dorthin vorhersagt und diese bei der Größenoptimierung vom "heißen" Code entfernt.

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, GCC ignoriert dies automatisch zugunsten von Profil-Feedback, 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

15
Cody Gray

__builtin_expect kann verwendet werden, um dem Compiler mitzuteilen, in welche Richtung Sie eine Verzweigung erwarten. Dies kann Einfluss darauf haben, wie der Code generiert wird. Typische Prozessoren führen den 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 ausgeführt als die normale Sequenz, bei der jede if-Anweisung um den bedingten Code herum verzweigt und drei Zweige ausführt.

Neuere x86-Prozessoren verfügen über Anweisungen für Zweige, von denen erwartet wird, dass sie belegt werden, oder für Zweige, von denen erwartet wird, dass sie nicht belegt werden (es gibt ein Anweisungspräfix, bei dem Einzelheiten nicht bekannt sind). Ich bin mir nicht sicher, ob der Prozessor das verwendet. Es ist nicht sehr nützlich, da die Verzweigungsvorhersage dies in Ordnung bringt. Ich glaube also nicht, dass Sie den Zweig tatsächlich beeinflussen können Vorhersage.

3
gnasher729

In Bezug auf das OP gibt es keine Möglichkeit, dem Prozessor mitzuteilen, dass der Zweig immer belegt ist oder nicht. Was Sie haben, ist __builtin_expect, das tut, was andere sagen, dass es tut. Darüber hinaus denke ich, dass Sie dem Prozessor nicht mitteilen möchten, ob der Zweig belegt ist oder nicht immer. Heutige Prozessoren wie die Intel-Architektur können recht komplexe Muster erkennen und sich effektiv anpassen.

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

Ein konkretes Beispiel: Exception Management Code. Per Definition tritt der Verwaltungscode in Ausnahmefällen auf, aber möglicherweise ist maximale Leistung erwünscht (möglicherweise liegt ein kritischer Fehler vor, 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, sammelt der Prozessor möglicherweise Statistiken, verliert sie jedoch, da die gleiche Klassifizierung nicht früh genug erfolgt und die Vorhersage-Ressourcen dem kürzlich aufgerufenen Code gewidmet sind. Ich wünschte, es gäbe ein Primitiv, das dem Prozessor mitteilt, "bitte widme diesem Code keine Vorhersageressourcen", wie du manchmal sagen kannst, "Cache dies nicht".

0
TheCppZoo