Aus meinem Universitätskurs habe ich gehört, dass es per Konvention besser ist, eine wahrscheinlichere Bedingung einzugeben if eher als drin elsewas helfen kann statisch Verzweigungsprädiktor. Zum Beispiel:
if (check_collision(player, enemy)) { // very unlikely to be true
doA();
} else {
doB();
}
kann umgeschrieben werden als:
if (!check_collision(player, enemy)) {
doB();
} else {
doA();
}
Ich habe einen Blogbeitrag gefunden Verzweigungsmuster mit GCCwas dieses Phänomen näher erklärt:
Für if-Anweisungen werden Vorwärtsverzweigungen generiert. Der Grund dafür, dass sie wahrscheinlich nicht genommen werden, besteht darin, dass der Prozessor die Tatsache ausnutzen kann, dass Befehle, die dem Verzweigungsbefehl folgen, möglicherweise bereits im Befehlspuffer innerhalb der Befehlseinheit platziert sind.
daneben steht (Hervorhebung von mir):
Wenn Sie eine if-else-Anweisung schreiben, Machen Sie den “then”-Block immer wahrscheinlicher als den else-Blocksodass der Prozessor bereits im Befehlsabrufpuffer platzierte Befehle nutzen kann.
Letztendlich gibt es einen Artikel, geschrieben von Intel, Verzweigungs- und Loop-Reorganisation zur Vermeidung von Fehlvorhersagendie dies mit zwei Regeln zusammenfasst:
Statische Verzweigungsvorhersage wird verwendet, wenn keine Daten vom Mikroprozessor gesammelt werden, wenn er auf eine Verzweigung trifft, was typischerweise das erste Mal ist, dass eine Verzweigung angetroffen wird. Die Regeln sind einfach:
- Eine Vorwärtsverzweigung ist standardmäßig nicht vergeben
- Eine Rückwärtsverzweigung ist standardmäßig vergriffen
Um Ihren Code effektiv zu schreiben, nutzen Sie diese Regeln beim Schreiben ansonsten oder Schalter Aussagen, überprüfen Sie zuerst die häufigsten Fälle und arbeiten Sie sich schrittweise bis zu den am wenigsten häufigen Fällen vor.
Soweit ich weiß, besteht die Idee darin, dass die Pipeline-CPU den Anweisungen aus dem Anweisungscache folgen kann, ohne sie zu unterbrechen, indem sie zu einer anderen Adresse innerhalb des Codesegments springt. Mir ist jedoch bewusst, dass dies bei modernen CPU-Mikroarchitekturen möglicherweise stark vereinfacht wird.
Es sieht jedoch so aus, als würde GCC diese Regeln nicht respektieren. Angesichts des Codes:
extern void foo();
extern void bar();
int some_func(int n)
{
if (n) {
foo();
}
else {
bar();
}
return 0;
}
es generiert (Version 6.3.0 mit -O3 -mtune=intel):
some_func:
lea rsp, [rsp-8]
xor eax, eax
test edi, edi
jne .L6 ; here, forward branch if (n) is (conditionally) taken
call bar
xor eax, eax
lea rsp, [rsp+8]
ret
.L6:
call foo
xor eax, eax
lea rsp, [rsp+8]
ret
Der einzige Weg, den ich gefunden habe, um das gewünschte Verhalten zu erzwingen, ist das Umschreiben der if Bedingung mit __builtin_expect folgendermaßen:
if (__builtin_expect(n, 1)) { // force n condition to be treated as true
Der Assemblercode würde also zu:
some_func:
lea rsp, [rsp-8]
xor eax, eax
test edi, edi
je .L2 ; here, backward branch is (conditionally) taken
call foo
xor eax, eax
lea rsp, [rsp+8]
ret
.L2:
call bar
xor eax, eax
lea rsp, [rsp+8]
ret
stackoverflow.com/q/109710/905902 Der Linux-Kernel verwendet Makros (alle __builtin_expect), um das vorherige Wissen über die bedingten Verzweigungen zu nutzen.
– Wildpässer
26. Januar 2017 um 19:12 Uhr
Moderne Intel-CPUs verwenden keine statische Verzweigungsvorhersage. Ich glaube auch nicht, dass GCC irgendwo verspricht, die “wahre” Klausel einer if/else-Anweisung als die wahrscheinlichste Alternative zu betrachten. Du sollst verwenden
__builtin_expect, wie Wildplasser erwähnt, um zu sagen, was wahrscheinlicher ist. Oder noch besser, profilgeführte Optimierung.– Rossgrat
26. Januar 2017 um 19:51 Uhr
Siehe Mikroarchitektur-Handbuch von Anger Fog. Abschnitt 3.16 „Statische Vorhersage in PM und Core 2“: „Diese Prozessoren verwenden keine statische Vorhersage. Der Prädiktor macht einfach eine zufällige Vorhersage, wenn eine Verzweigung zum ersten Mal gesehen wird, abhängig davon, was zufällig in dem zugewiesenen BTB-Eintrag steht die neue Filiale.”. agner.org/optimieren
– Rossgrat
26. Januar 2017 um 20:01 Uhr
Selbst in einem umfassenden Programm ist es unwahrscheinlich, dass es eine Rolle spielt. Sofern Sie keinen Prozessor mit nur statischer Vorhersage verwenden, werden die meisten Sprünge dynamisch vorhergesagt.
– Rossgrat
26. Januar 2017 um 20:24 Uhr
Aus irgendeinem Grund geht der profile_estimate-Pass von gcc davon aus, dass n mit 54%iger Wahrscheinlichkeit 0 ist … (siehe
-fdump-tree-all-all) Normalerweise hat es eine Heuristik, dass == eher falsch ist, aber es scheint hier nicht verwendet zu werden. Sie könnten es auf Bugzilla von gcc einreichen, um danach zu fragen. Beachten Sie, dass, wenn Sie mit kompilieren-fprofile-generateführen Sie dann Ihr Programm aus und kompilieren Sie es erneut mit-fprofile-usewird gcc Zugriff auf echte Statistiken haben und bessere Entscheidungen treffen.– Marc Glisse
27. Januar 2017 um 13:41 Uhr