Die folgende Implementierung von square erzeugt eine Reihe von cmp / je-Anweisungen, wie ich es von einer verketteten if-Anweisung erwarten würde:
int square(int num) {
if (num == 0){
return 0;
} else if (num == 1){
return 1;
} else if (num == 2){
return 4;
} else if (num == 3){
return 9;
} else if (num == 4){
return 16;
} else if (num == 5){
return 25;
} else if (num == 6){
return 36;
} else if (num == 7){
return 49;
} else {
return num * num;
}
}Und das Folgende erzeugt eine Datentabelle für die Rückgabe:
int square_2(int num) {
switch (num){
case 0: return 0;
case 1: return 1;
case 2: return 4;
case 3: return 9;
case 4: return 16;
case 5: return 25;
case 6: return 36;
case 7: return 49;
default: return num * num;
}
}Warum kann gcc den oberen in den unteren nicht optimieren?
Demontage als Referenz: https://godbolt.org/z/UP_igi
BEARBEITEN: Interessanterweise generiert MSVC eine Sprungtabelle anstelle einer Datentabelle für den Switch-Fall. Und überraschenderweise optimiert Clang sie auf das gleiche Ergebnis.
c++
c
gcc
optimization
compiler-optimization
chacham15
quelle
quelle
returns; Die Fälle haben keinebreaks, daher hat der Switch auch eine bestimmte Ausführungsreihenfolge. Die if / else-Kette hat in jedem Zweig Rückgaben, die Semantik ist in diesem Fall äquivalent. Die Optimierung ist nicht unmöglich . Als Gegenbeispiel optimiert icc keine der Funktionen.Antworten:
Der generierte Code für verwendet
switch-caseherkömmlicherweise eine Sprungtabelle. In diesem Fall scheint die direkte Rückgabe durch eine Nachschlagetabelle eine Optimierung zu sein, die die Tatsache nutzt, dass jeder Fall hier eine Rückgabe beinhaltet. Obwohl der Standard diesbezüglich keine Garantien gibt, wäre ich überrascht, wenn ein Compiler eine Reihe von Vergleichen anstelle einer Sprungtabelle für einen herkömmlichen Switch-Fall generieren würde.Nun kommt es
if-else, es ist genau das Gegenteil. Während dieswitch-caseAusführung unabhängig von der Anzahl der Zweige in konstanter Zeit erfolgt,if-elseist sie für eine geringere Anzahl von Zweigen optimiert. Hier würden Sie erwarten, dass der Compiler im Grunde genommen eine Reihe von Vergleichen in der Reihenfolge generiert, in der Sie sie geschrieben haben.Wenn ich also verwendet hätte,
if-elseweil ich erwarte, dass die meisten Aufrufesquare()für0oder1und selten für andere Werte ausgeführt werden, könnte das "Optimieren" dieser Werte für eine Tabellensuche tatsächlich dazu führen, dass mein Code langsamer als erwartet ausgeführt wird, wodurch mein Zweck,ifstattdessen einen zu verwenden, zunichte gemacht wird von aswitch. Obwohl es umstritten ist, denke ich, dass GCC das Richtige tut und Clang bei seiner Optimierung übermäßig aggressiv ist.Jemand hatte in den Kommentaren einen Link geteilt, über den clang diese Optimierung durchführt und für den auch auf Nachschlagetabellen basierender Code generiert wird
if-else. Etwas Bemerkenswertes passiert, wenn wir die Anzahl der Fälle mit Clang auf nur zwei (und einen Standardwert) reduzieren. Es wird erneut identischer Code für if und switch generiert, diesmal wird jedoch für beide auf Vergleiche und Verschiebungen anstelle des Lookup-Table-Ansatzes umgeschaltet . Dies bedeutet, dass selbst der Schalter, der den Schalter bevorzugt, weiß, dass das Wenn-Muster optimaler ist, wenn die Anzahl der Fälle gering ist!Zusammenfassend ist eine Folge von Vergleichen für
if-elseund eine Sprungtabelle fürswitch-casedas Standardmuster, dem Compiler folgen und Entwickler beim Schreiben von Code eher erwarten. In bestimmten Sonderfällen entscheiden sich einige Compiler jedoch möglicherweise dafür, dieses Muster zu brechen, wenn sie der Meinung sind, dass es eine bessere Optimierung bietet. Andere Compiler halten sich möglicherweise trotzdem an das Muster, auch wenn es anscheinend nicht optimal ist, und vertrauen darauf, dass der Entwickler weiß, was er will. Beide sind gültige Ansätze mit ihren eigenen Vor- und Nachteilen.quelle
0und zu prüfen1)?ifoffensichtlich schneller ist? Hier ist ein Beispiel für eine Plattform, bei der sowohl 0 als auch 1 bei Verwendung schneller sindifals bei Verwendung von switch: godbolt.org/z/wcJhvS (Beachten Sie, dass auch hier mehrere andere Optimierungen im Spiel sind)ifAnweisungen oder automatisch vom Compiler generiert werden . Ich bin kein ARM-Experte, daher bin ich mir nicht sicher, ob die Behauptung, Sie seienswitchschneller alsifwahr. Es würde von der Strafe für falsch vorhergesagte Zweige abhängen, und das würde tatsächlich davon abhängen, welcher ARM.Eine mögliche Begründung ist, dass
numder generierte Code für den ersten möglicherweise schneller ist, wenn niedrige Werte von wahrscheinlicher sind, z. B. immer 0. Der generierte Code für den Schalter benötigt für alle Werte die gleiche Zeit.Vergleich der besten Fälle gemäß dieser Tabelle . In dieser Antwort finden Sie eine Erläuterung der Tabelle.
Wenn Sie
num == 0für "wenn" xor haben, testen Sie, je (mit Sprung), ret. Latenz: 1 + 1 + Sprung. Xor und test sind jedoch unabhängig voneinander, sodass die tatsächliche Ausführungsgeschwindigkeit schneller als 1 + 1 Zyklen wäre.Wenn Sie
num < 7für "switch" mov, cmp, ja (ohne Sprung), mov, ret haben. Latenz: 2 + 1 + kein Sprung + 2.Eine Sprunganweisung, die nicht zum Springen führt, ist schneller als eine, die zum Springen führt. Die Tabelle definiert jedoch nicht die Latenz für einen Sprung, so dass mir nicht klar ist, welche besser ist. Es ist möglich, dass der letzte immer besser ist und GCC ihn einfach nicht optimieren kann.
quelle