Pourquoi le nombre d'appels d'une méthode récursive provoquant une StackOverflowError varie-t-il entre les exécutions du programme ?

Question

Une classe simple à des fins de démonstration :

public class Main {

    private static int counter = 0;

    public static void main(String[] args) {
        try {
            f();
        } catch (StackOverflowError e) {
            System.out.println(counter);
        }
    }

    private static void f() {
        counter++;
        f();
    }
}

J'ai exécuté le programme ci-dessus 5 fois, les résultats sont :

22025
22117
15234
21993
21430

Pourquoi les résultats sont-ils différents à chaque fois ?

J'ai essayé de définir la taille maximale de la pile (par exemple -Xss256k ). Les résultats ont ensuite été un peu plus cohérents, mais une fois encore, ils n'étaient pas égaux à chaque fois.

Version Java :

java version "1.8.0_72"
Java(TM) SE Runtime Environment (build 1.8.0_72-b15)
Java HotSpot(TM) 64-Bit Server VM (build 25.72-b15, mixed mode)

EDITAR

Lorsque le JIT est désactivé ( -Djava.compiler=NONE ), j'obtiens toujours le même nombre ( 11907 ).

C'est logique, car les optimisations du JIT affectent probablement la taille des cadres de pile et le travail effectué par le JIT doit certainement varier entre les exécutions.

Néanmoins, je pense qu'il serait bénéfique que cette théorie soit confirmée par des références à de la documentation sur le sujet et/ou des exemples concrets du travail effectué par le JIT dans cet exemple spécifique qui conduit à des changements de taille de trame.

Answer 1

La variance observée est causée par compilation JIT en arrière-plan .

Voici à quoi ressemble le processus :

1. Méthode f() lance l'exécution dans l'interpréteur.
2. Après un certain nombre d'invocations (environ 250), la méthode est programmée pour la compilation.
3. Le thread du compilateur travaille en parallèle avec le thread de l'application. Pendant ce temps, la méthode continue son exécution dans l'interpréteur.
4. Dès que le thread du compilateur termine la compilation, le point d'entrée de la méthode est remplacé, de sorte que le prochain appel à la méthode f() invoquera la version compilée de la méthode.

Il y a essentiellement une course entre le fil d'applcation et le fil du compilateur JIT. L'interpréteur peut effectuer un nombre différent d'appels avant que la version compilée de la méthode soit prête. À la fin, il y a un mélange de trames interprétées et compilées.

Il n'est pas étonnant que la disposition des cadres compilés diffère de celle des cadres interprétés. Les cadres compilés sont généralement plus petits ; ils n'ont pas besoin de stocker tout le contexte d'exécution sur la pile (référence à la méthode, référence au pool de constantes, données du profileur, tous les arguments, variables d'expression, etc.)

En outre, les possibilités de course sont encore plus nombreuses avec Compilation par paliers (par défaut depuis le JDK 8). Il peut y avoir une combinaison de 3 types de cadres : interpréteur, C1 et C2 (voir ci-dessous).

---

Faisons quelques expériences amusantes pour étayer la théorie.

1. Mode interprété pur. Pas de compilation JIT.
   Pas de courses => résultats stables.

   $ java -Xint Main
   11895
   11895
   11895

2. Désactiver arrière-plan compilation. Le JIT est activé, mais il est synchronisé avec le thread de l'application.
   Pas de courses à nouveau, mais le nombre d'appels est maintenant plus élevé en raison des cadres compilés.

   $ java -XX:-BackgroundCompilation Main
   23462
   23462
   23462

3. Compilez tout avec C1 avant exécution. Contrairement au cas précédent, il n'y aura pas de trames interprétées sur la pile, donc le nombre sera un peu plus élevé.

   $ java -Xcomp -XX:TieredStopAtLevel=1 Main
   23720
   23720
   23720

4. Maintenant, compilez tout avec C2 avant exécution. Cela produira le code le plus optimisé avec le plus petit cadre. Le nombre d'appels sera le plus élevé.

   $ java -Xcomp -XX:-TieredCompilation Main
   59300
   59300
   59300

   La taille par défaut de la pile étant de 1M, cela devrait signifier que la trame ne fait plus que 16 octets. Est-ce le cas ?

   $ java -Xcomp -XX:-TieredCompilation -XX:CompileCommand=print,Main.f Main
   
     0x00000000025ab460: mov    %eax,-0x6000(%rsp)    ; StackOverflow check
     0x00000000025ab467: push   %rbp                  ; frame link
     0x00000000025ab468: sub    $0x10,%rsp            
     0x00000000025ab46c: movabs $0xd7726ef0,%r10      ; r10 = Main.class
     0x00000000025ab476: addl   $0x2,0x68(%r10)       ; Main.counter += 2
     0x00000000025ab47b: callq  0x00000000023c6620    ; invokestatic f()
     0x00000000025ab480: add    $0x10,%rsp
     0x00000000025ab484: pop    %rbp                  ; pop frame
     0x00000000025ab485: test   %eax,-0x23bb48b(%rip) ; safepoint poll
     0x00000000025ab48b: retq

   En fait, la trame est ici de 32 octets, mais le JIT a intégré un niveau de récursivité.

5. Enfin, examinons la trace de la pile mixte. Pour l'obtenir, nous allons planter la JVM sur StackOverflowError (option disponible dans les builds de débogage).

   $ java -XX:AbortVMOnException=java.lang.StackOverflowError Main

   La décharge de l'accident hs_err_pid.log contient la trace détaillée de la pile où l'on peut trouver les trames interprétées en bas, les trames C1 au milieu et enfin les trames C2 en haut.

   Java frames: (J=compiled Java code, j=interpreted, Vv=VM code)
   J 164 C2 Main.f()V (12 bytes) @ 0x00007f21251a5958 [0x00007f21251a5900+0x0000000000000058]
   J 164 C2 Main.f()V (12 bytes) @ 0x00007f21251a5920 [0x00007f21251a5900+0x0000000000000020]
     // ... repeated 19787 times ...
   J 164 C2 Main.f()V (12 bytes) @ 0x00007f21251a5920 [0x00007f21251a5900+0x0000000000000020]
   J 163 C1 Main.f()V (12 bytes) @ 0x00007f211dca50ec [0x00007f211dca5040+0x00000000000000ac]
   J 163 C1 Main.f()V (12 bytes) @ 0x00007f211dca50ec [0x00007f211dca5040+0x00000000000000ac]
     // ... repeated 1866 times ...
   J 163 C1 Main.f()V (12 bytes) @ 0x00007f211dca50ec [0x00007f211dca5040+0x00000000000000ac]
   j  Main.f()V+8
   j  Main.f()V+8
     // ... repeated 1839 times ...
   j  Main.f()V+8
   j  Main.main([Ljava/lang/String;)V+0
   v  ~StubRoutines::call_stub

Answer 2

Tout d'abord, ce qui suit n'a pas fait l'objet de recherches. Je n'ai pas "plongé" dans le code source d'OpenJDK pour valider ce qui suit, et je n'ai pas accès à des connaissances internes.

J'ai essayé de valider vos résultats en exécutant votre test sur ma machine :

$ java -version
openjdk version "1.8.0_71"
OpenJDK Runtime Environment (build 1.8.0_71-b15)
OpenJDK 64-Bit Server VM (build 25.71-b15, mixed mode)

Le "nombre" varie dans une fourchette de ~250. (Pas autant que ce que vous voyez)

Tout d'abord, un peu de contexte. Dans une implémentation Java typique, la pile d'un thread est une région contiguë de la mémoire qui est allouée avant le démarrage du thread, et qui n'est jamais agrandie ou déplacée. Un débordement de pile se produit lorsque la JVM tente de créer un cadre de pile pour effectuer un appel de méthode, et que le cadre dépasse les limites de la région de mémoire. Le test pourrait Il est possible de le faire en testant explicitement la PS, mais je crois comprendre que cela est normalement mis en œuvre en utilisant une astuce astucieuse avec les paramètres de la page mémoire.

Lorsqu'une région de pile est allouée, la JVM effectue un appel système pour demander au système d'exploitation de marquer une page de "zone rouge" à la fin de la région de pile en lecture seule ou non accessible. Lorsqu'un thread effectue un appel qui déborde de la pile, il accède à la mémoire dans la "zone rouge", ce qui déclenche un défaut de mémoire. Le système d'exploitation le signale à la JVM par le biais d'un "signal", et le gestionnaire de signaux de la JVM le fait correspondre à un fichier StackOverflowError qui est "jeté" sur la pile du thread.

Voici donc quelques possible des explications de la variabilité :

• La granularité de la protection matérielle de la mémoire est la limite de la page. Ainsi, si la pile de threads a été allouée en utilisant malloc le début de la région ne sera pas aligné sur la page. Par conséquent, la distance entre le début de la trame de la pile et le premier mot de la "zone rouge" (qui est >< alignée sur la page) va être variable.

• La pile "principale" est potentiellement spéciale, car cette région peut être utilisé pendant l'amorçage de la JVM. Cela peut conduire à ce que des "trucs" soient laissés sur la pile avant le démarrage de la JVM. main a été appelé. (Ce n'est pas convaincant... et je ne suis pas convaincu.)

Cela dit, la "grande" variabilité que vous observez est déconcertante. La taille des pages est trop petite pour expliquer une différence de ~7000 dans les comptages.

UPDATE

Lorsque le JIT est désactivé (-Djava.compiler=NONE), j'obtiens toujours le même chiffre (11907).

Intéressant. Entre autres choses, cela pourrait faire en sorte que la vérification des limites de la pile soit faite différemment.

C'est logique, car les optimisations du JIT affectent probablement la taille des cadres de pile et le travail effectué par le JIT doit certainement varier entre les exécutions.

Plausible. La taille du cadre d'empilement pourrait bien être différente après le f() a été compilé en JIT. En supposant que f() a été compilé en JIT à un moment donné, votre pile aura un mélange d'"anciennes" et de "nouvelles" images. Si la compilation JIT a eu lieu à des moments différents, alors le rapport sera différent ... et donc l'indicateur count sera différent lorsque vous atteindrez la limite.

Néanmoins, je pense qu'il serait bénéfique que cette théorie soit confirmée par des références à de la documentation sur le sujet et/ou des exemples concrets du travail effectué par le JIT dans cet exemple spécifique qui conduit à des changements de taille de trame.

Il y a peu de chances que cela arrive, j'en ai peur... à moins que vous ne soyez prêt à PAYER quelqu'un pour faire quelques jours de recherche pour vous.

1) Aucune documentation de référence (publique) de ce type n'existe, AFAIK. Du moins, je n'ai jamais été capable de trouver une source définitive pour ce genre de chose ... à part une plongée profonde dans le code source.

2) L'examen du code compilé en JIT ne vous dit rien sur la façon dont l'interpréteur de bytecode traitait les choses avant que le code ne soit compilé en JIT. Ainsi, vous ne serez pas en mesure de voir si la taille de l'image a été modifiée. modifié .

Answer 3

Le fonctionnement exact de la pile Java n'est pas documenté, mais il dépend totalement de la mémoire allouée à ce thread.

Essayez simplement d'utiliser le constructeur de Thread avec stacksize et voyez si cela devient constant. Je ne l'ai pas essayé, alors partagez les résultats.