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

149

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.

Magnus Hoff
fuente

Respuestas:

128

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.

Konrad Rudolph
fuente
ICC lo haría, creo. Que yo sepa, ICC produce el código más rápido del mercado.
Paul Nathan
35
@Paul La pregunta es cuánto de la velocidad del código ICC es causada por optimizaciones algorítmicas como las optimizaciones de llamada de cola y cuánto es causada por las optimizaciones de caché y microinstrucción que solo Intel, con su conocimiento íntimo de sus propios procesadores, puede hacer.
Imagist
66
gcctiene una opción más estrecha -foptimize-sibling-callspara "optimizar las llamadas recursivas entre hermanos y cola". Esta opción (de acuerdo con gcc(1)las páginas de manual para las versiones 4.4, 4.7 y 4.8 de orientación varias plataformas) está activado en niveles -O2, -O3, -Os.
FooF
Además, ejecutar en modo DEPURAR sin solicitar explícitamente optimizaciones NO hará NINGUNA optimización en absoluto. Puede habilitar PDB para el modo de lanzamiento verdadero EXE e intente pasar por eso, pero tenga en cuenta que la depuración en el modo de lanzamiento tiene sus complicaciones: variables invisibles / despojadas, variables fusionadas, variables que quedan fuera del alcance en un alcance desconocido / inesperado, variables que nunca entran alcance y se convirtieron en constantes verdaderas con direcciones de nivel de pila y, bueno, marcos de pila combinados o faltantes. Por lo general, los marcos de pila combinados significan que el destinatario de la llamada está en línea, y los marcos faltantes / retroactivos probablemente son una cola.
Петър Петров
21

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;
}
Tom Barta
fuente
1
Sin embargo, puede activar la optimización del tiempo de enlace y supongo que incluso un externmétodo podría estar en línea entonces.
Konrad Rudolph
55
Extraño. Acabo de prueba gcc 4.2.3 (x86, Slackware 12.1) y gcc 4.6.2 (AMD64, Debian sibilante) y con-O1 hay ninguna inlining y no la optimización de la cola de recursión . Tienes que usar -O2para eso (bueno, en 4.2.x, que es bastante antiguo ahora, todavía no estará en línea). Por cierto, también vale la pena agregar que gcc puede optimizar la recursividad incluso cuando no es estrictamente una cola (como factorial sin acumulador).
przemoc
16

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.

Martin Bonner apoya a Monica
fuente
No funciona para mi El sistema me dice que mi voto está bloqueado hasta que se edite la respuesta.
hmuelner
Solo edité la respuesta (paréntesis eliminadas) y ahora pude deshacer mi voto negativo.
hmuelner
11

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" ...

Greg Whitfield
fuente
2
pruebe gcc why -g -O3 y obtenga optimizaciones en una compilación de depuración. xlC tiene el mismo comportamiento.
g24l
Cuando dices "la mayoría de los compiladores": ¿qué colecciones de compiladores consideras? Como se señaló, hay al menos dos compiladores que realizan optimizaciones durante la compilación de depuración, y que yo sepa, VC también lo hace (excepto si está habilitando modificar y continuar, tal vez).
Skyking
7

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. :-(

0124816
fuente