Résoudre un problème de performance vieux de 3 ans dans Gleam avec une arena Rust

• Dans la structure récursive Document du formateur Gleam, les allocations individuelles sur le tas répétées ont été remplacées par des références basées sur une arena, résolvant ainsi un problème d’amélioration des performances resté ouvert pendant 3 ans
• Box<Self> a été remplacé par &Self stocké dans une arena, et les vérifications de durée de vie de Rust garantissent que les données internes ne sont pas référencées après la suppression de l’arena
• Des centaines de Document récurrents, comme les mots-clés du langage et les virgules, sont désormais alloués une seule fois puis réutilisés, ce qui réduit le temps d’exécution du pretty-printer de 13 ms à 9,8 ms, soit 24 % plus rapide
• Le temps d’exécution total de gleam format, incluant la lecture et le parsing des sources, a également été réduit de 13 %, tandis que l’utilisation maximale de mémoire est passée de 8,4 Mo à 7,6 Mo, soit environ 10 % de moins
• Il a fallu modifier largement les fonctions et leurs sites d’appel pour passer l’arena, avec un travail manuel de l’ordre de +2963/-1032, mais cette approche consistant à réduire les allocations individuelles répétées a permis d’améliorer à la fois la vitesse et l’usage mémoire

---

Le coût des allocations dans une structure Document récursive

• Le pretty-printer de Gleam utilise une structure de données Document récursive qui décrit comment afficher le code et où le couper lorsque la limite de ligne est dépassée
• Ses principaux variants comprennent String, qui contient la chaîne à afficher, Break, qui définit les chaînes avant et après un saut de ligne, Group, qui regroupe plusieurs documents, et Nest, qui augmente l’indentation lors d’un saut de ligne
• Même une liste [1, 2] est représentée par une combinaison de String, Break, Nest et Group
  • Si elle tient sur la ligne courante, elle est affichée sur une seule ligne, comme [1, 2]
  • Si elle dépasse la limite de ligne, elle est répartie sur plusieurs lignes selon les Break définis, avec indentation et affichage de la virgule finale
• Les variants qui contiennent un autre Document, comme Nest, utilisaient auparavant Box<Self>, ce qui imposait une allocation individuelle sur le tas pour chaque document imbriqué, une opération pouvant représenter une part importante du temps d’exécution
• L’algorithme de base du pretty-printer de Gleam est décrit dans l’article Strictly Pretty

Remplacer Box par des références vers une arena

• L’ancien Nest(Box<Self>) a été remplacé par Nest(&'doc Self), afin que la structure référence un autre Document stocké dans l’arena
• Pour contenir ces références, une durée de vie 'doc pour les données de document a été ajoutée à Document, séparément de la durée de vie 'string des chaînes
• L’implémentation utilise le crate typed_arena
  • Quand une valeur est stockée dans l’arena avec alloc, une référence vers cette valeur est retournée
  • Les données allouées peuvent être utilisées tant que l’arena reste en vie
  • Quand l’arena sort de portée, les données qu’elle contient sont également supprimées
• La référence retournée par alloc(&self, value: T) -> &mut T ne peut pas vivre plus longtemps que l’arena, et le borrow checker de Rust empêche les références invalides après la suppression de l’arena

Allouer une seule fois les documents récurrents et les réutiliser

• L’arena sert non seulement à référencer d’autres documents, mais aussi à mettre en cache les Document répétés dans l’ensemble du code
• Il n’est plus nécessaire de recréer à chaque fois les documents représentant les mots-clés du langage, comme String("fn"), String("pub") ou String("type")
• Les documents comme Break { unbroken: ", ", broken: "," }, utilisés entre les éléments d’une liste, sont eux aussi alloués une fois puis réutilisés
• Des centaines de petits documents qui devaient auparavant être sans cesse placés dans des Box peuvent désormais être alloués chacun une seule fois

Une API simple, mais de nombreuses modifications des sites d’appel

• L’API de l’arena elle-même est simple, mais convertir une grande partie du code existant a nécessité de nombreuses modifications répétitives
• Les fonctions qui se contentaient auparavant d’appeler Box::new doivent désormais recevoir un argument d’arena supplémentaire pour allouer les données
• Une fonction comme format_list passe désormais la même arena aux sous-fonctions qui formatent les éléments de la liste, et crée les documents imbriqués avec arena.alloc au lieu de Box::new
• Après plusieurs jours de recherches-remplacements prudents, le travail a été achevé dans une pull request de taille +2963/-1032
• Ce travail était répétitif et manuel, et aucun LLM n’a été utilisé dans le processus

Amélioration de la vitesse et de l’utilisation maximale de mémoire

• Lors du formatage de squirrel, un vrai projet Gleam, le temps d’exécution du pretty-printer est passé de 13 ms à 9,8 ms
  • En comparant uniquement le pretty-printer, cela représente une amélioration des performances de 24 %
• Comme gleam format lit et parse aussi le code source du projet en plus du formatage, le pretty-printer ne représente qu’une partie du travail total, mais le temps d’exécution global a tout de même été réduit de 13 %
• L’utilisation maximale de mémoire est passée de 8,4 Mo à 7,6 Mo, soit environ 10 % de moins
• En réduisant le nombre d’allocations individuelles sur le tas grâce à l’arena, le formateur s’exécute plus vite tout en consommant moins de mémoire

[GN⁺]

Avis sur Lobste.rs

• Si vous voulez réduire encore de 10 % le pic d’utilisation mémoire, il peut valoir la peine d’envisager une autre arène qui renvoie des handles opaques au lieu de références. Les handles peuvent être codés sur 16 ou 32 bits plutôt que 64 bits, ce qui est très efficace quand il y a beaucoup de petites allocations
  D’après https://donsz.nl/blog/arenas/, le seul crate qui prend cela en charge est compact_arena, mais si cela ne correspond pas à vos besoins, ce n’est pas non plus difficile à implémenter soi-même

  • Avec des handles opaques, on peut aussi stocker les données de façon plus compacte. columnar, un projet personnel, stocke les listes de Option<T> en les séparant en un indicateur de présence d’à peine plus de 1 bit par élément et les valeurs T des éléments effectivement présents
    En contrepartie, il renvoie Option<&T> comme type de référence, et non &Option<T> ; plus généralement, il s’agit de faire une récursion structurelle en suivant les références, plutôt que de placer des références dans une récursion structurelle
  • L’article repose sur une étude vieille de deux ans et ne couvre pas parfaitement tous les crates ; si vous repérez une erreur ou une nouvelle bibliothèque manquante, vous pouvez envoyer une PR
    Les arènes mériteraient d’être plus largement utilisées, et renvoyer des références plutôt que des handles ou des smart pointers rend le pattern matching sur des énumérations récursives très pratique en Rust. Normalement, même si l’on veut écrire quelque chose comme if let MyAst::Add(MyAst::Multiply(a, b), c) = expr {}, c’est impossible à cause des boîtes ou pointeurs intermédiaires, mais les références permettent de faire du pattern matching de manière transparente, sans fonctionnalité nightly. Si toutes les références pointent vers une même arène, la durée de vie qui relie tout l’arbre reste également cohérente
  • Les résultats étant bons, on envisage aussi de migrer d’autres parties du compilateur vers une approche par arène, et cette piste continuera d’être étudiée

• Cette approche ressemble beaucoup à celle prise en charge par pretty, une autre bibliothèque de pretty-printing de style Wadler. Cela dit, comme elle prend en charge plusieurs modes d’allocation mémoire, son API peut paraître un peu lourde

• Il est surprenant que l’auteur de l’article scientifique cité dans l’article travaille dans une entreprise IT ordinaire à Brunswick

  • C’est tout le charme de l’open source. L’expertise et le métier exercé au quotidien n’ont souvent pas grand-chose à voir