Aplatissement des AST et d’autres structures de données de compilateur

• Les arènes ou régions sont une technique simple et efficace pour les compilateurs et les outils qui leur ressemblent.
• Utiliser des arènes pour aplatir des arbres de syntaxe abstraite (AST) peut améliorer les performances et apporter plus de praticité.
• L’aplatissement consiste à empaqueter les nœuds de l’AST dans un tableau unique et à utiliser des indices de tableau au lieu de pointeurs.
• Un AST aplati offre des avantages comme une meilleure localité, des références plus petites, ainsi qu’une allocation et une libération moins coûteuses.
• Un AST aplati peut simplifier la gestion mémoire et permettre une déduplication pratique.
• Les résultats de performance montrent qu’une version aplatie de l’interpréteur peut être 2,4 fois plus rapide que la version classique.
• En exploitant la représentation aplatie de l’AST, on peut éliminer la récursivité et tirer parti d’un parcours linéaire pour améliorer encore les performances.
• Cet article examine les gains de performance obtenus grâce à l’aplatissement de structures de données dans l’interpréteur d’un langage de programmation.
• En outre, l’interpréteur aplati montre un gain de performance de 8,2 % par rapport à l’interpréteur récursif, avec 1,2 seconde contre 1,3 seconde.
• Cette technique réinvente en pratique l’idée de l’interpréteur de bytecode, la structure Expr servant d’instruction de bytecode.
• D’autres articles et projets liés à l’aplatissement de structures de données sont mentionnés, notamment LuaJIT, le vérificateur de types Sorbet et le shell Oil.
• Des concepts similaires liés à l’aplatissement et à l’optimisation de la localité apparaissent aussi dans des domaines comme le jeu vidéo, le traitement de données sérialisées, la conception orientée données et les systèmes entité-composant.
• L’article recommande également de consulter le billet d’Inanna Malick, qui applique la même technique à un langage « calculatrice » jouet implémenté en Rust.
• Les limites de l’utilisation de cette technique en Rust sont discutées, notamment l’impossibilité d’inclure en ligne d’autres Expr à l’intérieur de la structure Expr.
• La comparaison des performances a été effectuée sur un MacBook Pro équipé d’un processeur M1 Max et de 32 Go de mémoire, exécutant macOS 13.3.1 et Rust 1.69.0.

[GN⁺]

Commentaire Hacker News

• Blender utilise la même représentation sur disque et en mémoire pour permettre un chargement et une sauvegarde des fichiers rapides et sans perte.
• Un AST aplati est utilisé dans pulldown-cmark pour un parsing efficace du balisage inline.
• Une représentation d’AST aplatie permet des transformations d’arbre en O(1), indépendamment du nombre de nœuds ou de la profondeur de la pile.
• Les performances de pulldown-cmark sont remarquables par rapport aux autres parseurs CommonMark.
• La Warren Abstract Machine (WAM) utilise sur le tas une représentation aplatie pour Prolog.
• L’aplatissement des AST est un concept déjà employé dans des langages comme Lisp.
• Stocker les nœuds dans un tableau redimensionnable peut poser des problèmes d’allocation mémoire, mais cela peut être atténué par une mise en pool dans des blocs de taille de page.
• Il faut prêter attention à la manière dont les nœuds AST sont représentés dans le code et éviter tout padding inutile.
• Utiliser des index plutôt que des pointeurs permet d’obtenir un code plus petit et plus rapide.
• Il est possible d’implémenter une mémoire aplatie à l’aide d’un allocateur mémoire personnalisé, utile dans certains scénarios.
• Une structure AST compacte a été utilisée pour implémenter un parseur et un interpréteur JavaScript dans des environnements soumis à des contraintes mémoire.