Pourquoi .NET/C# n'optimise-t-il pas la récursivité des appels de queue ?

Question

J'ai trouvé cette question sur les langages qui optimisent la récursion de queue. Pourquoi le C# n'optimise-t-il pas la récursion de queue, lorsque cela est possible ?

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

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

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

    Foo(i+1);
}

Answer 1

La compilation JIT est un exercice d'équilibre délicat entre le fait de ne pas passer trop de temps à la phase de compilation (ce qui ralentit considérablement les applications de courte durée) et le fait de ne pas faire assez d'analyse pour que l'application reste compétitive à long terme par rapport à une compilation standard en avance sur le temps.

Il est intéressant de noter que le NGen Les étapes de 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 dont le comportement dépend du fait que le JIT ou le NGen était responsable du code machine.

El CLR lui-même prend en charge l'optimisation des appels de queue, mais le compilateur spécifique à la langue doit savoir comment générer le code d'accès à la queue approprié. opcode et le JIT doit être prêt à la respecter. F#'s fsc générera les opcodes appropriés (bien que pour une simple récursion, il peut simplement convertir le tout en un fichier de type while boucle directement). Le csc du C# ne le fait pas.

Voir cet article de blog pour plus de détails (il est fort possible qu'ils ne soient plus à jour étant donné les récents changements de JIT). Notez que les modifications apportées au CLR pour la version 4.0 les x86, x64 et ia64 le respecteront .

Answer 2

Ce site Soumission des commentaires sur Microsoft Connect devrait répondre à votre question. Il contient une réponse officielle de Microsoft, je vous recommande donc de vous y fier.

Merci pour la suggestion. Nous avons envisagé d'émettre un appel de queue à un certain nombre de points dans le le développement du compilateur C#. Cependant, il y a quelques problèmes subtils qui nous ont poussés à l'éviter jusqu'à jusqu'à présent : 1) Il y a en fait un un coût non négligeable lié à l'utilisation de l'instruction l'utilisation de l'instruction .tail dans le CLR (ce n'est instruction de saut comme les appels de queue que les appels de queue deviennent finalement dans de moins stricts, tels que les environnements comme les environnements d'exécution des langages fonctionnels où les appels de queue sont fortement optimisés). 2) Il y a peu de méthodes C# réelles où il serait où il serait légal d'émettre des appels de queue (d'autres langages encouragent des modèles de codage de codage qui ont plus de récursion récursion de queue, et beaucoup de ceux qui s'appuient fortement sur l'optimisation des appels de queue font en fait de la réécriture globale (comme les transformations de passage de continuité) pour augmenter la quantité de récursion récursion). 3) En partie à cause de 2), les cas où les méthodes C# débordent de la pile à cause d'une récursion profonde qui aurait dû réussi sont assez rares.

Tout cela dit, nous continuons à examiner cela, et nous pouvons dans une future version du compilateur trouver des modèles où il est logique d'émettre des instructions .tail dans certains cas.

D'ailleurs, comme cela a été souligné, il convient de noter que la récursion de queue es optimisé sur x64.

Answer 3

Le C# n'optimise pas la récursivité des appels de queue, car le F# est fait pour ça !

Pour plus de détails sur les conditions qui empêchent le compilateur C# d'effectuer des optimisations de type "tail-call", voir cet article : Conditions d'appel de queue JIT CLR .

Interopérabilité entre C# et F#

C# et F# interagissent très bien, et comme le Common Language Runtime (CLR) de .NET a été conçu dans l'optique de cette interopérabilité, 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 de code C#, voir Appeler du code F# à partir de code C# ; pour un exemple d'appel de fonctions C# à partir de code F#, voir Appeler des fonctions C# depuis F# .

Pour l'interopérabilité des délégués, voir 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écursion par appel de queue entre C# et F# : Génération d'Opcode Tail-Call 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 sur les principes du Lambda calculus. Pour un très bon livre sur les principes du Lambda calculus, voir ce livre gratuit : Structure et interprétation des programmes informatiques, par Abelson, Sussman et Sussman. .

Pour un très bon article d'introduction aux appels de queue en F#, voir cet article : Introduction détaillée aux appels de queue en F# . Enfin, voici un article qui traite de la différence entre la récursion sans appel de queue et la récursion avec appel de queue (en F#) : Récursion à queue ou récursion sans queue en fa dièse .

Answer 4

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

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

Answer 5

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