Quali compilatori C++, se ce ne sono, eseguono l'ottimizzazione della ricorsione della coda?

StackOverflow https://stackoverflow.com/questions/34125

Domanda

Mi sembra che funzionerebbe perfettamente per eseguire l'ottimizzazione della ricorsione della coda sia in C che in C++, tuttavia durante il debug non mi sembra mai di vedere uno stack di frame che indichi questa ottimizzazione.Questo è abbastanza buono, perché lo stack mi dice quanto è profonda la ricorsione.Tuttavia, anche l’ottimizzazione sarebbe carina.

Qualche compilatore C++ esegue questa ottimizzazione?Perché?Perché no?

Come posso dire al compilatore di farlo?

  • Per MSVC: /O2 O /Ox
  • Per il GCC: -O2 O -O3

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

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

Accetterei comunque suggerimenti su come determinare se una determinata funzione è ottimizzata in questo modo dal compilatore (anche se trovo rassicurante che Konrad mi dica di presumerlo)

È sempre possibile verificare se il compilatore fa proprio questo eseguendo una ricorsione infinita e controllando se il risultato è un ciclo infinito o uno stack overflow (l'ho fatto con GCC e ho scoperto che -O2 è sufficiente), ma voglio poter controllare una determinata funzione che so che terminerà comunque.Mi piacerebbe avere un modo semplice per verificarlo :)

Dopo alcuni test, ho scoperto che i distruttori rovinano la possibilità di effettuare questa ottimizzazione.A volte può valere la pena modificare l'ambito di determinate variabili e variabili temporanee per assicurarsi che escano dall'ambito prima dell'avvio dell'istruzione return.

Se è necessario eseguire un distruttore dopo la chiamata di coda, l'ottimizzazione della chiamata di coda non può essere eseguita.

È stato utile?

Soluzione

Tutti gli attuali compilatori tradizionali eseguono l'ottimizzazione delle chiamate di coda abbastanza bene (e lo fanno da più di un decennio), anche per chiamate reciprocamente ricorsive ad esempio:

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 esegua l'ottimizzazione è semplice:Basta attivare 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 eseguito l'ottimizzazione è eseguire una chiamata che altrimenti comporterebbe un overflow dello stack o osservare l'output dell'assembly.

Come nota storica interessante, l'ottimizzazione delle chiamate in coda per C è stata aggiunta al GCC nel corso di a tesi di diploma di Mark Probst.La tesi descrive alcuni avvertimenti interessanti nell'implementazione.Vale la pena leggerlo.

Altri suggerimenti

gcc 4.3.2 integra completamente questa funzione (scadente/banale atoi() implementazione) in main().Il livello di ottimizzazione è -O1.Noto che se ci gioco (anche cambiandolo da static A extern, la ricorsione della coda scompare abbastanza velocemente, quindi non dipenderei da essa per la correttezza del programma.

#include <stdio.h>
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;
}

Oltre all'ovvio (i compilatori non eseguono questo tipo di ottimizzazione a meno che tu non lo richieda), c'è una complessità nell'ottimizzazione delle chiamate di coda in C++:distruttori.

Dato qualcosa del tipo:

   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) la chiamata a coda ottimizza questo perché deve chiamare il distruttore di cls Dopo la chiamata ricorsiva ritorna.

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

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

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

Se utilizzi VC, prova una build di rilascio con le informazioni PDB attivate: questo ti consentirà di tracciare l'app ottimizzata e, si spera, dovresti vedere ciò che desideri.Tieni presente, tuttavia, che il debug e il tracciamento di una build ottimizzata ti faranno saltare dappertutto e spesso non potrai ispezionare direttamente le variabili poiché finiscono sempre e solo nei registri o vengono completamente ottimizzate.È un'esperienza "interessante"...

Come menziona Greg, i compilatori non lo faranno in modalità debug.Va bene che le build di debug siano più lente di una build di produzione, ma non dovrebbero bloccarsi più spesso:e se dipendi da un'ottimizzazione delle chiamate in coda, potrebbero fare esattamente questo.Per questo motivo è spesso meglio riscrivere la chiamata in coda come un ciclo normale.:-(

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top