Quels compilateurs C++, le cas échéant, optimisent la récursion de la queue ?

Question

Il me semble que l'optimisation de la récursion de queue fonctionnerait parfaitement en C et en C++. Pourtant, lors du débogage, je ne vois jamais de pile de trames indiquant cette optimisation. C'est plutôt une bonne chose, car la pile m'indique la profondeur de la récursion. Cependant, l'optimisation serait également appréciable.

Y a-t-il des compilateurs C++ qui font cette optimisation ? Pourquoi ? Pourquoi pas ?

Comment puis-je demander au compilateur de le faire ?

• Pour MSVC : /O2 ou /Ox
• Pour le GCC : -O2 ou -O3

Comment 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 le CCG

Je suis toujours preneur de suggestions sur la manière de déterminer si une certaine fonction est optimisée de cette manière par le compilateur (même si je trouve rassurant que Konrad me dise de le supposer).

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 résulte en une boucle infinie ou un débordement de pile (j'ai fait cela avec GCC et j'ai découvert que -O2 est suffisant), mais je veux pouvoir vérifier une certaine fonction dont je sais qu'elle se terminera de toute façon. J'aimerais avoir un moyen facile de vérifier cela :)

---

Après quelques tests, j'ai découvert que les destructeurs ruinent la possibilité d'effectuer cette optimisation. Il peut parfois être utile de modifier la portée de certaines variables et temporaires pour s'assurer qu'elles sortent de leur portée avant le début de l'énoncé de retour.

Si un destructeur doit être exécuté après le tail-call, l'optimisation du tail-call ne peut pas être effectuée.

Answer 1

Tous les compilateurs grand public actuels optimisent les appels de queue. assez bien (et ce depuis plus d'une décennie), même pour les appels mutuellement récursifs comme :

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

Il est facile de laisser le compilateur se charger de l'optimisation : Il suffit d'activer l'optimisation pour la vitesse :

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

Un moyen facile de vérifier si le compilateur a effectué l'optimisation est d'effectuer un appel qui, autrement, entraînerait un dépassement de pile - ou de regarder la sortie de l'assemblage.

À titre d'information historique, l'optimisation des appels de queue pour le langage C a été ajoutée au GCC au cours d'un processus d'évaluation de l'efficacité de l'application. thèse de diplôme par Mark Probst. La thèse décrit certains problèmes intéressants dans la mise en œuvre. Elle vaut la peine d'être lue.

Answer 2

Gcc 4.3.2 inline complètement cette fonction (merdique/triviale) atoi() ) en main() . Le niveau d'optimisation est -O1 . Je remarque que si je joue avec (même en le changeant de static a extern la récursion de queue disparaît assez rapidement, donc je ne dépendrai pas d'elle pour la correction 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;
}

Answer 3

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

Vu 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) optimiser le tail-call car il doit d'appeler le destructeur de cls après l'appel récursif revient.

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

Une forme particulièrement courante de ce phénomène est celle où Funky est en fait un std::vector ou similaire.

Answer 4

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

Si vous utilisez VC, essayez un release build avec les informations PDB activées - cela vous permettra de tracer l'application optimisée et vous devriez alors voir ce que vous voulez. Notez, cependant, que le débogage et le suivi d'un build optimisé vous fera sauter partout, et souvent vous ne pouvez pas inspecter les variables directement car elles finissent toujours dans les registres ou sont entièrement optimisées. C'est une expérience "intéressante"...

Answer 5

Comme le mentionne Greg, les compilateurs ne le feront pas en mode débogage. Il n'y a pas de problème à ce que les builds de débogage soient plus lents que les builds de production, mais ils ne doivent pas se planter plus souvent : et si vous dépendez de l'optimisation d'un appel de queue, c'est exactement ce qu'ils peuvent faire. Pour cette raison, il est souvent préférable de réécrire l'appel de queue comme une boucle normale :-(.