- Refonte complète d’un outil interne pour visualiser le processus de compilation JavaScript·WebAssembly du moteur SpiderMonkey, avec implémentation d’une fonctionnalité générant des graphes interactifs
- L’ancien iongraph basé sur Graphviz offrait une disposition instable et une structure peu intuitive, ce qui réduisait l’efficacité du débogage ; pour le remplacer, un nouvel algorithme de placement a été conçu en interne
- Le nouvel algorithme simplifie l’approche de Sugiyama afin de représenter clairement les structures de boucle, et fournit un placement stable et rapide en moins de 1000 lignes de JavaScript
- Les graphes utilisent des arêtes droites dans un style de diagramme ferroviaire pour améliorer la lisibilité, avec une vitesse de rendu des milliers de fois supérieure à Graphviz
- L’outil est intégré au profiler de Firefox et des extensions sont prévues, comme la recherche ou la visualisation des registres
Refonte de l’outil de visualisation de SpiderMonkey
- Un nouvel outil a été développé pour visualiser les graphes internes générés par le compilateur d’optimisation Ion de SpiderMonkey
- L’utilisateur peut saisir du code JavaScript sur une page web afin d’explorer en temps réel sous forme de graphe le processus d’optimisation d’une fonction
- Le graphe permet d’observer les changements étape par étape grâce au glisser-déposer, au zoom et à un curseur
- L’ancien iongraph basé sur Graphviz produisait des PDF, mais il ne correspondait pas à la structure du code source et souffrait d’une forte instabilité de sortie
- De petites modifications du code pouvaient déplacer fortement les nœuds, rendant la comparaison entre passes difficile
- Les structures de boucle et de condition étaient visuellement déformées, ce qui compliquait la compréhension du flux de contrôle
Les limites de Graphviz et la nouvelle approche
- L’algorithme de Sugiyama de Graphviz convient à l’optimisation de graphes généraux, mais ne reflète pas les spécificités des graphes de flux de contrôle (CFG)
- Les boucles de JavaScript et de WebAssembly n’ont qu’un seul point d’entrée et possèdent un flux de contrôle réductible (reducible)
- L’équipe SpiderMonkey a exploité ces contraintes pour concevoir un algorithme spécialisé simplifié
- Suppression des cycles : les backedges de boucle sont ignorées
- Hiérarchisation (Leveling) : les blocs après une boucle sont placés plus bas afin de refléter le flux du code
- Omission de la minimisation des croisements : priorité à la stabilité avec un ordre fixe des branches true/false
- Préservation de la structure en arbre des boucles : les boucles imbriquées restent visuellement claires
- Le résultat est un placement concis, rapide et stable ; l’implémentation initiale tient en environ 1000 lignes de JavaScript
Étapes de l’algorithme de placement d’iongraph
- Étape 1 : Layering
- Les blocs sont ordonnés par niveaux en tenant compte des relations intérieur/extérieur des boucles
- Après la fin d’une boucle, les blocs sont placés plus bas de toute la hauteur de la boucle
- Étape 2 : création de nœuds fictifs
- Des nœuds fictifs sont ajoutés aux arêtes traversant plusieurs niveaux afin d’éviter les collisions visuelles
- Les arêtes allant vers la même destination sont fusionnées pour réduire le bruit visuel
- Étape 3 : alignement des arêtes (Straighten)
- Les nœuds parents et enfants sont alignés pour conserver des lignes verticales, avec application d’une indentation pour les boucles
- Les nœuds fictifs participent aussi à l’alignement afin d’éviter les chevauchements et préserver la structure
- Étape 4 : gestion des pistes horizontales
- Les arêtes horizontales sont organisées par pistes (tracks) afin d’éviter tout chevauchement
- Elles sont séparées vers le haut ou vers le bas selon leur direction, et les arêtes fusionnables sont regroupées
- Étape 5 : placement vertical (Verticalize)
- Une coordonnée Y est attribuée à chaque niveau pour uniformiser la hauteur et améliorer la lisibilité
- Étape 6 : rendu (Render)
- Utilisation d’arêtes droites dans un style de diagramme ferroviaire
- Les arêtes ne se croisent qu’à la verticale et à l’horizontale, avec une directionnalité et une structure claires
Les effets d’un algorithme simple
- Plutôt que des optimisations complexes, le recours à un placement prévisible fondé sur des règles assure lisibilité et stabilité
- L’ordre fixe des nœuds et la simplification des arêtes garantissent la cohérence entre passes
- En écartant le constraint solver, l’outil obtient une structure plus facile à comprendre pour un humain
- Il devient possible de concevoir une disposition centrée sur le sens, comme l’organisation interne des boucles ou le placement inférieur des blocs suivants
- Amélioration des performances : un graphe de fonction zlib qui demandait 10 minutes à Graphviz est rendu en 20 millisecondes
- Une vitesse des milliers de fois supérieure et une meilleure explorabilité sont obtenues
Suite prévue
- iongraph est déjà intégré au profiler de Firefox, ce qui permet de consulter les graphes lors de l’analyse des performances
- Pour l’instant, il n’est utilisable que dans les builds du shell SpiderMonkey, pas dans les builds du navigateur
- Fonctionnalités proposées pour la suite
- Fonctions de navigation avancées, recherche, visualisation de l’allocation des registres, etc.
- Il n’existe pas de feuille de route claire, et les contributions open source sont les bienvenues
- Pour des essais en local, il suffit de définir
IONFLAGS=logs pour générer /tmp/ion.json, puis de le charger dans la
version autonome déployée
- Le code source est publié sur GitHub, et il est possible d’échanger directement avec les développeurs via le salon Matrix
1 commentaires
Commentaires sur Hacker News
Pour être précis, la comparaison ne porte pas sur l’ensemble de Graphviz, mais sur dot(1)
Graphviz est un framework de visualisation qui inclut plusieurs moteurs de layout (dot, neato, fdp, sfdp, circo, twopi, etc.)
Ce serait vraiment formidable si le nouvel algorithme proposé contribuait à Graphviz
Voir la documentation correspondante : description du langage Graphviz et documentation du moteur de layout dot
Il peut bien fonctionner sur des graphes de flot de contrôle (CFG) avec un flot de contrôle réductible, mais il doit y avoir beaucoup d’exceptions complexes
En plus, iongraph est basé sur JavaScript, donc pour l’intégrer à Graphviz, il faudrait le convertir en C avec un outil comme Claude
La capacité à aller lire soi-même l’implémentation originale d’un algorithme ressemble vraiment à un super-pouvoir
Ayant déjà fait des visualisations complexes avec Graphviz, j’ai d’abord été surpris que quelqu’un le réimplémente directement
Mais en voyant la structure de l’algorithme, j’ai réalisé que cela pouvait être plus simple que je ne le pensais
Cela dit, tant qu’on n’a pas terminé l’implémentation réelle, il reste difficile de connaître la complexité cachée
Spécialiser un algorithme général pour un domaine de problème précis permet souvent d’obtenir de bien meilleurs résultats
Mais dans la plupart des cas, par commodité, on utilise tel quel un algorithme généraliste
Concevoir un système adapté à une application précise apporte de grands gains en performance, scalabilité et tolérance aux pannes
Mais quand on vise une amélioration de 1000x, un ou deux ans passent très vite
Un système général de layout de graphes doit couvrir une bien plus grande variété de cas, donc il devient inévitablement plus complexe
C’est pourquoi je pense qu’un bon compromis consiste à analyser l’entrée, utiliser un algorithme rapide pour les cas particuliers, et un algorithme général garanti pour le reste
Très bon article. À noter que le dot de Graphviz n’est pas une implémentation pure de l’algorithme de Sugiyama
L’implémentation réelle est décrite en détail dans les articles du site
Si l’on compare dot et iongraph sur de grands graphes, on voit que dot est optimisé pour la minimisation de surface, contrairement à iongraph
Les visualisations de grands graphes sont impressionnantes à regarder, mais en pratique elles sont rarement utiles
La visualisation reste utile jusqu’à quelques dizaines de nœuds ; au-delà, la complexité des arêtes rend la compréhension difficile
Au final, cela ne marche bien que sur des exemples simples, et dans des environnements complexes cela devient plutôt un obstacle
La plupart des problèmes peuvent être réduits à de petites unités
En revanche, même sur de petits graphes, Graphviz n’est pas très esthétique, tandis que iongraph offre une bien meilleure lisibilité des lignes
À long terme, je pense qu’il faut des éléments interactifs comme la recherche et des fonctions de mise en évidence/masquage
La limite frustrante des diagrammes, c’est qu’ils ne peuvent ni émettre ni recevoir de liens
Mermaid permet des liens textuels, mais les liens dans le diagramme restent limités
La discussion associée sur StackOverflow vaut aussi le détour
Il faudrait un outil où ce type de fonctionnalité soit pensé comme une capacité de premier ordre dès la conception
La vraie force de Graphviz, c’est le langage dot
Les graphes définis en dot offrent une excellente compatibilité entre outils, et la syntaxe est simple et facile à lire
Des alternatives comme Mermaid sont apparues, mais dot restera probablement longtemps un format standard
C’était vraiment un article très sympa
Je me demande si ce type de techniques a aussi été utilisé dans le moteur de layout TALA de D2
Voir des exemples de TALA
Si le dessin de graphes vous intéresse, je recommande les cours de Will Evans (lien)
J’ai autrefois contribué un correctif de bug au lexer Dot de l’Open Graph Drawing Framework (OGDF),
et OGDF implémente des algorithmes plus rapides avec moins de croisements que Graphviz
D’après mon expérience, les résultats d’OGDF étaient bien plus propres
Voir aussi l’historique des PR concernées : lien GitHub
Intéressant. Je me demande comment exécuter les exemples
Ce projet a pour point fort de prendre en charge l’exploration interactive en partant du principe d’un environnement client web
Comme le layout est spécialisé pour les graphes de flot de contrôle (CFG), il permet une visualisation adaptée au domaine
Graphviz dispose aussi de fonctions de polylignes et de contrôle de l’ordre des arêtes, mais elles sont mal documentées
Intégrer l’algorithme de routage des arêtes de Brandes et Kopf serait une bonne idée
Graphviz est un projet vieux de presque 40 ans, aujourd’hui maintenu par quelques bénévoles de deuxième génération
Fabriquer des outils reste toujours un marché difficile, et les utilisateurs sont intelligents mais appartiennent à des équipes aux budgets réduits
Il est dommage que l’évolution des outils déclaratifs de diagrammes 2D soit si lente
Toute personne qui travaille dans ce domaine a toujours droit à un +1 d’encouragement
J’ai aussi utilisé mermaid et graphviz, mais au final je reviens toujours à FigJam — la lisibilité et le rendu esthétique y sont meilleurs
graphviz est un binaire massif, mermaid dépend du rendu SVG du navigateur, ce qui est peu pratique
Il faudrait simplement un outil permettant de créer facilement des diagrammes en texte
L’approche proposée par l’auteur me semble être une bonne tentative pour maîtriser ce compromis
J’en étais satisfait, à part le fait que les boucles n’étaient pas gérées
La sortie SVG/HTML est pratique pour ajuster le style et copier le contenu
Si vous cherchez un outil de diagrammes textuel, je recommande TikZ
Voir le wiki TikZ
En revanche, on n’y retrouve pas le retour visuel immédiat d’un FigJam
Je n’aimais pas le trop grand nombre de dépendances de mermaid ni le manque de cohérence de son code
À la place, nomnoml(lien) a un code propre, et il existe aussi graphre, porté en Typescript (lien)
Pour utiliser mermaid avec resvg-js, il faudrait un refactoring autour de la mesure de la largeur du texte dans le SVG