¿Qué compiladores de C ++, si los hay, optimizan la recursividad de cola?

Me parece que funcionaría perfectamente bien para hacer una optimización de recursión de cola tanto en C como en C ++, aunque durante la depuración nunca parece ver una pila de cuadros que indique esta optimización. Eso es bastante bueno, porque la pila me dice cuán profunda es la recursión. Sin embargo, la optimización también sería agradable.

¿Algún compilador de C ++ hace esta optimización? ¿Por qué? Por qué no?

¿Cómo hago para decirle al compilador que lo haga?

• Para MSVC: /O2o/Ox
• Para CCG: -O2o-O3

¿Qué tal verificar si el compilador ha hecho esto en cierto caso?

• Para MSVC, habilite la salida PDB para poder rastrear el código, luego inspeccione el código
• Para GCC ..?

Todavía tomaría sugerencias sobre cómo determinar si una determinada función está optimizada de esta manera por el compilador (aunque me parece tranquilizador que Konrad me diga que asuma)

Siempre es posible verificar si el compilador hace esto haciendo una recursión infinita y verificando si resulta en un bucle infinito o un desbordamiento de pila (hice esto con GCC y descubrí que -O2es suficiente), pero quiero ser capaz de verificar una determinada función que sé que terminará de todos modos. Me encantaría tener una manera fácil de verificar esto :)

Después de algunas pruebas, descubrí que los destructores arruinan la posibilidad de hacer esta optimización. A veces puede valer la pena cambiar el alcance de ciertas variables y temporales para asegurarse de que se salgan del alcance antes de que comience la declaración de retorno.

Si algún destructor necesita ejecutarse después de la llamada de cola, la optimización de la llamada de cola no se puede hacer.

Todos los compiladores principales actuales realizan la optimización de llamadas de cola bastante bien (y lo han hecho durante más de una década), incluso para llamadas recursivas mutuas como:

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);
}

Permitir que el compilador realice la optimización es sencillo: simplemente active la optimización para la velocidad:

• Para MSVC, use /O2o /Ox.
• Para GCC, Clang e ICC, use -O3

Una manera fácil de verificar si el compilador realizó la optimización es realizar una llamada que de otro modo resultaría en un desbordamiento de la pila, o mirando la salida del ensamblaje.

Como una nota histórica interesante, Mark Probst agregó la optimización de cola para C al CCG en el curso de una tesis de diploma . La tesis describe algunas advertencias interesantes en la implementación. Vale la pena leerlo.

gcc 4.3.2 integra completamente esta función ( atoi()implementación trivial / trivial ) en main(). El nivel de optimización es -O1. Noto que si juego con él (incluso cambiándolo de statica extern, la recursión de la cola desaparece bastante rápido, por lo que no dependería de ello para la corrección del programa.

#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;
}

Además de lo obvio (los compiladores no hacen este tipo de optimización a menos que usted lo solicite), hay una complejidad sobre la optimización de llamadas de cola en C ++: destructores.

Dado algo como:

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

El compilador no puede (en general) optimizar la cola porque necesita llamar al destructor cls después de que la llamada recursiva regrese.

A veces, el compilador puede ver que el destructor no tiene efectos secundarios visibles externamente (por lo que puede hacerse temprano), pero a menudo no puede.

Una forma particularmente común de esto es donde Funkyes realmente una std::vectoro similar.

La mayoría de los compiladores no hacen ningún tipo de optimización en una compilación de depuración.

Si usa VC, intente una versión de lanzamiento con la información de PDB activada; esto le permitirá rastrear la aplicación optimizada y, con suerte, debería ver lo que quiere en ese momento. Sin embargo, tenga en cuenta que depurar y rastrear una compilación optimizada lo impulsará por todas partes y, a menudo, no puede inspeccionar las variables directamente, ya que solo terminan en registros o se optimizan por completo. Es una experiencia "interesante" ...

Como Greg menciona, los compiladores no lo harán en modo de depuración. Está bien que las compilaciones de depuración sean más lentas que una compilación de productos, pero no deberían bloquearse más a menudo: y si depende de una optimización de llamada de cola, pueden hacer exactamente eso. Debido a esto, a menudo es mejor reescribir la llamada de cola como un bucle normal. :-(