Tritt der Verzweigungs-Prädiktor dabei ein?

Question

Die meisten, wenn nicht alle modernen Prozessoren verwenden eine Technik namens "Verzweigungsvorhersage", mit der sie raten, welchen Weg man in einen Wenn-Dann-Else-Zweig nehmen soll.

Ich habe eine Frage bezüglich des Schemas. Lassen Sie sich sagen, dass wir dieses Stück Code haben, in keiner bestimmten Sprache:

if(someCondition) 
{ 
    // some action 
    return someValue; 
} 
// some other action 
return someOtherValue; 

Logisch gesehen, ist, dass Code zu diesem Code-äquivalent:

if(someCondition) 
{ 
    // some action 
    return someValue; 
} 
else 
{ 
    // some other action 
    return someOtherValue; 
} 

Der Verzweigungsprädiktor ‚vorhersagen‘ in der den Zweig würde zweites Beispiel, aber was ist mit dem ersten Beispiel? Wird es raten? Was wird in die Pipeline geladen? Gibt es irgendeine Geschwindigkeit, die man mit den beiden Beispielen erreichen kann, wenn man den Einfluss des tatsächlichen Codes in den Blöcken außer Acht lässt?

Meine Vermutung, es ist abhängig vom Compiler: Wenn Anweisungen implementiert werden (in Assembly) mit Sprüngen, die nur durchgeführt werden, wenn das Vergleichsflag im Register gesetzt ist. Wie der Assembler aussieht, hängt vom Compiler ab. Wenn es keinen gemeinsamen Weg gibt, mit dem jeder Compiler arbeitet, was ich bezweifle, ist dies Compiler-abhängig. Was würde in diesem Fall bei den neuesten Visual Studio C++ - und GC++ - Compilern passieren?

Als Hexafraktion aufgezeigt, die Beziehung zwischen den Rückgabewerten sowie wie someCondition bestimmt wird ... der Verzweigung Prädiktor möglicherweise nicht treten. Betrachten wir nur wahr und falsch als Rückgabewerte. Für die Bedingung nehmen wir sowohl an, dass es ein Feld ist, das vorherbestimmt wurde, entweder innerhalb oder außerhalb der Funktion, eine lokale Variable und irgendeine arithmetische Aussage.

Um ehrlich zu sein, ich vermute nicht, dass es einen großen Unterschied zwischen dem Fall gibt, dass die Bedingung eine lokale Variable ist, und dem Fall, dass das Feld in der gleichen Funktion vorgegeben wurde.

Answer 1

Wahrscheinlich gcc -O3, dass auf eine glose Sequenz optimieren würde, ein bedingten Bewegungsbefehle verwenden. z.B. auf x86

# generate someValue in %rax, the x86-64 ABI's return value register 
# generate someOtherValue in %rdi, to pick one at random 
    test someCondition # probably actually test or cmp a register 
    cmovz %rdi, %rax # copy %rdi to %rax, if the zero flag is set. 
    ret 

cmov hat eine Datenabhängigkeit sowohl von seinen Eingaben als auch von Flags. Eine bedingte Verzweigung ist eine Steuerung Abhängigkeit. Die Verwendung von cmov ist oft gut, es sei denn, es ist Teil einer langen Abhängigkeitskette und die Verzweigung ist ziemlich vorhersagbar.

Wenn innerhalb der if Blöcke mehr Arbeit war, würde gcc einen bedingten Sprungbefehl erzeugen.

# generate someValue in %rax 
    test someCondition 
    jz .zero 
    ret 
.zero: 
    # compute someOtherValue. This work doesn't need to happen at all 
    # if we don't end up needing it, unlike in the cmov case 
    mov someOtherValue, %rax 
    ret 

Verzweigungsvorhersage arbeitet auf bedingte Sprunganweisungen nicht auf High-Level-Konstrukte. Die gleichen Anweisungen werden verwendet, um zum Anfang einer Schleife zurückzuspringen, wenn die Schleifenbedingung wahr ist. Gemäß http://agner.org/optimize/ erinnern sich aktuelle Intel-CPUs an Muster von bis zu 64 Iterationen für Schleifen. So haben Schleifen, die jedes Mal die gleiche Anzahl von Iterationen ausführen, bei der letzten Iteration keine Verzweigungsfehlvorhersage, wenn die Anzahl der Iterationen 64 oder weniger beträgt.

Es ist also nicht die Folge von Anweisungen, die der Verzweigungsvorhersager prüft, um zu erraten, ob ein Sprung genommen oder nicht genommen wird. Jeder einzelne Verzweigungsbefehl erhält einen Eintrag in dem Verzweigungsprotokollpuffer, wenn er genommen wird. Und ja, jeder Compiler hat keine andere Wahl, als jcc (Jump on Condition Code) Anweisungen zu verwenden, um Verzweigungen/Schleifen zu implementieren.

Der Standardwert ist nicht angenommen. Wenn diese Vorhersage korrekt ist, entfernt die CPU möglicherweise nicht immer nützliche Informationen aus dem Cache, um Platz zu schaffen. Weitere Details auf niedriger Ebene finden Sie in Agner Fogs Mikroarch-Dokument.

---

Unter Linux den Verzweigungsprädiktor in Aktion zu sehen, Sie perf stat verwenden können:

perf stat /bin/ls # in some big directory 
    ... normal ls output 

Performance counter stats for '/bin/ls': 

    10.403069  task-clock (msec)   # 0.094 CPUs utilized 
     2,255  context-switches   # 0.217 M/sec 
      0  cpu-migrations   # 0.000 K/sec 
      190  page-faults    # 0.018 M/sec 
    16,612,260  cycles     # 1.597 GHz 
    7,843,399  stalled-cycles-frontend # 47.21% frontend cycles idle 
    5,205,565  stalled-cycles-backend # 31.34% backend cycles idle 
    20,227,093  instructions    # 1.22 insns per cycle 
               # 0.39 stalled cycles per insn 
    3,975,777  branches     # 382.173 M/sec 
########### These two lines ###### 
     55,785  branch-misses    # 1.40% of all branches 

    0.110765717 seconds time elapsed 

Intel Sandybridge (i5 2500k), bei Low-Power-Taktrate, mit dem Standard-cpufreq Gouverneur, läuft nicht im Takt, bevor ls fertig ist.

Answer 2

Es gibt keinen Unterschied zwischen diesen beiden Codebeispielen. Die else ist irrelevant, da keine Verzweigung am Ende der wahren Klausel erforderlich ist. Selbst wenn das nicht wahr wäre, wäre die Verzweigung am Ende der wahren Klausel nicht bedingt.

Mit anderen Worten, muss der Code so etwas wie kompilieren:

Compute test expression 
    Branch if false to false_label 
    True action 
    Return some value 
False_label; 
    False action 
    Return some other value