Pourquoi Java n'a-t-il pas d'optimisation pour la récursion finale?

92

D'après ce que j'ai lu: La raison en est qu'il n'est pas facile de déterminer quelle méthode sera appelée, car nous avons un héritage.

Cependant, pourquoi Java n’a-t-il pas au moins une optimisation de la récursion pour les méthodes statiques et n’impose pas le moyen approprié d’appeler des méthodes statiques avec le compilateur?

Pourquoi Java n'a-t-il aucun support pour la récursion de la queue?

Je ne suis pas sûr qu'il y ait une difficulté du tout.

En ce qui concerne le duplicata suggéré , comme l'explique Jörg W Mittag 1 :

  • L'autre question concerne le coût total de possession, celui-ci concernant TRE. TRE est beaucoup plus simple que TCO.
  • En outre, l’autre question concerne les limitations imposées par la machine virtuelle Java aux implémentations de langage souhaitant être compilées dans la machine virtuelle. Cette question concerne Java, qui est le seul langage qui n’est pas restreint par la machine virtuelle, dans la mesure où la spécification de la machine virtuelle peut être modifiée. les mêmes personnes qui conçoivent Java.
  • Enfin, il n'y a même pas de restriction dans la JVM à propos de TRE, car celle-ci a un GOTO intra-méthode, qui est tout ce dont vous avez besoin pour TRE.

1 Formatage ajouté pour rappeler les points créés.

java compiler recursion InforméA
la source
26
Pour citer Eric Lippert : "Les fonctionnalités ne sont pas bon marché, elles sont extrêmement chères et ne doivent pas seulement justifier leurs propres coûts, elles doivent justifier le coût d'opportunité de ne pas utiliser la centaine d'autres fonctionnalités que nous aurions pu réaliser avec ce budget." Java a été conçu en partie pour attirer les développeurs C / C ++ et l’optimisation de la récursion finale n’est pas garantie dans ces langages.
Doval
5
Corrigez-moi si je me trompe, mais Eric Lippert est-il le concepteur de C # qui a l'optimisation de la récursion de la queue?
InformedA
1
Il fait partie de l'équipe de compilation C #, oui.
Doval
10
D'après ce que j'ai compris, l'EJE pourrait le faire , si certaines conditions sont remplies , peut-être. Donc, en pratique, vous ne pouvez pas compter dessus. Mais le fait que C # l'ait ou non est sans importance pour Eric.
Doval
4
@InstructedA Si vous creusez un peu plus loin, vous pouvez voir que cela n'est jamais fait dans le compilateur JIT 32 bits. Le JIT 64 bits est plus récent et plus intelligent à bien des égards. Le compilateur expérimental encore plus récent (à la fois pour 32 et 64 bits) est encore plus intelligent et supportera l'optimisation de la récursion finale en IL qui ne le demande pas explicitement. Vous devez également prendre en compte un autre point: les compilateurs JIT n’ont pas beaucoup de temps. Ils sont fortement optimisés pour la vitesse - une application dont la compilation en C ++ peut prendre des heures peut encore passer de IL à natif en quelques centaines de ms, tout au plus (au moins partiellement).
Luaan

Réponses:

132

Comme l'explique Brian Goetz (architecte de langage Java chez Oracle) dans cette vidéo :

Dans les classes [...] jdk, un certain nombre de méthodes sensibles à la sécurité reposent sur le comptage des cadres de pile entre le code de la bibliothèque jdk et le code appelant pour déterminer qui les appelle.

Tout ce qui modifierait le nombre d'images sur la pile briserait cela et provoquerait une erreur. Il admet que c'était une raison stupide, et les développeurs du JDK ont depuis remplacé ce mécanisme.

Il mentionne ensuite que ce n'est pas une priorité, mais que la récursion de la queue

finira par se faire.

NB: Ceci s'applique à HotSpot et à OpenJDK, les autres machines virtuelles peuvent varier.

ggovan
la source
7
Je suis étonné qu'il y ait une réponse aussi sobre que celle-là! Mais on dirait vraiment que la réponse est possible. C’est maintenant possible, pour des raisons techniques dépassées, cela n’a pas encore été fait. Nous attendons donc maintenant que quelqu'un décide qu’il est assez important à mettre en œuvre.
BrianH
1
Pourquoi ne pas implémenter une solution de contournement? Comme un label-goto sous la couverture qui saute juste au début de l'appel de la méthode avec de nouvelles valeurs pour les arguments? Ce serait une optimisation à la compilation et n'aurait pas besoin de décaler les trames de la pile ou de causer des violations de la sécurité.
James Watkins
2
Ce sera beaucoup mieux pour nous si vous ou quelqu'un d’autre ici pouvez aller plus loin et expliquer précisément ce que sont ces "méthodes sensibles à la sécurité". Je vous remercie!
InformedA
3
@InstructedA - voir securingjava.com/chapter-three/chapter-three-6.html qui contient une description détaillée de la façon dont le système Manager Java Security a travaillé vers la version de Java 2.
Jules
3
Une solution consiste à utiliser un autre langage JVM. Scala, par exemple, fait cela dans le compilateur, pas au moment de l'exécution.
James Moore
24

Java n’a pas l’optimisation des appels de queues pour la même raison que la plupart des langages impératifs ne l’ont pas. Les boucles impératives sont le style préféré du langage et le programmeur peut remplacer la récursion de la queue par des boucles impératives. La complexité n'en vaut pas la peine pour une fonctionnalité dont l'utilisation est découragée par une question de style.

Cette chose dans laquelle les programmeurs voulaient parfois écrire dans un style FP dans des langages sinon impératifs n’était à la mode que depuis une dizaine d’années, après que les ordinateurs ont commencé à s’intégrer dans des cœurs au lieu de GHz. Même maintenant, ce n'est pas si populaire. Si je proposais de remplacer une boucle impérative par une récursion de la queue au travail, la moitié des réviseurs de code riraient et l'autre moitié donnerait un regard confus. Même en programmation fonctionnelle, vous évitez généralement la récursion de la queue, à moins que d'autres constructions, telles que les fonctions d'ordre supérieur, ne s'emboîtent mal.

Karl Bielefeldt
la source
36
Cette réponse ne semble pas juste. Le fait que la récursion de la queue ne soit pas strictement nécessaire ne signifie pas que cela ne serait pas utile. Les solutions récursives sont souvent plus faciles à comprendre que les itérations, mais le manque d'appels en bout de ligne signifie que les algorithmes récursifs deviennent incorrects pour les problèmes de grande taille qui feraient exploser la pile. C’est une question de correction, pas de performance (la vitesse de négociation pour la simplicité en vaut souvent la peine). Comme la réponse correcte l'indique, l'absence d'appels de queue est due à un modèle de sécurité étrange reposant sur des traces de pile, et non à une bigoterie impérative.
amon
4
@amon James Gosling a déclaré un jour qu'il ne pourrait pas ajouter une fonctionnalité à Java à moins que plusieurs personnes ne l'aient demandée , et c'est seulement à ce moment-là qu'il l' examinerait . Donc, je ne serais pas surpris si une partie de la réponse était vraiment "tu peux toujours utiliser une forboucle" (et de même pour les fonctions de première classe vs les objets). Je n'irais pas jusqu'à qualifier cela de "bigoterie impérative" mais je ne pense pas que cela aurait été très demandé en 1995 alors que la principale préoccupation était probablement la vitesse de Java et le manque de médicaments génériques.
Doval
7
@amon, un modèle de sécurité me semble être une raison légitime de ne pas ajouter de coût total de possession à une langue préexistante, mais une mauvaise raison de ne pas l'inclure dans la langue. Vous ne jetez pas une fonctionnalité majeure visible par le programmateur afin d'inclure une fonctionnalité mineure en coulisse. "Pourquoi Java 8 n'a-t-il pas de TCO?" Est une question très différente de "Pourquoi Java 1.0 n'a-t-il pas de TCO?" Je répondais à ce dernier.
Karl Bielefeldt
3
@ rwong, vous pouvez transformer n'importe quelle fonction récursive en une fonction itérative. (Si vous me le permettez, j’ai écrit un exemple ici )
alain
3
@ZanLynx cela dépend du type de problème. Par exemple, la configuration des visiteurs peut bénéficier du coût total de possession (en fonction des spécificités de la structure et du visiteur) sans rien avoir à faire avec la PF. Passer par des machines à états est similaire bien que la transformation à l'aide de trampolines semble légèrement plus naturelle (selon le problème) Aussi, bien que techniquement, vous puissiez implémenter des arbres en utilisant des boucles, je pense que le consensus est que la récursion est beaucoup plus naturelle (similaire pour DFS bien que dans ce cas, vous pouvez éviter la récursivité en raison des limites de pile, même avec le TCO).
Maciej Piechotka
5

Java n’offre pas d’optimisation d’appel en hauteur, car la machine virtuelle Java n’a pas de code-octet pour les appels en aval (vers un pointeur de fonction inconnu , par exemple, une méthode dans une vtable).

Il semble que pour des raisons sociales (et peut-être techniques), l'ajout d'une nouvelle opération de code intermédiaire dans la machine virtuelle Java (ce qui la rendrait incompatible avec les versions précédentes de cette machine virtuelle) est terriblement difficile pour le propriétaire de la spécification de la machine virtuelle.

Les raisons techniques pour ne pas ajouter de nouveau bytecode dans les spécifications de la machine virtuelle Java incluent le fait que les implémentations réelles de la machine virtuelle Java sont des composants logiciels extrêmement complexes (en raison, par exemple, de nombreuses optimisations JIT).

Les appels en queue vers une fonction inconnue requièrent le remplacement du cadre de pile actuel par un nouveau et cette opération doit être effectuée dans la machine virtuelle (il ne s’agit pas uniquement de changer le compilateur générant du code intermédiaire).

Basile Starynkevitch
la source
17
La question ne concerne pas les appels de queue, mais la récursion de la queue. Et la question ne concerne pas le langage de bytecode JVM, mais le langage de programmation Java, qui est un langage complètement différent. Scala compile en bytecode JVM (entre autres) et a une élimination de la récursion de la queue. Les implémentations de schéma sur la machine virtuelle Java ont des appels de queue propres et complets. Java 7 (JVM Spec, 3rd Ed.) A ajouté un nouveau bytecode. La JVM J9 d’IBM exécute le TCO même sans recourir à un bytecode spécial.
Jörg W Mittag
1
@ JörgWMittag: C'est vrai, mais ensuite, je me demande s'il est vraiment vrai que le langage de programmation Java n'a pas d'appels de fin appropriés. Il serait peut-être plus exact d'affirmer que le langage de programmation Java n'a pas besoin d'appels de fin appropriés, car rien dans la spécification ne le prescrit. (C'est: Je ne suis pas sûr que rien dans la spécification effectivement interdit une mise en œuvre de l' élimination des appels de la queue Il est tout simplement pas mentionné..)
ruakh
4

Sauf si une langue a une syntaxe spéciale pour effectuer un appel final (récursif ou autre) et qu'un compilateur craquera lorsqu'un appel final est demandé mais ne peut pas être généré, l'optimisation "optionnelle" de l'appel final ou de la récursion générera des situations dans lesquelles une pièce de code peut nécessiter moins de 100 octets de pile sur une machine, mais plus de 100 000 000 octets de pile sur une autre. Une telle différence devrait être considérée comme qualitative plutôt que simplement quantitative.

On s'attend à ce que les machines aient des tailles de pile différentes et il est donc toujours possible que le code fonctionne sur une machine, mais bloque la pile sur une autre. Cependant, en règle générale, le code qui fonctionne sur une machine même lorsque la pile est artificiellement restreinte fonctionnera probablement sur toutes les machines avec des tailles de pile "normales". Toutefois, si une méthode récurrente 1 000 000 de profondeur est optimisée en appel final sur une machine, mais pas sur une autre, l'exécution sur la première machine fonctionnera probablement même si sa pile est exceptionnellement petite et échouera sur cette dernière même si sa pile est exceptionnellement grande. .

supercat
la source
2

Je pense que la récursion d'appels en queue n'est pas utilisée en Java principalement parce que cela altérerait les traces de la pile et rendrait donc le débogage d'un programme beaucoup plus difficile. Je pense que l'un des principaux objectifs de Java est de permettre aux programmeurs de facilement déboguer leur code, et le traçage des piles est essentiel pour le faire, en particulier dans un environnement de programmation fortement orienté objet. Etant donné que l'itération pourrait être utilisée à la place, le comité de langue a dû se rendre compte qu'il ne valait pas la peine d'ajouter une récursion de la queue.

ennuyeux
la source