Warum wird ein Switch nicht wie verkettet optimiert, wenn sonst in c / c ++?

39

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.

chacham15
quelle
3
Was meinst du mit "undefiniertem Verhalten"? Solange das beobachtbare Verhalten dasselbe ist, kann der Compiler jeden
gewünschten
2
@ user207421 ignoriert das returns; Die Fälle haben keine breaks, 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.
user1810087
9
Vielleicht die einfachste Antwort ... gcc kann diese Struktur (noch) nicht sehen und optimieren.
user1810087
3
Ich stimme @ user1810087 zu. Sie haben einfach die aktuelle Grenze des Compiler-Verfeinerungsprozesses gefunden. Ein Sub-Sub-Fall, der derzeit (von einigen Compilern) nicht als optimierbar erkannt wird. Tatsächlich kann nicht jede andere If-Kette auf diese Weise optimiert werden, sondern nur die Teilmenge, in der die gleiche Variable gegen konstante Werte getestet wird.
Roberto Caboni
1
Das if-else hat eine andere Ausführungsreihenfolge von oben nach unten. Das Ersetzen des Codes durch Nur-wenn-Anweisungen hat den Maschinencode jedoch nicht verbessert. Der Schalter hingegen hat keine vordefinierte Ausführungsreihenfolge und ist im Wesentlichen nur eine verherrlichte Goto-Jump-Tabelle. Abgesehen davon darf ein Compiler über das beobachtbare Verhalten hier nachdenken, so dass die schlechte Optimierung der if-else-Version ziemlich enttäuschend ist.
Lundin

Antworten:

29

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 die switch-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 Aufrufe square()für 0oder 1und 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 a switch. 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ür switch-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.

th33lf
quelle
2
Ja, Optimierung ist ein mehrkantiges Schwert: Was sie schreiben, was sie wollen, was sie bekommen und wen wir dafür verfluchen.
Deduplikator
1
"... dann würde das 'Optimieren' für eine Tabellensuche tatsächlich dazu führen, dass mein Code langsamer ausgeführt wird als ich erwartet habe ..." Können Sie eine Begründung dafür liefern? Warum sollte eine Sprungtabelle jemals langsamer sein als zwei mögliche bedingte Verzweigungen (um Eingaben gegen 0und zu prüfen 1)?
Cody Grey
@CodyGray Ich muss gestehen, dass ich nicht das Niveau der Zählzyklen erreicht habe - ich hatte nur das Gefühl, dass das Laden aus dem Speicher durch einen Zeiger mehr Zyklen dauern könnte als ein Vergleichen und Springen, aber ich könnte mich irren. Ich hoffe jedoch, dass Sie mir zustimmen, dass selbst in diesem Fall, zumindest für '0', ifoffensichtlich schneller ist? Hier ist ein Beispiel für eine Plattform, bei der sowohl 0 als auch 1 bei Verwendung schneller sind ifals bei Verwendung von switch: godbolt.org/z/wcJhvS (Beachten Sie, dass auch hier mehrere andere Optimierungen im Spiel sind)
th33lf
1
Nun, Zählzyklen funktionieren auf modernen superskalaren OOO-Architekturen sowieso nicht. :-) Ladevorgänge aus dem Speicher werden nicht langsamer sein als falsch vorhergesagte Zweige. Die Frage ist also, wie wahrscheinlich es ist, dass der Zweig vorhergesagt wird. Diese Frage gilt für alle Arten von bedingten Verzweigungen, unabhängig davon, ob sie durch explizite ifAnweisungen oder automatisch vom Compiler generiert werden . Ich bin kein ARM-Experte, daher bin ich mir nicht sicher, ob die Behauptung, Sie seien switchschneller als ifwahr. Es würde von der Strafe für falsch vorhergesagte Zweige abhängen, und das würde tatsächlich davon abhängen, welcher ARM.
Cody Gray
0

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.

vll
quelle
1
Hmm, interessante Theorie, aber für ifs vs switch hast du: xor, test, jmp vs mov, cmp jmp. Jeweils drei Anweisungen, wobei die letzte ein Sprung ist. Scheint im besten Fall gleich, nein?
Chacham15
3
"Eine Sprunganweisung, die nicht zum Springen führt, ist schneller als eine, die zum Springen führt." Auf die Branchenvorhersage kommt es an.
Geza