Créer une machine virtuelle en Rust

• English: Writing a virtual machine in Rust

Aperçu #

Pour m’aider à apprendre le langage Rust, j’ai décidé de réaliser un interpréteur pour Lox, le langage de script que Robert Nystrom a créé à des fins pédagogiques pour son livre Crafting Interpreters. Je m’intéresse aux langages de script qui sont destinés à être embarqués dans des applications, et cet exercice m’a semblé un bon moyen d’en savoir plus sur la construction de ce type de langage.

Le livre de Nystrom présente, étape par étape, le développement de deux versions de l’interpréteur. Alors que la première, en Java, parcourt un arbre de syntaxe abstraite (AST) pour exécuter un script, la deuxième, en C, comporte une machine virtuelle qui exécute du bytecode. Cette deuxième version m’intéressait davantage. Au fil des ans, j’avais réalisé deux interpréteurs qui parcourent des arbres de syntaxe abstraite, en commençant par Apache FreeMarker, ainsi qu’un compilateur source à source optimisant utilisant l’inférence de types. Mais je n’avais pas encore fait de machine virtuelle. L’idée me rappelait de bons souvenirs de programmation en assembleur sur l’Apple II quand j’avais quinze ans. Le jeu d’instructions de la machine virtuelle de Nystrom est plus simple que celle du processeur Motorola 6502 de l’Apple II, mais le principe est le même. J’ai donc sauté la première partie du livre pour aller directement à celle où il s’agit de la machine virtuelle.

Le résultat est OrganicLox. La conception est globalement celle présentée dans le livre, mais j’ai essayé de coder dans un Rust courant, en visant des performances raisonnables, sans écrire de code non sécurisé. Les fonctionnalités d’OrganicLox devraient être identiques à celles du programme clox de Nystrom : au moins, ses 246 tests automatisés passent.

J’ai décidé de ne pas créer mon propre ramasse-miettes, car tout le monde semble s’accorder à dire que les ramasse-miettes sont particulièrement difficiles à réaliser en Rust. Par souci de simplicité, j’ai opté plutôt pour le comptage des références (au moyen de Rc). Sur la branche main, cela veut dire que les cycles de propriétés d’objets ne seront pas nettoyés. Sur la branche with_dumpster_gc, j’ai remplacé Rc par la crate dumpster, qui assure le comptage des références et nettoie aussi les cycles.

Ce que j’ai préféré #

J’ai beaucoup aimé ce livre : les explications claires de Nystrom, ses illustrations utiles, son style léger et son humour ont rendu le livre agréable à lire.

Pour moi, la mise en œuvre des variables locales et des fermetures dans une machine virtuelle à pile ont été parmi les aspects les plus intéressants de la conception que présente Nystrom, conception qui s’inspire largement de celle de l’interpréteur Lua. J’ai aimé apprendre que le compilateur associe les variables locales à des positions spécifiques sur la pile, de sorte que la machine virtuelle n’a besoin de connaître que ces positions et non pas les noms des variables concernés.

La mise en œuvre des upvalues, à savoir les variables qui sont capturées par les fermetures et qui doivent donc éventuellement être allouées sur le tas, n’a pas été simple à faire correctement. En corrigeant un bogue, j’ai été heureux de me rendre compte que l’appel récursif d’une function définie dans une portée locale nécessite que la fermeture de la fonction soit une des ses propres upvalues.

Ce que j’aurais souhaité #

Les explications de Nystrom sont tantôt ascendantes, tantôt descendantes. L’approche ascendante a présenté plus de difficultés quant à la traduction de sa conception en Rust, car je devais deviner où il voulait en venir. Plusieurs fois j’ai dû réusiner beaucoup de code parce que je n’avais pas deviné juste. Comme l’implémentation de Lox dans toutes sortes de langages de programmation semble être un exercice courant, il aurait été utile d’avoir plus souvent une vue d’ensemble de la conception.

Cela m’a fait plaisir de découvrir la technique de Pratt pour construire un analyseur syntaxique descendant reposant sur la précédence des opérateurs et de constater qu’il est vraiment possible de générer du bytecode sans d’abord construire un AST. Mais il aurait peut-être été plus utile de construire un AST et d’apprendre quelque chose sur la conception d’une deuxième phase pour optimiser le bytecode.

La performance #

L’optimisation principale que j’ai faite au départ a été de faire en sorte que l’analyseur lexical mette tous les identificateurs dans un pool de chaînes de caractères (en utilisant string_interner), pour que ni le compilateur ni la machine virtuelle aient à comparer des chaînes représentant des identificateurs.

Après avoir fini le chapitre 24, j’ai passé un peu de temps à me pencher sur la performance, en suivant les conseils du Rust Performance Book. J’ai fait des tests de performance avec criterion et du profilage avec perf et hotspot, j’ai ajusté la configuration du compilateur Rust and j’ai marqué quelques fonctions inline.

Ensuite j’ai regardé quelques autres versions de Lox en Rust et j’ai remarqué que tout le monde semble avoir eu du mal à obtenir des performances proches de celles du clox de Nystrom et que les versions qui y arrivent comportent beaucoup de code non sécurisé, ce que je voulais éviter.

Je recommande vivement billet de blog de Manuel Cerón sur sa tentative impressionnante, déterminée et partiellement réussie d’égaler la vitesse de clox en Rust en écrivant de plus en plus de code non sécurisé.

À titre de comparaison, voici les résultats de l’exécution de quelques-uns des tests de performance de Nystrom sur les versions suivantes :

• Le clox de Nystrom
• La version sécurisée du loxido de Cerón
• La version non sécurisée de loxido
• OrganicLox avec Rc
• OrganicLox avec le ramasse-miettes dumpster

OrganicLox avec Rc est donc deux à quatre fois plus lent que clox, ce qui est peut-être typique des interpréteurs réalisés en Rust par rapport à ceux réalisés en C. La version avec dumpster est beaucoup plus lente. Il semble clair qu’un ramasse-miettes rapide est essentiel pour une machine virtuelle très performante.

Quelle est l’importance de ces différences ? Les tests de performance sont conçus pour simuler des scénarios extrêmes, par exemple en utilisant de longues boucles ou la récursivité profonde, ou en créant une charge de travail importante pour le ramasse-miettes. Ils ne sont donc pas forcément représentatifs des cas d’utilisation réels. Il arrive souvent que les scripts exécutés par une application dans un interpréteur embarqué sont courts et font très peu de travail. On pourrait se faire une idée plus réaliste de la performance d’une machine virtuelle dans un tel scénario en exécutant la suite de tests d’intégration de Nystrom, qui exécute 246 scripts courts en Lox et vérifie leurs sorties. Voici une comparaison :

Dans une application où chaque cycle CPU compte, les écarts entre les performances de ces différentes implémentations pourraient avoir beaucoup d’importance. Mais dans d’autres cas d’utilisation, ils pourraient être insignifiants.

D’autres approaches possibles #

Il est tentant d’essayer d’ajouter un compilateur à la volée (JIT) pour améliorer la performance de l’interpréteur, soit en en écrivant un à partir de zéro, soit en en utilisant un backend existant comme LLVM ou Cranelift. Roto et Dora sont des exemples en Rust de cette approche. Mais même si on adopte cette démarche, il n’est pas facile d’atteindre un haut niveau de performance. Dans ces tests de performance, le nouveau JIT de Python n’a aucun effet mesurable sur les performances (voir aussi ces résultats de tests de la performance de Dora).

Voilà une raison d’envisager d’utiliser un interpréteur existant qui a déjà bénéficié d’années de développement, plutôt que d’en créer un nouveau. Le langage Lua est une option largement utilisée, mais il n’est pas assez rapide pour certaines applications. La machine virtuelle LuaJIT est un ordre de grandeur plus rapide que la machine virtuelle Lua standard pour certains cas d’utilisation, mais c’est un compilateur à la volée basé sur les arbres de traces, ce qui a des avantages et des inconvénients. Les développeurs de Lua ont publié un article intéressant qui traite des limites de cette approche et propose une autre solution (un langage supplémentaire à typage statique, un peu comme Cython).

Pour certains cas d’utilisation, si des scripts embarqués ne font pas beaucoup de travail, leurs performances pourraient ne pas être critiques. S’ils font tellement de travail que leurs performances sont insuffisantes, une autre option consiste à ne pas intégrer d’interpréteur du tout. Cloudflare, qui avait investi massivement pendant plus de 20 ans dans des scripts en utilisant LuaJIT embarqué dans OpenResty, les a récemment remplacés par du code Rust.