Quali, se esistono, i compilatori C ++ eseguono l’ottimizzazione della ricorsione in coda?

Mi sembra che funzioni perfettamente bene per ottimizzare la ricorsione in coda sia in C che in C ++, eppure durante il debug non vedo mai uno stack di frame che indichi questa ottimizzazione. È abbastanza buono, perché lo stack mi dice quanto è profonda la ricorsione. Tuttavia, l’ottimizzazione sarebbe anche carina.

I compilatori C ++ fanno questa ottimizzazione? Perché? Perchè no?

Come faccio a dire al compilatore di farlo?

  • Per MSVC: /O2 o /Ox
  • Per GCC: -O2 o -O3

Che ne dici di verificare se il compilatore ha fatto questo in un determinato caso?

  • Per MSVC, abilitare l’output PDB per poter tracciare il codice, quindi ispezionare il codice
  • Per GCC ..?

Prenderò comunque suggerimenti su come determinare se una certa funzione è ottimizzata in questo modo dal compilatore (anche se trovo rassicurante che Konrad mi dica di assumerlo)

È sempre ansible verificare se il compilatore fa tutto ciò facendo una ricorsione infinita e controllando se si verifica un ciclo infinito o un overflow dello stack (l’ho fatto con GCC e ho scoperto che -O2 è sufficiente), ma voglio essere in grado di controllare una determinata funzione che so che terminerà comunque. Mi piacerebbe avere un modo semplice per controllare questo 🙂


Dopo alcuni test, ho scoperto che i distruttori rovinano la possibilità di fare questa ottimizzazione. A volte può valer la pena cambiare l’ambito di certe variabili e temporanee per assicurarsi che vadano fuori campo prima che inizi la dichiarazione di ritorno.

Se è necessario eseguire un qualsiasi distruttore dopo la coda, non è ansible eseguire l’ottimizzazione della chiamata di coda.

Tutti gli attuali compilatori mainstream eseguono l’ottimizzazione delle chiamate tail abbastanza bene (e lo hanno fatto per oltre un decennio), anche per le chiamate reciprocamente ricorsive come:

 int bar(int, int); int foo(int n, int acc) { return (n == 0) ? acc : bar(n - 1, acc + 2); } int bar(int n, int acc) { return (n == 0) ? acc : foo(n - 1, acc + 1); } 

Lasciare che il compilatore faccia l’ottimizzazione è semplice: basta triggersre l’ottimizzazione per la velocità:

  • Per MSVC, utilizzare /O2 o /Ox .
  • Per GCC, Clang e ICC, utilizzare -O3

Un modo semplice per verificare se il compilatore ha effettuato l’ottimizzazione è eseguire una chiamata che altrimenti si tradurrebbe in un sovraccarico dello stack o guardando l’output dell’assieme.

Come nota storica interessante, l’ottimizzazione della chiamata di coda per C è stata aggiunta al GCC nel corso di una tesi di diploma di Mark Probst. La tesi descrive alcuni avvertimenti interessanti nell’implementazione. Vale la pena leggerlo.

gcc 4.3.2 completamente inline questa funzione (implementazione crappy / trivial atoi() ) in main() . Il livello di ottimizzazione è -O1 . Mi accorgo che se ci gioco con esso (anche cambiando da static a extern , la ricorsione della coda va via piuttosto velocemente, quindi non dipenderei da essa per la correttezza del programma.

 #include  static int atoi(const char *str, int n) { if (str == 0 || *str == 0) return n; return atoi(str+1, n*10 + *str-'0'); } int main(int argc, char **argv) { for (int i = 1; i != argc; ++i) printf("%s -> %d\n", argv[i], atoi(argv[i], 0)); return 0; } 

La maggior parte dei compilatori non esegue alcun tipo di ottimizzazione in una build di debug.

Se utilizzi VC, prova una versione di build con le informazioni sul PDB triggerste: questo ti consentirà di tracciare l’app ottimizzata e dovresti vedere, se tutto va bene, ciò che desideri. Nota, tuttavia, che il debugging e il tracciamento di una build ottimizzata ti faranno saltare dappertutto, e spesso non puoi controllare direttamente le variabili poiché finiscono sempre nei registri o vengono completamente ottimizzate. È un’esperienza “interessante” …

Oltre all’ovvio (i compilatori non fanno questo tipo di ottimizzazione a meno che non lo chiediate), c’è una complessità nell’ottimizzazione delle chiamate tail in C ++: i distruttori.

Dato qualcosa come:

  int fn(int j, int i) { if (i <= 0) return j; Funky cls(j,i); return fn(j, i-1); } 

Il compilatore non può (in generale) tail-call ottimizzare questo perché ha bisogno di chiamare il distruttore di cls dopo il ritorno delle chiamate ricorsive.

A volte il compilatore può vedere che il distruttore non ha effetti collaterali esternamente visibili (quindi può essere fatto presto), ma spesso non può.

Una forma particolarmente comune di questo è dove Funky è in realtà un std::vector o simile.

Come menziona Greg, i compilatori non lo faranno in modalità di debug. Va bene che le build di debug siano più lente di una build prod, ma non dovrebbero bloccarsi più spesso: e se si dipende da un’ottimizzazione delle chiamate tail, possono fare esattamente questo. Per questo motivo è spesso preferibile riscrivere la coda come un normale ciclo. 🙁