Articles

Voir l’Analyse d’échappement Fonctionner

Posted on

Vous avez peut-être entendu parler d’une phase d’analyse du compilateur appelée analyse d’échappement. Il informe une optimisation appelée remplacement scalaire des agrégats qui supprime l’allocation inutile d’objets Java. Je trouve que les gens ont souvent une incompréhension de ce que cette optimisation fait vraiment et une sous-appréciation de ce dont elle est capable. Nous pouvons mieux le connaître en le voyant fonctionner dans la pratique.

Contexte

Je vais montrer comment le compilateur GraalVM, dans le cadre de GraalVM et configuré pour la compilation juste à temps dans la configuration hébergée, applique l’analyse d’échappement et le remplacement scalaire des agrégats. Le compilateur GraalVM est plus puissant à cet égard que le compilateur juste à temps le plus courant auquel vous êtes probablement habitué, C2 dans HotSpot.

Notez que chaque fois que je dis compilateur dans cet article, je veux dire compilation juste à temps, donc le genre de compilation qui se produit à l’exécution dans la JVM. Je ne parle pas du compilateur javac.

Je vais montrer comment le compilateur comprend nos exemples de programmes en examinant l’une des structures de données qu’il utilise lors de la compilation, sa représentation intermédiaire supérieure. Il s’agit d’un graphique qui capture la signification d’un programme Java tel qu’il est optimisé et transformé avant le début de la conversion en code machine. Cela semble probablement très avancé, mais je pense que pour la plupart des personnes ayant une certaine expérience de Java, c’est en fait un moyen assez accessible de comprendre ce que fait le compilateur.

Cette représentation intermédiaire est différente d’un arbre syntaxique abstrait, ou AST, qui est une représentation syntaxique du texte de votre programme. Il est également différent d’un graphe d’appel, qui vous indique simplement quelles méthodes appellent quelles autres méthodes.

J’utiliserai un outil appelé Seafoam, de l’équipe d’implémentation du langage de Shopify, pour créer des diagrammes des structures de données déversées hors de Graal. Vous pouvez également utiliser un outil appelé Visualiseur de graphique idéal d’Oracle Labs.

Terminologie

L’analyse d’échappement est un processus d’analyse. Il détecte si un objet est visible en dehors d’une unité de compilation (une unité de compilation est généralement une méthode plus toutes les autres méthodes qui y sont intégrées.) Un objet peut devenir visible en dehors d’une unité de compilation en étant renvoyé, ou passé en argument à une autre méthode, ou écrit dans un champ, ou similaire.

Le remplacement scalaire des agrégats utilise le résultat de l’analyse d’échappement et fonctionne sur des objets qui n’échappent pas à l’unité de compilation, ou ne l’échappent que sur certaines branches. Il remplace les objets (agrégats) par des valeurs simples (scalaires) similaires aux variables locales. Nous verrons cela plus concrètement plus tard.

Allocation d’objet

Nous allons travailler avec une classe simple Vector qui contient les champs double x et y. Il a un constructeur, des getters et une méthode add qui renvoie un nouvel objet qui est ce Vector ajouté à un autre.

J’ai une méthode main qui exécute une boucle et appelle une méthode

sum

qui utilise

add

pour additionner deux vecteurs générés aléatoirement. La boucle est là pour obtenir le code suffisamment chaud pour déclencher la compilation juste à temps, la randomisation est là pour que les valeurs ne soient pas profilées pour être effectivement constantes, et la méthode sum séparée est là pour créer un bloc de code soigné à regarder lorsque vous regardez comment le code est compilé.

Je vais compiler et exécuter cela en utilisant GraalVM CE sur Java 8 20.3.0 sur macOS sur AMD64. Je désactive une optimisation appelée remplacement sur pile car cette optimisation rend la compilation un peu plus compliquée et plus difficile à comprendre. J’utilise ensuite l’option

dump

de Graal pour lui demander de vider ses structures de données de représentation intermédiaires.

Nous pouvons maintenant utiliser Seafoam pour voir comment le compilateur comprend la méthode sum, juste avant d’exécuter l’analyse d’échappement. Le fichier sum.bgv contient la structure de données que le compilateur a vidée pour nous.

% seafoam sum.bgv:14 render

Que voyons-nous ici? Ce graphique est la façon dont Graal comprend la méthode sum pendant qu’il la compile. C’est du code Java, mais libre des contraintes d’une représentation textuelle. Les opérations sont représentées sous forme de nœuds (les cases, les losanges et les ovales) et les relations entre les opérations sont représentées sous forme d’arêtes (les flèches). La flèche rouge épaisse signifie qu’une opération doit se produire avant une autre. La flèche plus fine signifie que la sortie de l’opération est utilisée comme entrée d’une autre opération.

Nous avons dit que le programme était libéré des contraintes d’une représentation textuelle. Regardez l’opération add dans le nœud 14 par exemple. Nous savons que cela doit se produire après le chargement des deux valeurs des deux champs x et avant de stocker la valeur dans le champ x dans le nœud 19, mais peu nous importe que cela se produise avant ou après le chargement des deux champs y. Dans le code source textuel Java, tout est écrit dans un ordre linéaire. Le graphique détend cette contrainte et code uniquement les contraintes que la spécification du langage Java nécessite réellement. Le compilateur est alors libre de choisir l’ordre final dans lequel tout s’exécute.

En lisant ce graphique, nous pouvons voir que nous créons un nouveau Vector, puis chargeons les champs x et y des deux objets d’entrée, les ajoutons ensemble puis les stockons dans le nouveau Vector que nous avons créé avant de le renvoyer. Il y a quelques détails supplémentaires dans le graphique, tels que la vérification null, la barrière de champ finale, et plus encore, car il s’agit d’un véritable graphique de compilateur, mais nous les ignorerons pour cet article pour le garder court.

La chose clé à voir ici maintenant est qu’il y a un point précis où le nouvel objet Vector est créé.

Remplacement scalaire de base

Examinons la même méthode juste après l’exécution de l’analyse d’échappement et du remplacement scalaire des agrégats.

% seafoam sum.bgv:15 render

Maintenant, le graphique a été encore plus détendu de la façon dont il apparaît dans le texte. Au lieu d’une opération New Vector, nous l’avons maintenant décomposée en une opération générique pour allouer un objet, en prenant la valeur des champs de cet objet. Il n’y a plus StoreField ici.

Dans cette méthode particulière, cela n’a rien d’utile – le graphique a été détendu mais il n’a révélé aucune optimisation vraiment utile. En effet, le seul objet que nous avons alloué doit vraiment être alloué car il quitte la méthode. L’analyse d’échappement a été exécutée mais l’objet s’est échappé, il n’y a donc pas eu de remplacement scalaire des agrégats.

Pour aller plus loin, regardons une méthode qui somme trois objets Vector.

private static Vector sum(Vector a, Vector b, Vector c) {return a.add(b).add(c);}

Le graphique avant l’analyse d’échappement et le remplacement scalaire des agrégats a la même structure que la méthode précédente. Nous avons deux opérations New Vector. Le résultat de a.add(b) est écrit dans le premier nouvel objet, puis lu à nouveau pour le .add(c) suivant. Nous pouvons voir à quel point cela est inutile – l’objet intermédiaire n’est jamais visible en dehors de l’unité de compilation car il n’est ni stocké ni transmis nulle part – alors pourquoi l’allouer et pourquoi y stocker des champs que nous venons de relire immédiatement?

Si nous regardons le graphique après l’analyse d’échappement et le remplacement scalaire des agrégats, nous voyons que l’intermédiaire Vector a été entièrement supprimé. Il n’y en a qu’un Alloc, pas deux. L’agrégat des champs de l’objet intermédiaire a été remplacé par les valeurs scalaires des arêtes reliant directement le producteur et le consommateur, sans faire un intermédiaire StoreField puis LoadField.

L’efficacité du remplacement scalaire

Quelques exemples supplémentaires montreront à quel point cette optimisation est un peu plus puissante que ce que l’on suppose souvent.

Si nous additionnons un tableau d’objets Vector, nous en créerons logiquement un Vector par itération.

private static Vector sum(Vector first, Vector... rest) {Vector sum = first;for (Vector vector : rest) {sum = sum.add(vector);}return sum;}

Ce graphique est maintenant assez compliqué, mais le point clé est que vous pouvez voir une opération New Vector à l’intérieur de la boucle (à l’intérieur du cercle formé de flèches rouges épaisses.)

Après une analyse d’échappement partielle et un remplacement scalaire des agrégats exécutés, il n’y a plus New Vector à l’intérieur de la boucle. Il y a une seule allocation à la fin pour le Vector final qui est retourné, et les valeurs pour x et y sont accumulées en accumulant des valeurs (les petites boucles autour des nœuds 33 et 92, et des nœuds 36 et 93.) Cela signifie qu’aucune mémoire n’est plus allouée dans la boucle interne de cette méthode.

Parfois, les gens parlent d’objets qui n’échappent pas à une unité de compilation allouée sur la pile. Voici pourquoi c’est un malentendu. Cette méthode additionne deux objets Vector mais ne renvoie que le composant x.

private static double sumX(Vector a, Vector b) {return a.add(b).getX();}

Avant l’exécution de l’analyse d’échappement, cette méthode ressemble exactement à l’original sum, sauf que le champ x est ensuite chargé et renvoyé. Le champ y est stocké mais jamais utilisé, et l’intermédiaire Vector n’échappe pas à l’unité de compilation.

Après l’analyse d’échappement et le remplacement scalaire des agrégats, nous pouvons voir un point important à noter: après le remplacement de l’objet par des scalaires, il n’y avait pas de consommateur de la valeur y, donc le code pour le générer n’avait rien pour le connecter au graphique et il a donc été supprimé.

Si nous allouions littéralement l’objet sur la pile, stockant l’objet dans le même format uniquement dans la mémoire de pile plutôt que dans la mémoire de tas, nous devions toujours générer la valeur intermédiaire y. Nous n’allouons l’objet nulle part – nous l’avons remplacé par des bords de flux de données à la place.

Notez que l’allocation de pile d’objets est vraiment une chose, et cela est proposé pour HotSpot standard et C2, mais c’est dans un but légèrement différent que nous n’aborderons pas ici pour plus de simplicité.

Par rapport à l’optimisation manuelle

Réécririez-vous certaines de ces méthodes pour accumuler les x et y dans les variables locales et ne pas créer d’objets Vector intermédiaires ? Par exemple, vous pouvez réécrire le sum sur un tableau d’objets Vector comme ceci:

Ce graphique est en effet plus efficace que le graphique de notre somme avec des objets intermédiaires Vector avant analyse d’échappement. Il n’y a pas d’allocation à l’intérieur de la boucle.

Mais si nous revenons à notre boucle de somme précédente avec des objets intermédiaires Vector après l’analyse d’échappement et le remplacement scalaire des agrégats, ils se ressemblent fondamentalement. Il n’y avait aucun avantage à réécrire cette méthode de la version de haut niveau avec de simples objets intermédiaires Vector à la version optimisée manuellement.

(En fait, peut–être existe – la version optimisée manuellement est plus rapide à compiler et s’exécute plus rapidement tout en étant interprétée jusqu’à sa compilation.)

Analyse d’échappement partiel

Quelque chose que Graal peut faire que C2 ne peut pas, et un avantage clé de GraalVM, est l’analyse d’échappement partiel. Au lieu de déterminer une valeur binaire indiquant si un objet échappe ou non à l’unité de compilation, cela peut déterminer sur quelles branches un objet l’échappe et déplacer l’allocation de l’objet uniquement vers les branches où il s’échappe.

Cette méthode artificielle somme deux objets Vector, puis sur la base d’une condition s, elle le passe en paramètre à une autre méthode appelée blackhole, ce qui le fait s’échapper, ou elle ajoute un troisième vecteur, puis le renvoie.

L’intermédiaire Vector stocké dans x s’échappe sur la première branche, mais pas sur la seconde.

Nous empêchons blackhole d’être en ligne en spécifiant -XX:CompileCommand=dontinline,Vector.blackhole.

Avant l’exécution de l’analyse d’échappement partielle, nous pouvons voir que New Vector pour x est exécuté pour les deux branches.

Après analyse d’échappement partiel et remplacement scalaire des agrégats, l’intermédiaire New Vector a disparu. Au lieu de cela, sur la branche où il s’échappe, nous avons l’objet Alloc, qui fait référence aux valeurs qu’il devrait avoir de x et y, et sur l’autre branche où l’objet n’échappe pas les valeurs pour x et y sont simplement utilisées directement.

L’allocation a été déplacée uniquement vers la branche où elle est réellement nécessaire.

Espérons que tout cela vous aidera à comprendre ce qu’est l’analyse d’échappement et le remplacement scalaire des agrégats en le voyant fonctionner dans la pratique. J’espère également que cela vous montrera que ce n’est pas vraiment une allocation de pile et que c’est en fait quelque chose de plus puissant que cela, et que cela vous montrera ce que le compilateur GraalVM peut faire pour vous.

Plus d’informations

L’algorithme d’analyse d’échappement partiel de Graal est décrit dans Analyse d’échappement partiel et Remplacement scalaire pour Java.

J’ai écrit plus sur ces graphiques du compilateur et comment les lire pour Comprendre les graphiques de Graal de base.

Auteur: Chris Seaton

Chris est chercheur (Ingénieur Principal) chez Shopify, où il travaille sur le langage de programmation Ruby, et Visiteur à l’Université de Manchester.

Il était auparavant Directeur de recherche au sein du groupe de recherche sur les machines Virtuelles Oracle Labs, où il a dirigé l’implémentation TruffleRuby de Ruby, et a travaillé sur d’autres projets de langages et de machines virtuelles. Avant cela, il a terminé un doctorat à Manchester où il a étudié les langages de programmation et le parallélisme irrégulier, et un MEng à l’Université de Bristol sur les langages à syntaxe et sémantique mutables.

Pendant son temps libre, il est Chef d’escadron du Cheshire Yeomanry squadron du Queen’s Own Yeomanry, l’escadron historique de cavalerie légère de réserve du Cheshire.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.