Quand il n'y a pas de TCO, quand s'inquiéter de souffler la pile?

14

Chaque fois qu'il y a une discussion sur un nouveau langage de programmation ciblant la JVM, il y a inévitablement des gens qui disent des choses comme:

"La JVM ne prend pas en charge l'optimisation des appels de queue, donc je prédis beaucoup de piles explosives"

Il existe des milliers de variations sur ce thème.

Maintenant, je sais que certains langages, comme Clojure par exemple, ont une construction récurrente spéciale que vous pouvez utiliser.

Ce que je ne comprends pas, c'est: quelle est la gravité du manque d'optimisation des appels de queue? Quand devrais-je m'en inquiéter?

Ma principale source de confusion vient probablement du fait que Java est l'un des langages les plus réussis de tous les temps et que bon nombre des langages JVM semblent plutôt bien fonctionner. Comment est - ce possible si le manque de TCO est vraiment de toute préoccupation?

Cedric Martin
la source
4
si vous avez une récursion assez profonde pour faire exploser la pile sans TCO, alors vous aurez un problème même avec TCO
ratchet freak
18
@ratchet_freak C'est absurde. Scheme n'a même pas de boucles, mais parce que la spécification requiert la prise en charge du TCO, l'itération récursive sur un grand ensemble de données n'est pas plus chère qu'une boucle impérative (avec le bonus que la construction Scheme renvoie une valeur).
itsbruce
6
@ratchetfreak TCO est un mécanisme permettant de rendre les fonctions récursives écrites d'une certaine manière (c'est-à-dire de manière récursive) complètement incapables de faire exploser la pile même si elles le voulaient. Votre déclaration n'a de sens que pour la récursivité qui n'est pas écrite de manière récursive, auquel cas vous avez raison et le TCO ne vous aidera pas.
Evicatos
2
La dernière fois que j'ai regardé, le 80x86 ne fait pas non plus d'optimisation des appels (natifs). Mais cela n'a pas empêché les développeurs de langages de porter des langages qui l'utilisent. Le compilateur identifie quand il peut utiliser un saut par rapport à un jsr, et tout le monde est content. Vous pouvez faire la même chose sur une JVM.
kdgregory
3
@kdgregory: Mais le x86 a GOTO, pas la JVM. Et x86 n'est pas utilisé comme plateforme d'interopérabilité. La JVM n'a pas GOTOet l'une des principales raisons de choisir la plate-forme Java est l'interopérabilité. Si vous souhaitez implémenter TCO sur la JVM, vous devez faire quelque chose pour la pile. Gérez-le vous-même (c'est-à-dire n'utilisez pas du tout la pile d'appels JVM), utilisez des trampolines, utilisez des exceptions comme GOTO, quelque chose comme ça. Dans tous ces cas, vous devenez incompatible avec la pile d'appels JVM. Il est impossible d'être compatible avec la pile avec Java, d'avoir un TCO et de hautes performances. Vous devez sacrifier l'un de ces trois.
Jörg W Mittag

Réponses:

16

Considérez ceci, disons que nous nous sommes débarrassés de toutes les boucles en Java (les rédacteurs du compilateur sont en grève ou quelque chose). Maintenant, nous voulons écrire factorielle, donc nous pourrions corriger quelque chose comme ça

int factorial(int i){ return factorial(i, 1);}
int factorial(int i, int accum){
  if(i == 0) return accum;
  return factorial(i-1, accum * i);
}

Maintenant, nous nous sentons assez intelligents, nous avons réussi à écrire notre factorielle même sans boucles! Mais lorsque nous testons, nous remarquons qu'avec un nombre de taille raisonnable, nous obtenons des erreurs de stackoverflow car il n'y a pas de TCO.

En vrai Java, ce n'est pas un problème. Si jamais nous avons un algorithme récursif de queue, nous pouvons le transformer en boucle et être très bien. Mais qu'en est-il des langues sans boucles? Ensuite, vous êtes juste arrosé. C'est pourquoi clojure a cette recurforme, sans elle, elle n'est même pas complète (pas moyen de faire des boucles infinies).

La classe des langages fonctionnels qui ciblent la JVM, Frege, Kawa (Scheme), Clojure essaient toujours de faire face au manque d'appels de queue, car dans ces langages, TC est la façon idiomatique de faire des boucles! S'il était traduit en schéma, ce factoriel ci-dessus serait un bon factoriel. Ce serait extrêmement gênant si une boucle 5000 fois faisait planter votre programme. Cela peut être contourné cependant, avec recurdes formulaires spéciaux, des annotations faisant allusion à l'optimisation des appels personnels, au trampoline, etc. Mais ils forcent tous des résultats de performance ou un travail inutile sur le programmeur.

Maintenant, Java n'est pas non plus gratuit, car il y a plus de TCO que de récursivité, qu'en est-il des fonctions mutuellement récursives? Ils ne peuvent pas être directement traduits en boucles, mais ne sont toujours pas optimisés par la JVM. Cela rend spectaculairement désagréable d'essayer d'écrire des algorithmes en utilisant la récursivité mutuelle en utilisant Java car si vous voulez des performances / plage décentes, vous devez faire de la magie noire pour qu'il s'intègre dans les boucles.

Donc, en résumé, ce n'est pas énorme pour de nombreux cas. La plupart des appels de queue ne se déroulent que sur un stackframe profond, avec des choses comme

return foo(bar, baz); // foo is just a simple method

ou sont récursives. Cependant, pour la classe de TC qui ne correspond pas à cela, chaque langage JVM ressent la douleur.

Cependant, il y a une bonne raison pour laquelle nous n'avons pas encore de TCO. La JVM nous donne des traces de pile. Avec le TCO, nous éliminons systématiquement les stackframes que nous savons "condamnés", mais la JVM pourrait en fait en avoir besoin plus tard pour une trace de stack! Imaginons que nous implémentions un FSM comme celui-ci, où chaque état appelle le suivant. Nous effacerions tous les enregistrements des états précédents afin qu'un retraçage nous montre quel état, mais rien sur la façon dont nous y sommes arrivés.

De plus, et de manière plus urgente, une grande partie de la vérification du bytecode est basée sur la pile, éliminant la chose qui nous permet de vérifier que le bytecode n'est pas une perspective agréable. Entre cela et le fait que Java possède des boucles, le TCO semble un peu plus difficile que cela ne vaut aux ingénieurs JVM.

Daniel Gratzer
la source
2
Le plus gros problème est le vérificateur de code d'octet, qui est entièrement basé sur l'inspection de la pile. C'est un bogue majeur dans la spécification JVM. Il y a 25 ans, lorsque la JVM a été conçue, les gens ont déjà dit qu'il serait préférable d'avoir le langage de code d'octet JVM pour être sûr en premier lieu plutôt que d'avoir ce langage dangereux et de s'appuyer sur la vérification de code d'octet après coup. Cependant, Matthias Felleisen (l'une des figures de proue de la communauté Scheme) a écrit un article démontrant comment les appels de queue peuvent être ajoutés à la JVM tout en préservant le vérificateur de code d'octets.
Jörg W Mittag
2
Fait intéressant, la machine virtuelle Java par IBM J9 n'effectue TCO.
Jörg W Mittag
1
@jozefg Fait intéressant, personne ne se soucie des entrées stacktrace pour les boucles, donc l'argument stacktrace ne tient pas la route, du moins pour les fonctions récursives de queue.
Ingo
2
@MasonWheeler C'est exactement mon point: le stacktrace ne vous dit pas dans quelle itération cela s'est produit. Vous ne pouvez le voir qu'indirectement, en inspectant les variables de boucle, etc. Alors pourquoi voudriez-vous plusieurs entrées de trace de pile hundert d'une fonction récursive de queue? Seul le dernier est intéressant! Et, comme avec les boucles, vous pouvez déterminer de quelle récursivité il s'agit en inspectant les variables locales, les valeurs des arguments, etc.
Ingo
3
@Ingo: Si une fonction ne se reproduit qu'avec elle-même, la trace de la pile peut ne pas montrer grand-chose. Si, cependant, un groupe de fonctions est mutuellement récursif, alors une trace de pile peut parfois montrer beaucoup.
supercat
7

Les optimisations des appels de queue sont principalement importantes en raison de la récursivité de queue. Cependant, il existe un argument expliquant pourquoi il est bon que la JVM n'optimise pas les appels de queue: lorsque TCO réutilise une partie de la pile, une trace de pile à partir d'une exception sera incomplète, ce qui rend le débogage un peu plus difficile.

Il existe des moyens de contourner les limites de la JVM:

  1. La récursivité de queue simple peut être optimisée en boucle par le compilateur.
  2. Si le programme est dans un style passant-continuation, alors il est trivial d'utiliser "trampoline". Ici, une fonction ne renvoie pas le résultat final, mais une suite qui est ensuite exécutée à l'extérieur. Cette technique permet à un rédacteur de compilateur de modéliser un flux de contrôle arbitrairement complexe.

Cela peut nécessiter un exemple plus large. Considérez un langage avec des fermetures (par exemple JavaScript ou similaire). On peut écrire la factorielle comme

def fac(n, acc = 1) = if (n <= 1) acc else n * fac(n-1, acc*n)

print fac(x)

Maintenant, nous pouvons le faire renvoyer un rappel à la place:

def fac(n, acc = 1) =
  if (n <= 1) acc
  else        (() => fac(n-1, acc*n))  // this isn't full CPS, but you get the idea…

var continuation = (() => fac(x))
while (continuation instanceof function) {
  continuation = continuation()
}
var result = continuation
print result

Cela fonctionne maintenant dans un espace de pile constant, ce qui est un peu idiot car il est récursif de toute façon. Cependant, cette technique est capable d'aplatir tous les appels de queue dans un espace de pile constant. Et si le programme est en CPS, cela signifie que la pile d'appels est globalement constante (en CPS, chaque appel est un appel de queue).

Un inconvénient majeur de cette technique est qu'elle est beaucoup plus difficile à déboguer, un peu plus difficile à implémenter et moins performante - voir toutes les fermetures et indirection que j'utilise.

Pour ces raisons, il serait largement préférable que la machine virtuelle implémente un appel de queue - les langages comme Java qui ont de bonnes raisons de ne pas prendre en charge les appels de queue n'auraient pas à l'utiliser.

amon
la source
1
"Comme TCO réutilise une partie de la pile, une trace de pile d'une exception sera incomplète", - oui, mais alors, une trace de pile à partir d'une boucle est incomplète non plus - elle n'enregistre pas la fréquence à laquelle la boucle a été exécutée. - Hélas, même si la JVM prendrait en charge les appels de queue appropriés, on pourrait toujours se retirer, pendant le débogage, par exemple. Et puis, pour la production, activez TCO pour être sûr que le code s'exécute avec 100 000 ou 100 000 000 appels de queue.
Ingo
1
@Ingo No. (1) Lorsque les boucles ne sont pas implémentées comme récursivité, il n'y a aucune raison pour qu'elles apparaissent sur la pile (appel de queue, saut, appel). (2) Le TCO est plus général que l'optimisation de récursivité de queue. Ma réponse utilise la récursivité comme exemple . (3) Si vous programmez dans un style qui repose sur le TCO, la désactivation de cette optimisation n'est pas une option - le TCO complet ou les traces de pile complètes sont soit une fonctionnalité de langue, soit elles ne le sont pas. Par exemple, Scheme parvient à équilibrer les inconvénients du TCO avec un système d'exception plus avancé.
amon
1
(1) entièrement d'accord. Mais par le même raisonnement, il n'y a aucune raison de garder des centaines et des milliers d'entrées de trace de pile qui pointent toutes return foo(....);dans la méthode foo(2), bien sûr. Néanmoins, nous acceptons le suivi incomplet des boucles, des affectations (!), Des séquences d'instructions. Par exemple, si vous trouvez une valeur inattendue dans une variable, vous voulez sûrement savoir comment elle y est arrivée. Mais vous ne vous plaignez pas de manquer de traces dans ce cas. Parce qu'il est en quelque sorte gravé dans notre cerveau que a) cela se produit uniquement sur les appels b) cela se produit sur tous les appels. Les deux n'ont aucun sens, à mon humble avis.
Ingo
(3) Pas d'accord. Je ne vois aucune raison pour laquelle il devrait être impossible de déboguer mon code avec un problème de taille N, pour certains N suffisamment petits pour s'en tirer avec la pile normale. Et puis, pour activer l'interrupteur et activer le TCO - en supprimant efficacement la contrainte sur la taille du probem.
Ingo
@Ingo “Pas d'accord. Je ne vois aucune raison pour laquelle il devrait être impossible de déboguer mon code avec un problème de taille N, pour certains N suffisamment petits pour s'en tirer avec la pile normale. »Si TCO / TCE est pour une transformation CPS, puis le tourner off débordera la pile et plantera le programme, donc aucun débogage ne serait possible. Google a refusé d'implémenter le TCO dans V8 JS, en raison de ce problème accidentel . Ils voudraient une syntaxe spéciale pour que le programmeur puisse déclarer qu'il veut vraiment le TCO et la perte de la trace de la pile. Est-ce que quelqu'un sait si les exceptions sont également ratées par TCO?
Shelby Moore III
6

Une partie importante des appels dans un programme sont des appels de queue. Chaque sous-programme a un dernier appel, donc chaque sous-programme a au moins un appel de queue. Les appels de queue ont les caractéristiques de performance GOTOmais la sécurité d'un appel de sous-programme.

Avoir des appels de queue appropriés vous permet d'écrire des programmes que vous ne pourriez pas écrire autrement. Prenons, par exemple, une machine d'état. Une machine à états peut être implémentée très directement en faisant de chaque état un sous-programme et de chaque transition d'état un appel de sous-programme. Dans ce cas, vous passez d'un état à l'autre, en faisant appel après appel après appel, et vous ne revenez jamais ! Sans appels de queue appropriés, vous exploseriez immédiatement la pile.

Sans PTC, vous devez utiliser des GOTOtrampolines ou des exceptions comme flux de contrôle ou quelque chose comme ça. C'est beaucoup plus laid, et pas tellement une représentation 1: 1 directe de la machine d'état.

(Notez comment j'ai habilement évité d'utiliser l'exemple ennuyeux de "boucle". C'est un exemple où les PTC sont utiles même dans un langage avec des boucles.)

J'ai délibérément utilisé le terme «appels de queue appropriés» ici au lieu de TCO. TCO est une optimisation du compilateur. PTC est une fonctionnalité de langage qui nécessite que chaque compilateur effectue le TCO.

Jörg W Mittag
la source
The vast majority of calls in a program are tail calls. Pas si "la grande majorité" des méthodes appelées effectuent plus d'un appel. Every subroutine has a last call, so every subroutine has at least one tail call. Ceci est trivialement démontrables faux: return a + b. (Sauf si vous êtes dans un langage insensé où les opérations arithmétiques de base sont définies comme des appels de fonction, bien sûr.)
Mason Wheeler
1
"Ajouter deux nombres, c'est ajouter deux nombres." Sauf pour les langues où ce n'est pas le cas. Qu'en est-il de l'opération + en Lisp / Scheme où un seul opérateur arithmétique peut prendre un nombre arbitraire d'arguments? (+ 1 2 3) La seule façon saine d'implémenter cela est en fonction.
Evicatos
1
@Mason Wheeler: Qu'entendez-vous par inversion d'abstraction?
Giorgio
1
@MasonWheeler C'est, sans aucun doute, l'entrée Wikipedia la plus ondulée sur un sujet technique que j'ai jamais vue. J'ai vu des entrées douteuses mais c'est juste ... wow.
Evicatos
1
@MasonWheeler: Parlez-vous des fonctions de longueur de liste aux pages 22 et 23 de On Lisp? La version tail-call est environ 1,2 fois plus compliquée, loin de 3x. Je ne sais pas non plus ce que vous entendez par inversion d'abstraction.
Michael Shaw
4

"La JVM ne prend pas en charge l'optimisation des appels de queue, donc je prédis beaucoup de piles explosives"

Quiconque dit cela (1) ne comprend pas l'optimisation des appels de queue, ou (2) ne comprend pas la JVM, ou (3) les deux.

Je vais commencer par la définition des appels de queue de Wikipedia (si vous n'aimez pas Wikipedia, voici une alternative ):

En informatique, un appel de queue est un appel de sous-programme qui se produit à l'intérieur d'une autre procédure comme son action finale; il peut produire une valeur de retour qui est ensuite immédiatement renvoyée par la procédure d'appel

Dans le code ci-dessous, l'appel à bar()est l'appel final de foo():

private void foo() {
    // do something
    bar()
}

L'optimisation des appels de queue se produit lorsque l'implémentation du langage, voyant un appel de queue, n'utilise pas l'invocation de méthode normale (qui crée un cadre de pile), mais crée plutôt une branche. Il s'agit d'une optimisation car une trame de pile nécessite de la mémoire, et elle nécessite des cycles CPU pour pousser des informations (telles que l'adresse de retour) sur la trame, et parce que la paire appel / retour est supposée nécessiter plus de cycles CPU qu'un saut inconditionnel.

Le TCO est souvent appliqué à la récursivité, mais ce n'est pas sa seule utilisation. Elle n'est pas non plus applicable à toutes les récursions. Le code récursif simple pour calculer une factorielle, par exemple, ne peut pas être optimisé pour les appels de queue, car la dernière chose qui se produit dans la fonction est une opération de multiplication.

public static int fact(int n) {
    if (n <= 1) return 1;
    else return n * fact(n - 1);
}

Pour implémenter l'optimisation des appels de queue, vous avez besoin de deux choses:

  • Une plate-forme qui prend en charge la branche en plus des appels de sous-routine.
  • Un analyseur statique qui peut déterminer si l'optimisation des appels de queue est possible.

C'est ça. Comme je l'ai noté ailleurs, la JVM (comme toute autre architecture complète de Turing) a un goto. Il se trouve qu'il a un goto inconditionnel , mais la fonctionnalité pourrait facilement être implémentée à l'aide d'une branche conditionnelle.

L'élément d'analyse statique est ce qui est délicat. Dans une seule fonction, ce n'est pas un problème. Par exemple, voici une fonction Scala récursive de queue pour additionner les valeurs dans a List:

def sum(acc:Int, list:List[Int]) : Int = {
  if (list.isEmpty) acc
  else sum(acc + list.head, list.tail)
}

Cette fonction se transforme en le bytecode suivant:

public int sum(int, scala.collection.immutable.List);
  Code:
   0:   aload_2
   1:   invokevirtual   #63; //Method scala/collection/immutable/List.isEmpty:()Z
   4:   ifeq    9
   7:   iload_1
   8:   ireturn
   9:   iload_1
   10:  aload_2
   11:  invokevirtual   #67; //Method scala/collection/immutable/List.head:()Ljava/lang/Object;
   14:  invokestatic    #73; //Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
   17:  iadd
   18:  aload_2
   19:  invokevirtual   #76; //Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
   22:  checkcast   #59; //class scala/collection/immutable/List
   25:  astore_2
   26:  istore_1
   27:  goto    0

Notez le goto 0à la fin. Par comparaison, une fonction Java équivalente (qui doit utiliser un Iteratorpour imiter le comportement de rupture d'une liste Scala en tête et en queue) se transforme en le bytecode suivant. Notez que les deux dernières opérations sont maintenant un appel , suivi d'un retour explicite de la valeur produite par cet appel récursif.

public static int sum(int, java.util.Iterator);
  Code:
   0:   aload_1
   1:   invokeinterface #64,  1; //InterfaceMethod java/util/Iterator.hasNext:()Z
   6:   ifne    11
   9:   iload_0
   10:  ireturn
   11:  iload_0
   12:  aload_1
   13:  invokeinterface #70,  1; //InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
   18:  checkcast   #25; //class java/lang/Integer
   21:  invokevirtual   #74; //Method java/lang/Integer.intValue:()I
   24:  iadd
   25:  aload_1
   26:  invokestatic    #43; //Method sum:(ILjava/util/Iterator;)I
   29:  ireturn

L' optimisation des appels queue d'une seule fonction est trivial: le compilateur peut voir qu'il n'y a pas de code qui utilise le résultat de l'appel, il peut donc remplacer le Invoke avec goto.

Là où la vie devient difficile, c'est si vous avez plusieurs méthodes. Les instructions de branchement de la JVM, contrairement à celles d'un processeur à usage général tel que le 80x86, se limitent à une seule méthode. C'est encore relativement simple si vous avez des méthodes privées: le compilateur est libre de les intégrer comme il convient, donc peut optimiser les appels de queue (si vous vous demandez comment cela pourrait fonctionner, envisagez une méthode courante qui utilise un switchpour contrôler le comportement). Vous pouvez même étendre cette technique à plusieurs méthodes publiques dans la même classe: le compilateur insère les corps de méthode, fournit des méthodes de pont public et les appels internes se transforment en sauts.

Mais, ce modèle tombe en panne lorsque vous considérez les méthodes publiques dans différentes classes, en particulier à la lumière des interfaces et des chargeurs de classe. Le compilateur de niveau source n'a tout simplement pas suffisamment de connaissances pour implémenter les optimisations d'appel de fin. Cependant, contrairement aux implémentations "bare-metal", la * JVM (a les informations pour le faire, sous la forme du compilateur Hotspot (du moins, l'ex-compilateur Sun en a). Je ne sais pas si elle fonctionne réellement optimisations de queue-appel, et ne soupçonnez pas, mais il pourrait .

Ce qui m'amène à la deuxième partie de votre question, que je reformulerai comme «devrions-nous nous en préoccuper?

De toute évidence, si votre langue utilise la récursivité comme unique primitive d'itération, vous vous en souciez. Mais, les langues qui ont besoin de cette fonctionnalité peuvent l'implémenter; le seul problème est de savoir si un compilateur pour ledit langage peut produire une classe qui peut appeler et être appelée par une classe Java arbitraire.

En dehors de ce cas, je vais inviter des votes négatifs en disant que cela n'a pas d'importance. La plupart du code récursif que j'ai vu (et j'ai travaillé avec beaucoup de projets de graphes) n'est pas optimisable en queue d'appel . Comme le factoriel simple, il utilise la récursivité pour construire l'état, et l'opération de queue est une combinaison.

Pour le code qui est optimisable par appel, il est souvent simple de traduire ce code sous une forme itérable. Par exemple, cette sum()fonction que j'ai montrée précédemment peut être généralisée comme foldLeft(). Si vous regardez la source , vous verrez qu'elle est en fait implémentée comme une opération itérative. Jörg W Mittag avait un exemple de machine d'état implémentée via des appels de fonction; il existe de nombreuses implémentations de machines à états efficaces (et maintenables) qui ne dépendent pas de la conversion d'appels de fonction en sauts.

Je terminerai avec quelque chose de complètement différent. Si vous recherchez votre chemin à partir des notes de bas de page dans le SICP, vous pourriez vous retrouver ici . Personnellement, je trouve que c'est un endroit beaucoup plus intéressant que de remplacer mon compilateur JSRpar JUMP.

kdgregory
la source
Si un opcode d'appel de queue existait, pourquoi l'optimisation de l'appel de queue exigerait autre chose que d'observer à chaque site d'appel si la méthode faisant l'appel devrait exécuter un code par la suite? Il se peut que dans certains cas, une instruction comme celle-ci return foo(123);puisse être mieux exécutée par in-lining fooque par génération de code pour manipuler la pile et effectuer un saut, mais je ne vois pas pourquoi l'appel de queue serait différent d'un appel ordinaire dans cet égard.
supercat
@supercat - Je ne sais pas quelle est votre question. Le premier point de cet article est que le compilateur ne peut pas savoir à quoi pourrait ressembler le cadre de pile de tous les callees potentiels (rappelez-vous que le cadre de pile contient non seulement les arguments de la fonction mais aussi ses variables locales). Je suppose que vous pouvez ajouter un opcode qui vérifie l'exécution des cadres compatibles, mais cela m'amène à la deuxième partie du message: quelle est la vraie valeur?
kdgregory