Pourquoi .NET / C # n’optimise-t-il pas la récursivité d’appel?

J’ai trouvé cette question sur les langages optimisant la récursion de la queue. Pourquoi C # n’optimise pas la récursion de la queue, autant 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 est important)?

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 exercice d’équilibre délicat entre ne pas consacrer trop de temps à la phase de compilation (ce qui ralentit considérablement les applications de courte durée) et ne pas effectuer suffisamment d’parsings pour maintenir la compétitivité de l’application à long terme .

Il est intéressant de noter que les étapes de compilation NGen 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 le NGen soit responsable du code machine.

Le CLR lui-même prend en charge l’optimisation des appels de queue, 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 # va générer les opcodes pertinents (bien que pour une récursivité simple, il soit possible de convertir directement le tout en une boucle while). Le csc de C # ne le fait pas.

Voir ce billet de blog pour quelques détails (peut-être maintenant obsolète compte tenu des changements récents JIT). Notez que les modifications du CLR pour la version 4.0 du x86, x64 et ia64 le respecteront .

Cette soumission de commentaires Microsoft Connect devrait répondre à votre question. Il contient une réponse officielle de Microsoft, je vous recommande donc de passer par là.

Merci pour la suggestion. Nous avons envisagé d’émettre des instructions d’appel de queue à un certain nombre de points lors du développement du compilateur C #. Cependant, il y a quelques problèmes subtils qui nous ont poussés à éviter cela jusqu’à présent: 1) L’utilisation de l’instruction .tail dans le CLR entraîne un coût supplémentaire non négligeable (il ne s’agit dans de nombreux environnements moins ssortingcts tels que les environnements d’exécution de langage fonctionnel où les appels de queue sont fortement optimisés). 2) Il existe peu de méthodes C # réelles pour lesquelles il serait légal d’émettre des appels de queue (les autres langages encouragent les modèles de codage qui ont plus de récursivité, et beaucoup d’autres utilisent des réécritures globales). ) pour augmenter la récursivité de la queue). 3) En partie à cause de 2), les cas où les méthodes C # emstacknt un dépassement dû à une récursivité profonde qui aurait dû aboutir sont assez rares.

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

Au fait, comme cela a été souligné, il convient de noter que la récursion de la queue est optimisée sur x64.

C # n’optimise pas pour la récursivité d’appel car c’est ce à quoi sert F #!

Pour plus de détails sur les conditions qui empêchent le compilateur C # d’effectuer des optimisations d’appel, reportez-vous à cet article: Conditions d’appel du CLI JIT .

Interopérabilité entre C # et F #

C # et F # fonctionnent très bien, et le CLR (Common Language Runtime) .NET étant conçu pour cette interopérabilité, chaque langage est conçu avec des optimisations spécifiques. Pour un exemple montrant combien il est facile d’appeler le code F # à partir du code C #, voir Appeler le code F # à partir du code C # ; Pour un exemple d’appel des fonctions C # à partir du code F #, voir Appeler des fonctions C # à partir de F # .

Pour l’interopérabilité des delegates, voir cet article: Déléguer l’interopérabilité 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écursion d’appel entre C # et F #: Génération d’un code d’opération d’appel en C # et F # .

Voici un article avec quelques exemples en C #, F # et C ++ \ CLI: Aventures dans la récursion de queue en C #, F # et C ++ \ CLI

La principale différence théorique est que C # est conçu avec des boucles alors que F # est conçu selon 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 dans F #, consultez cet article: Introduction détaillée aux appels de queue dans F # . Enfin, voici un article qui couvre la différence entre la récursion hors queue et la récursion d’appel de queue (en F #): récursivité de la queue par rapport à la récursion sans queue dans F sharp .

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

C # implémente également ceci. La raison pour laquelle il n’est pas toujours appliqué est que les règles utilisées pour appliquer la récursion de la queue sont très ssortingctes.

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