Quels compilateurs C ++, le cas échéant, utilisent l’optimisation de la récursion de la queue?

Il me semble que cela fonctionnerait parfaitement pour une optimisation de la récursion de la queue en C et en C ++, mais pendant le débogage, je ne vois jamais une stack de trames indiquant cette optimisation. C’est plutôt bien, car la stack me dit à quel point la récursivité est profonde. Cependant, l’optimisation serait également une bonne chose.

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

Comment puis-je dire au compilateur de le faire?

  • Pour MSVC: /O2 ou /Ox
  • Pour GCC: -O2 ou -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 quand même des suggestions pour 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 en effectuant une récursion infinie et en vérifiant s’il en résulte une boucle infinie ou un débordement de stack (je l’ai fait avec GCC et j’ai découvert que -O2 est suffisant), mais je veux pour pouvoir vérifier une certaine fonction que je sais finira quand même. J’aimerais avoir un moyen facile de vérifier cela 🙂


Après quelques tests, j’ai découvert que les destructeurs gâchaient la possibilité de réaliser cette optimisation. Cela peut parfois valoir la peine de modifier la scope de certaines variables et de certains éléments temporaires pour s’assurer qu’ils sont hors de scope avant que la déclaration de retour ne commence.

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

Tous les compilateurs actuels utilisent assez bien l’ optimisation des appels de queue (et ce depuis plus d’une décennie), même pour des appels 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: 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 consiste à effectuer un appel qui entraînerait un débordement de stack – ou à examiner la sortie de l’assembly.

Comme une note historique intéressante, l’optimisation de l’appel de queue pour C a été ajoutée au GCC au cours 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 de lire.

gcc 4.3.2 intègre complètement cette fonction (implémentation de atoi() / sortingvial atoi() ) dans main() . Le niveau d’optimisation est -O1 . Je remarque que si je joue avec ça (même en le changeant de static en extern , la récursion de la queue disparaît assez rapidement, donc je ne compte pas sur elle pour l’exactitude des programmes).

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

La plupart des compilateurs ne font aucune sorte d’optimisation dans une version de débogage.

Si vous utilisez VC, essayez une version avec les infos PDB activées – cela vous permettra de suivre l’application optimisée et vous devriez voir ce que vous voulez. Notez, cependant, que le débogage et le traçage d’une version optimisée vous feront sauter partout, et souvent vous ne pouvez pas inspecter directement les variables car elles ne se retrouvent que dans des registres ou sont complètement optimisées. C’est une expérience “intéressante” …

En plus des évidences (les compilateurs ne font pas ce genre d’optimisation à moins que vous ne le demandiez), il existe une complexité liée à l’optimisation de l’appel 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) optimiser 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 (cela peut donc être fait plus tôt), mais souvent il ne le peut pas.

Une forme particulièrement courante est celle où Funky est en réalité un std::vector ou similaire.

Comme le mentionne Greg, les compilateurs ne le feront pas en mode débogage. Il est acceptable que les builds de debug soient plus lents que les builds prod, mais ils ne devraient pas planter plus souvent: et si vous dépendez d’une optimisation des appels de fin, ils peuvent le faire exactement. Pour cette raison, il est souvent préférable de réécrire l’appel de queue en tant que boucle normale. 🙁