Ein teurer Sprung mit GCC 5.4.0

Ich hatte eine Funktion, die so aussah (nur den wichtigen Teil zeigend):

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) && (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

So geschrieben, dauerte die Funktion auf meinem Computer ~ 34 ms. Nachdem Sie die Bedingung in Bool-Multiplikation geändert haben (damit der Code so aussieht):

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) * (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

Die Ausführungszeit verringerte sich auf ~ 19 ms.

Der verwendete Compiler war GCC 5.4.0 mit -O3 und nachdem ich den generierten asm-Code mit godbolt.org überprüft hatte, stellte ich fest, dass das erste Beispiel einen Sprung generiert, das zweite nicht. Ich habe mich für GCC 6.2.0 entschieden, das bei Verwendung des ersten Beispiels auch eine Sprunganweisung generiert, aber GCC 7 scheint keine mehr zu generieren.

Auf diese Weise herauszufinden, wie der Code beschleunigt werden kann, war ziemlich grausam und dauerte einige Zeit. Warum verhält sich der Compiler so? Ist es beabsichtigt und sollten die Programmierer darauf achten? Gibt es noch ähnliche Dinge?

BEARBEITEN: Link zu Godbolt https://godbolt.org/g/5lKPF3

Der logische AND-Operator ( &&) verwendet eine Kurzschlussauswertung, was bedeutet, dass der zweite Test nur durchgeführt wird, wenn der erste Vergleich als wahr ausgewertet wird. Dies ist oft genau die Semantik, die Sie benötigen. Betrachten Sie beispielsweise den folgenden Code:

if ((p != nullptr) && (p->first > 0))

Sie müssen sicherstellen, dass der Zeiger nicht null ist, bevor Sie ihn dereferenzieren. Wenn dies keine Kurzschlussbewertung wäre, hätten Sie ein undefiniertes Verhalten, da Sie einen Nullzeiger dereferenzieren würden.

Es ist auch möglich, dass die Kurzschlussbewertung einen Leistungsgewinn in Fällen ergibt, in denen die Bewertung der Bedingungen ein teurer Prozess ist. Beispielsweise:

if ((DoLengthyCheck1(p) && (DoLengthyCheck2(p))

Wenn dies DoLengthyCheck1fehlschlägt, macht es keinen Sinn, anzurufen DoLengthyCheck2.

In der resultierenden Binärdatei führt eine Kurzschlussoperation jedoch häufig zu zwei Zweigen, da dies für den Compiler der einfachste Weg ist, diese Semantik beizubehalten. (Aus diesem Grund kann die Kurzschlussbewertung auf der anderen Seite der Medaille manchmal das Optimierungspotenzial hemmen .) Sie können dies anhand des relevanten Teils des Objektcodes erkennen, der für Ihre ifAussage von GCC 5.4 generiert wurde :

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L5

    cmp     ax, 478           ; (l[i + shift] < 479)
    ja      .L5

    add     r8d, 1            ; nontopOverlap++

Sie sehen hier die beiden Vergleiche ( cmpAnweisungen) hier, gefolgt von einem separaten bedingten Sprung / Zweig ( jaoder Sprung, falls oben).

Es ist eine allgemeine Faustregel, dass Zweige langsam sind und daher in engen Schleifen vermieden werden sollten. Dies gilt für praktisch alle x86-Prozessoren aus dem bescheidenen 8088 (dessen langsame Abrufzeiten und extrem kleine Prefetch-Warteschlange [vergleichbar mit einem Befehls-Cache] in Kombination mit einem völligen Mangel an Verzweigungsvorhersage dazu führten, dass für genommene Verzweigungen der Cache entleert werden musste ) zu modernen Implementierungen (deren lange Pipelines falsch vorhergesagte Zweige ähnlich teuer machen). Beachten Sie die kleine Einschränkung, die ich dort hineingeschlichen habe. Moderne Prozessoren seit dem Pentium Pro verfügen über fortschrittliche Zweigvorhersage-Engines, mit denen die Kosten für Zweige minimiert werden sollen. Wenn die Richtung der Verzweigung richtig vorhergesagt werden kann, sind die Kosten minimal. Meistens funktioniert dies gut, aber wenn Sie in pathologische Fälle geraten, in denen der Zweigprädiktor nicht auf Ihrer Seite ist,Ihr Code kann extrem langsam werden . Hier befinden Sie sich vermutlich, da Sie sagen, dass Ihr Array unsortiert ist.

Sie sagen, dass Benchmarks bestätigt haben, dass das Ersetzen des &&durch einen *den Code spürbar schneller macht. Der Grund dafür ist offensichtlich, wenn wir den relevanten Teil des Objektcodes vergleichen:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    xor     r15d, r15d        ; (curr[i] < 479)
    cmp     r13w, 478
    setbe   r15b

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     ax, 478
    setbe   r14b

    imul    r14d, r15d        ; meld results of the two comparisons

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

Es ist etwas kontraintuitiv, dass dies schneller sein könnte, da hier mehr Anweisungen vorhanden sind, aber so funktioniert die Optimierung manchmal. Sie sehen, cmpdass hier dieselben Vergleiche ( ) durchgeführt werden, aber jetzt wird jedem ein xorund ein a vorangestellt setbe. Das XOR ist nur ein Standardtrick zum Löschen eines Registers. Dies setbeist ein x86-Befehl, der ein Bit basierend auf dem Wert eines Flags setzt und häufig zum Implementieren von verzweigungslosem Code verwendet wird. Hier setbeist die Umkehrung von ja. Es setzt sein Zielregister auf 1, wenn der Vergleich unter oder gleich war (da das Register vor Null gesetzt wurde, ist es ansonsten 0), während es javerzweigt ist, wenn der Vergleich über Null war. Sobald diese beiden Werte im r15bund erhalten wurdenr14bRegister werden sie mit multipliziert imul. Die Multiplikation war traditionell eine relativ langsame Operation, aber auf modernen Prozessoren ist sie verdammt schnell, und dies wird besonders schnell sein, da nur zwei Werte in Byte-Größe multipliziert werden.

Sie hätten die Multiplikation genauso gut durch den bitweisen AND-Operator ( &) ersetzen können , der keine Kurzschlussauswertung durchführt. Dies macht den Code viel klarer und ist ein Muster, das Compiler im Allgemeinen erkennen. Wenn Sie dies jedoch mit Ihrem Code tun und ihn mit GCC 5.4 kompilieren, wird weiterhin der erste Zweig ausgegeben:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L4

    cmp     ax, 478           ; (l[i + shift] < 479)
    setbe   r14b

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

Es gibt keinen technischen Grund, warum der Code auf diese Weise ausgegeben werden musste, aber aus irgendeinem Grund sagen die internen Heuristiken, dass dies schneller ist. Es wäre wahrscheinlich schneller, wenn der Verzweigungsprädiktor auf Ihrer Seite wäre, aber es wäre wahrscheinlich langsamer, wenn die Verzweigungsvorhersage häufiger fehlschlägt als erfolgreich.

Neuere Generationen des Compilers (und anderer Compiler wie Clang) kennen diese Regel und verwenden sie manchmal, um denselben Code zu generieren, den Sie durch Handoptimierung gesucht hätten. Ich sehe regelmäßig, wie Clang &&Ausdrücke in denselben Code übersetzt , der ausgegeben worden wäre, wenn ich ihn verwendet hätte &. Das Folgende ist die relevante Ausgabe von GCC 6.2 mit Ihrem Code unter Verwendung des normalen &&Operators:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L7

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r14b

    add     esi, r14d         ; nontopOverlap++

Beachten Sie, wie klug das ist! Es werden signierte Bedingungen ( jgund setle) im Gegensatz zu nicht signierten Bedingungen ( jaund setbe) verwendet, dies ist jedoch nicht wichtig. Sie können sehen, dass es immer noch das Vergleichen und Verzweigen für die erste Bedingung wie die ältere Version setCCausführt und dieselbe Anweisung verwendet, um verzweigungslosen Code für die zweite Bedingung zu generieren, aber es ist viel effizienter geworden, wie es das Inkrement ausführt . Anstatt einen zweiten redundanten Vergleich sbbdurchzuführen, um die Flags für eine Operation zu setzen, wird das Wissen, r14ddas entweder 1 oder 0 ist, verwendet, um diesen Wert einfach bedingungslos hinzuzufügen nontopOverlap. Wenn r14d0 ist, ist die Addition ein No-Op; Andernfalls wird 1 hinzugefügt, genau wie es vorgesehen ist.

GCC 6.2 tatsächlich produziert mehr effizienten Code , wenn Sie das Kurzschließen verwenden &&Operator als der bitweise &Operator:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L6

    cmp     eax, 478          ; (l[i + shift] < 479)
    setle   r14b

    cmp     r14b, 1           ; nontopOverlap++
    sbb     esi, -1

Der Zweig und die bedingte Menge sind noch vorhanden, aber jetzt kehrt sie zu der weniger cleveren Art des Inkrementierens zurück nontopOverlap. Dies ist eine wichtige Lektion, warum Sie vorsichtig sein sollten, wenn Sie versuchen, Ihren Compiler zu übertreffen!

Wenn Sie jedoch anhand von Benchmarks nachweisen können , dass der Verzweigungscode tatsächlich langsamer ist, kann es sich lohnen, Ihren Compiler zu überlisten. Sie müssen dies nur mit einer sorgfältigen Überprüfung der Demontage tun - und bereit sein, Ihre Entscheidungen neu zu bewerten, wenn Sie auf eine spätere Version des Compilers aktualisieren. Der Code, den Sie haben, könnte beispielsweise wie folgt umgeschrieben werden:

nontopOverlap += ((curr[i] < 479) & (l[i + shift] < 479));

Hier gibt es überhaupt keine ifAussage, und die überwiegende Mehrheit der Compiler wird niemals daran denken, dafür Verzweigungscode auszugeben. GCC ist keine Ausnahme; Alle Versionen erzeugen etwas Ähnliches wie das Folgende:

    movzx   r14d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r14d, 478         ; (curr[i] < 479)
    setle   r15b

    xor     r13d, r13d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r13b

    and     r13d, r15d        ; meld results of the two comparisons
    add     esi, r13d         ; nontopOverlap++

Wenn Sie den vorherigen Beispielen gefolgt sind, sollte Ihnen dies sehr vertraut vorkommen. Beide Vergleiche werden verzweigt durchgeführt, die Zwischenergebnisse werden andzusammen bearbeitet , und dann wird dieses Ergebnis (das entweder 0 oder 1 sein wird) addbearbeitet nontopOverlap. Wenn Sie verzweigungslosen Code wünschen, wird dies praktisch sicherstellen, dass Sie ihn erhalten.

GCC 7 ist noch schlauer geworden. Es generiert jetzt praktisch identischen Code (mit Ausnahme einer geringfügigen Neuanordnung von Anweisungen) für den obigen Trick wie den ursprünglichen Code. Die Antwort auf Ihre Frage: "Warum verhält sich der Compiler so?" liegt wahrscheinlich daran, dass sie nicht perfekt sind! Sie versuchen, mithilfe von Heuristiken den bestmöglichen Code zu generieren, treffen jedoch nicht immer die besten Entscheidungen. Aber zumindest können sie mit der Zeit schlauer werden!

Eine Möglichkeit, diese Situation zu betrachten, besteht darin, dass der Verzweigungscode die bessere Best-Case- Leistung aufweist. Wenn die Verzweigungsvorhersage erfolgreich ist, führt das Überspringen unnötiger Vorgänge zu einer etwas schnelleren Laufzeit. Verzweigungsloser Code weist jedoch die bessere Worst-Case- Leistung auf. Wenn die Verzweigungsvorhersage fehlschlägt, ist die Ausführung einiger zusätzlicher Anweisungen nach Bedarf zur Vermeidung einer Verzweigung definitiv schneller als eine falsch vorhergesagte Verzweigung. Selbst die klügsten und klügsten Compiler werden es schwer haben, diese Wahl zu treffen.

Und für Ihre Frage, ob dies etwas ist, auf das Programmierer achten müssen, lautet die Antwort mit ziemlicher Sicherheit Nein, außer in bestimmten Hot-Loops, die Sie durch Mikrooptimierungen beschleunigen möchten. Dann setzen Sie sich mit der Demontage hin und finden Möglichkeiten, sie zu optimieren. Und wie ich bereits sagte, seien Sie bereit, diese Entscheidungen erneut zu prüfen, wenn Sie auf eine neuere Version des Compilers aktualisieren, da dieser entweder etwas Dummes mit Ihrem kniffligen Code anstellen kann oder seine Optimierungsheuristik so weit geändert hat, dass Sie zurückkehren können zur Verwendung Ihres Originalcodes. Kommentar gründlich!

Eine wichtige Sache zu beachten ist, dass

(curr[i] < 479) && (l[i + shift] < 479)

und

(curr[i] < 479) * (l[i + shift] < 479)

sind nicht semantisch äquivalent! Insbesondere wenn Sie jemals die Situation haben, in der:

• 0 <= i und i < curr.size() sind beide wahr
• curr[i] < 479 ist falsch
• i + shift < 0 oder i + shift >= l.size() ist wahr

dann der Ausdruck (curr[i] < 479) && (l[i + shift] < 479) garantiert ein genau definierter boolescher Wert. Beispielsweise verursacht es keinen Segmentierungsfehler.

Unter diesen Umständen ist der Ausdruck (curr[i] < 479) * (l[i + shift] < 479)jedoch undefiniertes Verhalten . es ist zulässig, einen Segmentierungsfehler zu verursachen.

Dies bedeutet, dass der Compiler beispielsweise für das ursprüngliche Code-Snippet nicht einfach eine Schleife schreiben kann, die beide Vergleiche durchführt und eine ausführt and Operation , es sei denn, der Compiler kann auch nachweisen, dass l[i + shift]in einer Situation, in der dies nicht erforderlich ist , niemals ein Segfault verursacht wird.

Kurz gesagt, der ursprüngliche Code bietet weniger Optimierungsmöglichkeiten als letzterer. (Ob der Compiler die Gelegenheit erkennt oder nicht, ist natürlich eine ganz andere Frage.)

Sie können die Originalversion reparieren, indem Sie stattdessen Folgendes tun

bool t1 = (curr[i] < 479);
bool t2 = (l[i + shift] < 479);
if (t1 && t2) {
    // ...

Der &&Bediener führt eine Kurzschlussauswertung durch. Dies bedeutet, dass der zweite Operand nur ausgewertet wird, wenn der erste ausgewertet wird true. Dies führt in diesem Fall sicherlich zu einem Sprung.

Sie können ein kleines Beispiel erstellen, um dies zu zeigen:

#include <iostream>

bool f(int);
bool g(int);

void test(int x, int y)
{
  if ( f(x) && g(x)  )
  {
    std::cout << "ok";
  }
}

Die Assembler-Ausgabe finden Sie hier .

Sie können sehen, dass der generierte Code zuerst aufgerufen wird f(x), dann die Ausgabe überprüft und zur Auswertung springt, g(x)wann dies wartrue . Andernfalls verlässt es die Funktion.

Die Verwendung der "booleschen" Multiplikation erzwingt stattdessen jedes Mal die Auswertung beider Operanden und benötigt daher keinen Sprung.

Abhängig von den Daten kann der Sprung zu einer Verlangsamung führen, da er die Pipeline der CPU und andere Dinge wie die spekulative Ausführung stört. Normalerweise hilft die Verzweigungsvorhersage, aber wenn Ihre Daten zufällig sind, kann nicht viel vorhergesagt werden.

Dies kann daran liegen, dass der &&Compiler bei Verwendung des logischen Operators zwei Bedingungen überprüfen muss, damit die if-Anweisung erfolgreich ist. Im zweiten Fall, da Sie implizit einen int-Wert in einen Bool konvertieren, trifft der Compiler einige Annahmen basierend auf den übergebenen Typen und Werten sowie (möglicherweise) einer einzelnen Sprungbedingung. Es ist auch möglich, dass der Compiler die jmps mit Bitverschiebungen vollständig optimiert.