Quels compilateurs C ++, le cas échéant, effectuent une optimisation de la récursivité de la queue?

Il me semble que cela fonctionnerait parfaitement pour faire une optimisation de la récursivité de queue en C et C ++, mais pendant le débogage, je ne semble jamais voir une pile de cadres indiquant cette optimisation. C'est plutôt bien, car la pile me dit à quel point la récursivité est profonde. Cependant, l'optimisation serait également très intéressante.

Est-ce que des compilateurs C ++ font cette optimisation? Pourquoi? Pourquoi pas?

Comment dire au compilateur de le faire?

• Pour MSVC: /O2ou/Ox
• Pour GCC: -O2ou-O3

Que diriez-vous de vérifier si le compilateur a fait cela dans un certain cas?

• Pour MSVC, activez la sortie PDB pour pouvoir tracer le code, puis inspectez le code
• Pour GCC ..?

Je prendrais toujours des suggestions sur la façon de déterminer si une certaine fonction est optimisée comme celle-ci par le compilateur (même si je trouve rassurant que Konrad me dise de l'assumer)

Il est toujours possible de vérifier si le compilateur fait cela du tout en faisant une récursion infinie et en vérifiant si cela se traduit par une boucle infinie ou un débordement de pile (je l'ai fait avec GCC et j'ai découvert que c'était -O2suffisant), mais je veux être capable de vérifier une certaine fonction dont je sais qu'elle se terminera de toute façon. J'adorerais avoir un moyen facile de vérifier cela :)

Après quelques tests, j'ai découvert que les destructeurs ruinaient la possibilité de faire cette optimisation. Cela peut parfois valoir la peine de changer la portée de certaines variables et temporaires pour s'assurer qu'elles sortent de la portée avant le début de l'instruction return.

Si un destructeur doit être exécuté après l'appel final, l'optimisation de l'appel final ne peut pas être effectuée.

Tous les compilateurs grand public actuels effectuent assez bien l' optimisation des appels de queue (et ce depuis plus d'une décennie), même pour des appels mutuellement récursifs tels que:

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

Laisser le compilateur faire l'optimisation est simple: activez simplement l'optimisation pour la vitesse:

• Pour MSVC, utilisez /O2ou /Ox.
• Pour GCC, Clang et ICC, utilisez -O3

Un moyen simple de vérifier si le compilateur a effectué l'optimisation consiste à effectuer un appel qui entraînerait autrement un débordement de pile - ou à consulter la sortie de l'assembly.

Comme note historique intéressante, l'optimisation des appels de queue pour C a été ajoutée au GCC dans le cadre d'une thèse de diplôme par Mark Probst. La thèse décrit quelques mises en garde intéressantes dans la mise en œuvre. Cela vaut la peine d'être lu.

gcc 4.3.2 intègre complètement cette fonction ( atoi()implémentation merdique / triviale ) dans main(). Le niveau d'optimisation est -O1. Je remarque que si je joue avec (même en le changeant de staticà extern, la récursivité de la queue disparaît assez rapidement, donc je ne compterais pas dessus pour l'exactitude du programme.

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

En plus de l'évidence (les compilateurs ne font pas ce genre d'optimisation à moins que vous ne le demandiez), il y a une complexité à propos de l'optimisation des appels de fin en C ++: les destructeurs.

Compte tenu de quelque chose comme:

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

Le compilateur ne peut pas (en général) l'optimisation de l'appel de fin car il doit appeler le destructeur de cls après le retour de l'appel récursif.

Parfois, le compilateur peut voir que le destructeur n'a pas d'effets secondaires visibles de l'extérieur (donc cela peut être fait tôt), mais souvent il ne peut pas.

Une forme particulièrement courante de ceci est où Funkyest en fait un std::vectorou similaire.

La plupart des compilateurs ne font aucun type d'optimisation dans une version de débogage.

Si vous utilisez VC, essayez une version de version avec les informations PDB activées - cela vous permettra de suivre l'application optimisée et vous devriez, espérons-le, voir ce que vous voulez alors. Notez, cependant, que le débogage et le traçage d'une version optimisée vous feront voyager partout, et souvent vous ne pouvez pas inspecter directement les variables car elles ne finissent que dans des registres ou sont entièrement optimisées. C'est une expérience "intéressante" ...

Comme Greg le mentionne, les compilateurs ne le feront pas en mode débogage. Il est normal que les versions de débogage soient plus lentes qu'une génération de prod, mais elles ne devraient pas planter plus souvent: et si vous dépendez d'une optimisation des appels de fin, ils peuvent faire exactement cela. Pour cette raison, il est souvent préférable de réécrire l'appel de fin comme une boucle normale. :-(