Pourquoi .NET / C # n'est-il pas optimisé pour la récursivité des appels de fin?

J'ai trouvé cette question sur les langues optimisant la récursivité de la queue. Pourquoi C # n'optimise pas la récursivité de queue, chaque fois que possible?

Pour un cas concret, pourquoi cette méthode n'est-elle pas optimisée en boucle ( Visual Studio 2008 32 bits, si cela compte)?:

private static void Foo(int i)
{
    if (i == 1000000)
        return;

    if (i % 100 == 0)
        Console.WriteLine(i);

    Foo(i+1);
}

La compilation JIT est un équilibre délicat entre ne pas passer trop de temps à faire la phase de compilation (ralentissant ainsi considérablement les applications de courte durée) et ne pas faire suffisamment d'analyses pour maintenir l'application compétitive à long terme avec une compilation standard à l'avance .

Fait intéressant, le NGen compilation ne visent pas à être plus agressives dans leurs optimisations. Je soupçonne que c'est parce qu'ils ne veulent tout simplement pas avoir de bogues où le comportement dépend du fait que le JIT ou NGen soit responsable du code machine.

Le CLR lui-même prend en charge l'optimisation des appels de fin, mais le compilateur spécifique au langage doit savoir comment générer l' opcode pertinent et le JIT doit être prêt à le respecter. Le fsc de F # générera les opcodes appropriés (bien que pour une simple récursion, il puisse simplement convertir le tout en whileboucle directement). Le csc de C # ne le fait pas.

Voir ce billet de blog pour quelques détails (très probablement maintenant obsolète compte tenu des récents changements JIT). Notez que le CLR change pour 4.0 les x86, x64 et ia64 le respecteront .

Cette soumission de commentaires sur Microsoft Connect doit répondre à votre question. Il contient une réponse officielle de Microsoft, je vous recommande donc de suivre cela.

Merci pour la suggestion. Nous avons envisagé d'émettre des instructions d'appel de fin à un certain nombre de points dans le développement du compilateur C #. Cependant, il y a quelques problèmes subtils qui nous ont poussés à éviter cela jusqu'à présent: 1) Il y a en fait des frais généraux non négligeables à l'utilisation de l'instruction .tail dans le CLR (ce n'est pas seulement une instruction de saut car les appels de queue deviennent finalement dans de nombreux environnements moins stricts tels que les environnements d'exécution de langage fonctionnel où les appels de queue sont fortement optimisés). 2) Il y a peu de vraies méthodes C # où il serait légal d'émettre des appels de queue (d'autres langages encouragent les modèles de codage qui ont plus de récursivité de queue, et beaucoup de ceux qui dépendent fortement de l'optimisation des appels de queue effectuent en fait une réécriture globale (comme les transformations Continuation Passing) pour augmenter la quantité de récursivité de queue). 3) En partie à cause de 2), les cas où les méthodes C # débordent en raison d'une récursivité profonde qui aurait dû réussir sont assez rares.

Cela dit, nous continuons à regarder cela, et nous pourrions dans une prochaine version du compilateur trouver des modèles où il est logique d'émettre des instructions .tail.

En passant, comme cela a été souligné, il est intéressant de noter que la récursivité de queue est optimisée sur x64.

C # n'optimise pas la récursivité des appels de fin car c'est à cela que sert F #!

Pour plus d'informations sur les conditions qui empêchent le compilateur C # d'effectuer des optimisations des appels de fin, consultez cet article: Conditions d'appel de fin JIT CLR .

Interopérabilité entre C # et F #

C # et F # interopèrent très bien, et comme le CLR (Common Language Runtime) .NET est conçu avec cette interopérabilité à l'esprit, chaque langage est conçu avec des optimisations spécifiques à son intention et à ses objectifs. Pour un exemple qui montre à quel point il est facile d'appeler du code F # à partir du code C #, consultez Appeler du code F # à partir du code C # ; pour un exemple d'appel de fonctions C # à partir du code F #, consultez Appel de fonctions C # à partir de F # .

Pour l'interopérabilité des délégués, consultez cet article: Interopérabilité des délégués entre F #, C # et Visual Basic .

Différences théoriques et pratiques entre C # et F #

Voici un article qui couvre certaines des différences et explique les différences de conception de la récursivité des appels de queue entre C # et F #: Génération de l'opcode Tail-Call en C # et F # .

Voici un article avec quelques exemples en C #, F # et C ++ \ CLI: Adventures in Tail Recursion en C #, F # et C ++ \ CLI

La principale différence théorique est que C # est conçu avec des boucles tandis que F # est conçu sur les principes du calcul Lambda. Pour un très bon livre sur les principes du calcul Lambda, voir ce livre gratuit: Structure et interprétation des programmes informatiques, par Abelson, Sussman et Sussman .

Pour un très bon article d'introduction sur les appels de queue en F #, consultez cet article: Introduction détaillée aux appels de queue en F # . Enfin, voici un article qui couvre la différence entre la récursivité sans queue et la récursion d'appel de queue (en F #): la récursivité de queue vs la récursivité sans queue en F sharp .

On m'a récemment dit que le compilateur C # pour 64 bits optimise la récursivité de la queue.

C # implémente également cela. La raison pour laquelle elle n'est pas toujours appliquée est que les règles utilisées pour appliquer la récursivité de queue sont très strictes.

Vous pouvez utiliser la technique du trampoline pour les fonctions récursives de queue en C # (ou Java). Cependant, la meilleure solution (si vous vous souciez seulement de l'utilisation de la pile) est d'utiliser cette petite méthode d' aide pour envelopper des parties de la même fonction récursive et la rendre itérative tout en gardant la fonction lisible.

Comme d'autres réponses l'ont mentionné, CLR prend en charge l'optimisation des appels de queue et il semble qu'il faisait historiquement l'objet d'améliorations progressives. Mais sa prise en charge en C # a un Proposalproblème ouvert dans le référentiel git pour la conception du langage de programmation C # Support tail recursion # 2544 .

Vous pouvez y trouver quelques détails et informations utiles. Par exemple @jaykrell mentionné

Laissez-moi vous dire ce que je sais.

Parfois, le tailcall est une performance gagnant-gagnant. Cela peut économiser du processeur. jmp est moins cher que call / ret Il peut économiser la pile. Toucher moins de pile améliore la localisation.

Parfois, le tailcall est une perte de performance, gain de pile. Le CLR a un mécanisme complexe dans lequel passer plus de paramètres à l'appelé que l'appelant a reçu. Je veux dire spécifiquement plus d'espace de pile pour les paramètres. C'est lent. Mais il conserve la pile. Il ne le fera qu'avec la queue. préfixe.

Si les paramètres de l'appelant sont plus grands que ceux de l'appelé, il s'agit généralement d'une transformation gagnant-gagnant assez facile. Il peut y avoir des facteurs tels que le changement de position de paramètre de géré à entier / flottant, et la génération de StackMaps précis et autres.

Maintenant, il y a un autre angle, celui des algorithmes qui exigent l'élimination des appels de queue, dans le but de pouvoir traiter des données arbitrairement grandes avec une pile fixe / petite. Il ne s'agit pas du tout de performances, mais de capacité à fonctionner.

Permettez-moi également de mentionner (comme info supplémentaire), lorsque nous System.Linq.Expressionsgénérons un lambda compilé en utilisant des classes d'expression dans l' espace de noms, il y a un argument nommé 'tailCall' qui, comme expliqué dans son commentaire, est

Un booléen qui indique si l'optimisation de l'appel de fin sera appliquée lors de la compilation de l'expression créée.

Je ne l'ai pas encore essayé, et je ne sais pas comment cela peut aider à répondre à votre question, mais quelqu'un peut probablement l'essayer et peut être utile dans certains scénarios:

var myFuncExpression = System.Linq.Expressions.Expression.Lambda<Func< … >>(body: … , tailCall: true, parameters: … );

var myFunc =  myFuncExpression.Compile();