recursivo - ¿Qué compiladores de C++, si existen, realizan la optimización de recursión de cola?

recursividad en programacion

Question

Me parece que funcionaría perfectamente para hacer la optimización de recursión de cola tanto en C como en C ++, pero mientras estoy depurando, nunca veo una pila de marcos que indique esta optimización. Eso es bueno, porque la pila me dice qué tan profunda es la recursión. Sin embargo, la optimización también sería agradable.

¿Alguno de los compiladores de C ++ hacen esta optimización? ¿Por qué? Por qué no?

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

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

¿Qué hay de comprobar si el compilador ha hecho esto en un caso determinado?

• 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 el compilador optimiza una función determinada como esta (aunque me parece tranquilizador que Konrad me diga que la asuma)

Siempre es posible verificar si el compilador hace esto haciendo una recursión infinita y comprobando si resulta en un bucle infinito o un desbordamiento de pila (lo hice con GCC y descubrí que -O2 es suficiente), pero quiero para poder 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 salgan del alcance antes de que comience la declaración de devolución.

Si se necesita ejecutar cualquier destructor después de la llamada final, la optimización de la llamada final no se puede hacer.

Answer 1

Además de lo obvio (los compiladores no hacen este tipo de optimización a menos que lo solicite), existe 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) tail-call optimizar esto porque necesita llamar al destructor de cls después de que retorna la llamada recursiva.

A veces, el compilador puede ver que el destructor no tiene efectos secundarios visible externamente (por lo que se puede hacer antes), pero a menudo no puede hacerlo.

Una forma particularmente común de esto es donde Funky es realmente un std::vector o similar.

Answer 2

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 prod, pero no deberían bloquearse con mayor frecuencia: y si depende de una optimización de la cola de llamadas, pueden hacer exactamente eso. Debido a esto, a menudo es mejor reescribir la llamada final como un ciclo normal. :-(

Answer 3

La mayoría de los compiladores no realizan 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 a través de la aplicación optimizada y, con suerte, deberá ver lo que desea en ese momento. Sin embargo, tenga en cuenta que la depuración y el rastreo de una compilación optimizada lo llevará por todas partes, y con frecuencia no puede inspeccionar las variables directamente, ya que solo terminan en registros o se optimizan por completo. Es una experiencia "interesante" ...

Answer 4

Tanto la versión actual de VC ++ como la de GCC optimizan las llamadas de cola bastante bien e incluso para llamadas recursivas recíprocas. Apuesto a que el compilador de Intel también lo hace.

Dejar que el compilador haga la optimización es sencillo: simplemente active la optimización para la velocidad. Pero lo haces de todos modos, ¿verdad? ;-)

• Para MSVC, use / O2 o / Ox.
• Para GCC, use -O3

La forma más fácil de comprobar si el compilador realizó la optimización (que yo sepa) es realizar una llamada que de lo contrario resultaría en un desbordamiento de la pila, o mirando la salida del conjunto. Sin embargo, normalmente no se puede asumir que el compilador hizo la optimización.

/ EDITAR: La optimización de la llamada de Tail para C se ha agregado al GCC en el curso de una tesis de diploma de Mark Probst. La tesis describe algunas advertencias interesantes en la implementación. Vale la pena leer.

Answer 5

gcc 4.3.2 enmarca completamente esta función (implementación de mierda / trivial atoi() ) en main() . El nivel de optimización es -O1 . Me doy cuenta que si juego con eso (incluso cambiándolo de static a extern , la recursividad de cola desaparece bastante rápido, así que no dependería de ella 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;
}