La seguente implementazione di square produce una serie di dichiarazioni cmp/je come mi aspetterei da una dichiarazione if concatenata:
int square(int num) {
se (num == 0){
ritorna 0;
} else if (num == 1){
ritorna 1;
} else if (num == 2){
ritorna 4;
} else if (num == 3){
ritorna 9;
} else if (num == 4){
ritorna 16;
} else if (num == 5){
ritorna 25;
} else if (num == 6){
ritorna 36;
} else if (num == 7){
ritorna 49;
} else {
ritorna num * num;
}
}
E il seguente produce una tabella di dati per il ritorno:
int square_2(int num) {
switch (num){
caso 0: ritorna 0;
caso 1: ritorna 1;
caso 2: ritorna 4
caso 3: restituire 9;;
caso 4: restituire 16
caso 5: restituire 25
caso 6: restituire 36;;
caso 7: restituire 49;
default: ritorna num * num;
}
}
Perché gcc non è in grado di ottimizzare quello superiore in quello inferiore?
Disassemblaggio per riferimento: https://godbolt.org/z/UP_igi
EDIT: è interessante notare che MSVC genera una tabella di salto invece di una tabella dati per il caso switch. E sorprendentemente, clang li ottimizza allo stesso risultato.
Il codice generato per switch-case
usa convenzionalmente una tabella di salto. In questo caso, il ritorno diretto attraverso una tabella di ricerca sembra essere un'ottimizzazione che sfrutta il fatto che ogni caso qui comporta un ritorno. Sebbene lo standard non dia garanzie in tal senso, sarei sorpreso se un compilatore generasse una serie di confronti invece di una tabella di salto per uno switch-case convenzionale.
Venendo ora a if-else
, è l'esatto opposto. Mentre switch-case
viene eseguito in tempo costante, indipendentemente dal numero di rami, if-else
è ottimizzato per un numero minore di rami. Qui, ci si aspetta che il compilatore generi fondamentalmente una serie di confronti nell'ordine in cui li avete scritti.
Quindi se avessi usato if-else
perché mi aspetto che la maggior parte delle chiamate a quadro()
siano per 0
o 1
e raramente per altri valori, allora 'ottimizzazione'questo ad un table-lookup potrebbe effettivamente far girare il mio codice più lentamente di quanto mi aspetto, sconfiggendo il mio scopo di usare un if
invece di un switch
. Quindi, anche se è discutibile, sento che GCC sta facendo la cosa giusta e clang è troppo aggressivo nella sua ottimizzazione.
Qualcuno aveva, nei commenti, condiviso un link dove clang fa questa ottimizzazione e genera codice basato su lookup-table anche per if-else
. Qualcosa di notevole accade quando riduciamo il numero di casi a soli due (e un default) con clang. Ancora una volta genera codice identico sia per if che per switch, ma questa volta,
passa a confrontare e spostare invece dell'approccio lookup-table, per entrambi!
In sintesi, una sequenza di confronti per if-else
e una jump-table per switch-case
è il modello standard che i compilatori tendono a seguire e che gli sviluppatori tendono ad aspettarsi quando scrivono codice. Tuttavia, per alcuni casi speciali, alcuni compilatori potrebbero scegliere di rompere questo schema quando pensano che fornisca una migliore ottimizzazione. Altri compilatori potrebbero semplicemente scegliere di attenersi allo schema comunque, anche se apparentemente sub-ottimale, confidando che lo sviluppatore sappia cosa vuole. Entrambi sono approcci validi con i loro vantaggi e svantaggi.
Una possibile motivazione è che se valori bassi di num
sono più probabili, per esempio sempre 0, il codice generato per il primo potrebbe essere più veloce. Il codice generato per switch richiede lo stesso tempo per tutti i valori.
Confrontando i casi migliori, secondo questa tabella. Vedere questa risposta per la spiegazione della tabella.
Se num == 0
, per "if" hai xor, test, je (con salto), ret. Latenza: 1 + 1 + salto. Tuttavia, xor e test sono indipendenti, quindi la velocità di esecuzione effettiva sarebbe più veloce di 1 + 1 cicli.
Se num < 7
, per "switch" hai mov, cmp, ja (senza salto), mov, ret. Latenza: 2 + 1 + nessun salto + 2.
Un'istruzione di salto che non porta al salto è più veloce di una che porta al salto. Tuttavia, la tabella non definisce la latenza per un salto, quindi non mi è chiaro quale sia meglio. È possibile che l'ultima sia sempre migliore e che GCC non sia semplicemente in grado di ottimizzarla.