- Même un interpréteur parcourant directement l’AST peut obtenir de gros gains de performances rien qu’avec la représentation des valeurs, les caches inline, le modèle objet, les watchpoints et des optimisations de détail répétées
- La base Zef, conçue avec très peu de considération pour les performances, était 35 fois plus lente que CPython 3.10, 80 fois plus lente que Lua 5.4.7 et 23 fois plus lente que QuickJS-ng 0.14.0, mais a atteint une accélération de 16,646× après 21 étapes d’optimisation
- Le plus grand saut de performance est venu de la refonte du modèle objet combinée aux caches inline, suivie d’un gain de 4,55× grâce à l’accès fondé sur Storage et Offsets, à la spécialisation mise en cache de l’AST et à l’application de watchpoints pour surveiller les redéfinitions de noms
- D’autres améliorations ont été ajoutées de façon cumulative, notamment la suppression du dispatch basé sur les chaînes, l’introduction de Symbol, le changement de la structure de passage des arguments, la spécialisation des getter et setter, les chemins rapides pour tables de hachage, ainsi que la spécialisation des littéraux de tableau et de
sqrt·toString - En incluant le portage vers Yolo-C++, le système devient 66,962 fois plus rapide que la base, 1,889 fois plus rapide que CPython 3.10 et 2,968 fois plus rapide que QuickJS-ng 0.14.0, mais il reste inadapté aux charges de travail de longue durée faute de libération mémoire
Introduction et méthodologie d’évaluation
- La cible des optimisations est un interpréteur parcourant directement l’AST, avec pour objectif d’amener le langage dynamique Zef, créé pour le plaisir, à un niveau capable de rivaliser avec Lua, QuickJS et CPython
- Plutôt que de se concentrer sur le réglage fin d’un compilateur JIT ou d’un GC mature, l’article met l’accent sur des optimisations applicables même à partir d’une base sans fondations solides
- Les techniques traitées sont la représentation des valeurs, les caches inline, le modèle objet, les watchpoints et l’application répétée d’optimisations de bon sens
- Les techniques du texte permettent à elles seules d’obtenir un gros gain de performances sans SSA, GC, bytecode ni code machine
- Accélération de 16× dans le cadre du texte
- Accélération de 67× en incluant le portage inachevé vers Yolo-C++
- L’évaluation des performances utilise la suite de benchmarks ScriptBench1
- Les benchmarks inclus sont Richards (ordonnanceur d’OS), DeltaBlue (solveur de contraintes), N-Body (simulation physique) et Splay (test d’arbre binaire)
- Les ports existants pour JavaScript, Python et Lua sont utilisés
- Les ports Python et Lua de Splay ont été générés avec Claude
- L’environnement expérimental est composé d’Ubuntu 22.04.5, d’un Intel Core Ultra 5 135U, de 32 Go de RAM et de Fil-C++ 0.677
- Lua 5.4.7 a été compilé avec GCC 11.4.0
- QuickJS-ng 0.14.0 utilise le binaire des releases GitHub
- CPython 3.10 utilise la version fournie par défaut avec Ubuntu
- Toutes les expériences utilisent la moyenne de 30 exécutions mélangées aléatoirement
- La plupart des comparaisons sont effectuées entre l’interpréteur Zef compilé avec Fil-C++ et d’autres interpréteurs construits avec le compilateur Yolo-C
Interpréteur Zef d’origine
- Il a été écrit avec très peu de considération pour les performances, et il est précisé qu’il n’y avait que deux choix faits dans cette optique
-
Représentation des valeurs
- Utilisation d’une tagged value sur 64 bits
- Les valeurs prises en charge sont double, entier 32 bits et
Object*
- Les valeurs prises en charge sont double, entier 32 bits et
- Les double sont représentés par une méthode à offset
0x1000000000000- Présentée comme une technique apprise de JavaScriptCore
- Désignée dans la littérature sous le nom de NuN tagging
- Les entiers et pointeurs utilisent leur représentation native
- Cela repose sur l’hypothèse qu’une valeur de pointeur n’est pas inférieure à
0x100000000 - Le texte précise explicitement qu’il s’agit d’un choix risqué
- Il est mentionné qu’une alternative aurait été de placer un tag de bits de poids fort
0xffff000000000000sur les entiers
- Cela repose sur l’hypothèse qu’une valeur de pointeur n’est pas inférieure à
- Cette représentation permet d’implémenter un chemin rapide fondé sur des tests de bits pour les opérations numériques
- Son avantage le plus important est toutefois d’éviter les allocations sur le tas pour les nombres
- Lorsqu’on crée un nouvel interpréteur, il est important de bien choisir dès le départ la représentation de base des valeurs, car il est ensuite très difficile de la modifier
- Comme point de départ pour l’implémentation d’un langage à typage dynamique, le texte propose une tagged value 32 bits ou 64 bits
- Utilisation d’une tagged value sur 64 bits
-
Choix du langage d’implémentation
- Un langage de la famille C++ a été choisi afin de pouvoir exprimer suffisamment d’optimisations
- Il est précisé que Java ne serait pas choisi en raison de la limite imposée aux optimisations bas niveau
- Il est aussi indiqué que Rust ne serait pas choisi à cause de l’état global mutable et de la représentation du tas avec références circulaires nécessaires à l’implémentation d’un langage à GC
- Il est toutefois mentionné qu’en acceptant une configuration multilingue ou beaucoup de code
unsafe, Rust pourrait être utilisé partiellement ou totalement
- Il est toutefois mentionné qu’en acceptant une configuration multilingue ou beaucoup de code
-
Mauvais choix du point de vue de l’ingénierie des performances
- Utilisation de Fil-C++
- Il permettait de développer rapidement et fournissait un GC gratuitement
- Il signale les violations de sûreté mémoire avec des informations de diagnostic et des traces de pile
- Il n’y a aucun comportement indéfini
- Le coût en performances est généralement d’environ 4×
- Interpréteur de parcours récursif de l’AST
- Avec une structure de méthode virtuelle
Node::evaluateredéfinie à plusieurs endroits
- Avec une structure de méthode virtuelle
- Abus de chaînes de caractères
- Le nœud AST
Getstocke unestd::stringdécrivant le nom de variable - Cette chaîne est utilisée à chaque accès à la variable
- Le nœud AST
- Abus de tables de hachage
- L’exécution de
Geteffectue une recherche dansstd::unordered_mapavec une clé de type chaîne
- L’exécution de
- Recherche de portée fondée sur une chaîne d’appels récursifs
- Presque toutes les formes d’imbrication et de fermeture sont autorisées
- Dans des imbrications comme une classe A dans une fonction F, puis une fonction G dans une classe B, les méthodes de A peuvent voir les champs de A, les variables locales de F, les champs de B et les variables locales de G
- L’implémentation d’origine gérait cela au moyen de fonctions récursives C++ interrogeant différents objets de portée
- Utilisation de Fil-C++
-
Caractéristiques de l’implémentation d’origine
- Malgré ces mauvais choix, elle permet d’implémenter un interpréteur de langage assez complexe avec peu de code
- Le plus gros module est le parser
- Le reste est plutôt simple et clair
-
Performances initiales
- L’interpréteur d’origine est 35 fois plus lent que CPython 3.10
-
80 fois plus lent que Lua 5.4.7
- 23 fois plus lent que QuickJS-ng 0.14.0
Tableau global de progression des optimisations
- Le tableau récapitule l’évolution des performances de Zef Baseline jusqu’à Zef Change #21: No Asserts, ainsi que Zef in Yolo-C++
- Les colonnes de comparaison sont vs Zef Baseline, vs Python 3.10, vs Lua 5.4.7 et vs QuickJS-ng 0.14.0
- Sur la dernière ligne, Zef Change #21: No Asserts est 16,646 fois plus rapide que la base
-
2,13 fois plus lent que Python 3.10
-
4,781 fois plus lent que Lua 5.4.7
- 1,355 fois plus lent que QuickJS-ng 0.14.0
-
-
Zef in Yolo-C++** est 66,962 fois plus rapide que la base
-
1,889 fois plus rapide que Python 3.10
-
1,189 fois plus lent que Lua 5.4.7
- 2,968 fois plus rapide que QuickJS-ng 0.14.0
-
Premières étapes d’optimisation
-
Optimisation n°1 : appel direct des opérateurs
- Le parseur ne crée plus les opérateurs sous forme de nœuds
DotCallportant le nom de l’opérateur, mais génère à la place des nœuds AST distincts pour chaque opérateur - Dans Zef,
a + beta.add(b)sont identiques- À l’origine,
a + bétait parsé commeDotCall(a, "add")avec l’argumentb - Chaque opération arithmétique entraînait une recherche de chaîne du nom de la méthode d’opérateur
DotCalltransmettait cette chaîne àValue::callMethodValue::callMethodeffectuait plusieurs comparaisons de chaînes
- À l’origine,
- Après modification, le parseur génère des nœuds
Binary<>etUnary<>- Des templates et des lambdas sont utilisés pour fournir des surcharges distinctes de
Node::evaluateselon l’opérateur - Chaque nœud appelle directement le fast path de
Valuecorrespondant à cet opérateur - Par exemple,
a + bappelleBinary<lambda for add>::evaluate, puisValue::add
- Des templates et des lambdas sont utilisés pour fournir des surcharges distinctes de
- Gain de performance : 17,5 %
- À ce stade, les performances restent 30 fois plus lentes que CPython 3.10
- 67 fois plus lentes que Lua 5.4.7
- 19 fois plus lentes que QuickJS-ng 0.14.0
- Le parseur ne crée plus les opérateurs sous forme de nœuds
-
Optimisation n°2 : appel direct des opérateurs RMW
- Les opérateurs classiques sont devenus plus rapides, mais les formes RMW comme
a += butilisaient encore un dispatch basé sur des chaînes - Le parseur a été modifié pour générer des nœuds distincts pour chaque cas RMW
- Le parseur demande désormais aux nœuds LValue de se remplacer eux-mêmes par une version RMW via un appel virtuel
makeRMW - Les LValue transformables en RMW sont Get, Dot et Subscript
- Get correspond à la lecture de variable
id - Dot correspond à
expr.id - Subscript correspond à
expr[index]
- Get correspond à la lecture de variable
- Chaque appel virtuel utilise la macro
SPECIALIZE_NEW_RMW- SetRMW pour
id += value - DotSetRMW pour
expr.id += value - SubscriptRMW pour
expr[index] += value
- SetRMW pour
- La spécialisation des opérateurs du changement n°1 utilise un dispatch par lambda
- Pour RMW, un enum est utilisé
- Ce choix a été fait parce qu’il faut gérer les trois chemins
get,dotetsubscript, et transmettre l’enum à plusieurs endroits - Au final, la fonction template
Value::callRMW<>effectue le dispatch vers l’appel réel de l’opérateur RMW
- Ce choix a été fait parce qu’il faut gérer les trois chemins
- Gain de performance : 3,7 %
- À ce stade, les performances restent 29 fois plus lentes que CPython 3.10
- 65 fois plus lentes que Lua 5.4.7
- 18,5 fois plus lentes que QuickJS-ng 0.14.0
- 1,22 fois plus rapide que le point de départ
- Les opérateurs classiques sont devenus plus rapides, mais les formes RMW comme
-
Optimisation n°3 : éviter les vérifications
IntObject- Le goulot d’étranglement venait du fait que le fast path de
ValueutiliseisInt(), dont leisIntSlow()interne effectue un appel virtuel àObject::isInt() - La représentation initiale des valeurs comportait quatre cas
- tagged int32
- tagged double
IntObjectpour les int64 impossibles à représenter en int32- tous les autres objets
- Même dans le cas d’
IntObject, c’étaitValuequi assurait le dispatch des méthodes entières- L’objectif était de garder toutes les implémentations des opérations arithmétiques à un seul endroit, à savoir
Value
- L’objectif était de garder toutes les implémentations des opérations arithmétiques à un seul endroit, à savoir
- Après optimisation, le fast path de
Valuene prend en compte que int32 et double- La logique de traitement d’
IntObjecta été déplacée dansIntObjectlui-même - Cela évite les appels à
isInt()qui survenaient à chaque dispatch de méthode
- La logique de traitement d’
- Gain de performance : 1 %
- À ce stade, les performances restent 29 fois plus lentes que CPython 3.10
- 65 fois plus lentes que Lua 5.4.7
- 18 fois plus lentes que QuickJS-ng 0.14.0
- 1,23 fois plus rapide que le point de départ
- Le goulot d’étranglement venait du fait que le fast path de
-
Optimisation n°4 : Symbol
- À l’origine, l’interpréteur utilisait
std::stringpresque partout - Les emplacements où l’usage de chaînes coûtait le plus cher étaient
Context::get,Context::set,Context::callFunction,Value::callMethod,Value::dot,Value::setDot,Value::callOperator<>, ainsi que la familleObject::callMethod - Avec une telle structure, l’exécution ne faisait pas un simple accès à une table de hachage, mais un accès à une table de hachage à clés chaîne, ce qui répétait hashing et comparaisons de chaînes
- L’optimisation a consisté à remplacer les recherches basées sur des chaînes par des pointeurs vers des objets
Symbolhash-consed - Une nouvelle classe
Symbola été ajoutée- Implémentée dans
symbol.hetsymbol.cpp - Symbol et chaîne sont convertibles dans les deux sens
- Lors de la conversion d’une chaîne en Symbol, le hash consing est effectué via une table de hachage globale
- Au final, il suffit de comparer l’identité des pointeurs
Symbol*pour savoir s’il s’agit du même symbole
- Implémentée dans
- Des symboles préparés à l’avance sont utilisés à la place des littéraux chaîne
- Par exemple,
Symbol::subscriptà la place de"subscript"
- Par exemple,
- De nombreuses signatures de fonctions ont été modifiées pour utiliser
Symbol*à la place deconst std::string& - Gain de performance : 18 %
- À ce stade, les performances restent 24 fois plus lentes que CPython 3.10
- 54 fois plus lentes que Lua 5.4.7
- 15 fois plus lentes que QuickJS-ng 0.14.0
- 1,46 fois plus rapide que le point de départ
- À l’origine, l’interpréteur utilisait
-
Optimisation n°5 : inlining de Value
- L’idée centrale est de permettre l’inlining des fonctions importantes
- Presque toutes les modifications s’articulent autour de l’introduction du nouveau header
valueinlines.h - La raison de la séparation avec
value.hest qu’il utilise des headers qui doivent eux-mêmes inclurevalue.h - Gain de performance : 2,8 %
- À ce stade, les performances restent 24 fois plus lentes que CPython 3.10
- 53 fois plus lentes que Lua 5.4.7
- 15 fois plus lentes que QuickJS-ng 0.14.0
- 1,5 fois plus rapide que le point de départ
Refonte du modèle objet et de la structure de cache
-
Optimisation n°6 : modèle objet, inline cache et watchpoint
- Refonte à grande échelle du fonctionnement de
Object,ClassObjectetContextafin de réduire le coût d’allocation des objets et d’éviter les recherches dans des tables de hachage lors des accès - Ce changement combine trois fonctionnalités : le modèle objet, les inline caches et les watchpoints
- Refonte à grande échelle du fonctionnement de
-
Modèle objet
- Auparavant, un objet
Contextétait alloué pour chaque portée lexicale- Chaque
Contextpossédait une table de hachage contenant les variables de cette portée
- Chaque
- Les objets avaient une structure plus complexe
- Chaque objet possédait une table de hachage associant à des
Contextles classes dont il est une instance
- Chaque objet possédait une table de hachage associant à des
- Cette structure était nécessaire à cause de l’héritage et des portées imbriquées
- Quand
Barhérite deFoo,BaretFoocapturent des portées différentes - Ils peuvent aussi avoir des champs privés différents portant le même nom
- Quand
- La nouvelle structure introduit le concept de
Storage- Les données sont stockées selon des offsets
- L’offset est déterminé par un certain
Context
Contextexiste toujours, mais il est désormais créé à l’avance lors de la passeresolvede l’AST, et non au moment de la création d’un objet ou d’une portée- Lors de la création réelle d’un objet ou d’une portée, on n’alloue plus que le Storage, dimensionné selon la taille calculée par ce
Context
- Auparavant, un objet
-
Inline cache
- Technique consistant, à un emplacement de code comme
expr.name, à mémoriser le type dynamique deexprvu la dernière fois ainsi que le dernier offset auquelnamea été résolu - Il s’agit d’une technique classique surtout décrite dans le contexte des JIT, mais elle est ici appliquée à un interpréteur
- Les informations mémorisées sont implémentées en construisant par placement, sur le nœud AST général, des nœuds AST spécialisés
- Technique consistant, à un emplacement de code comme
-
Composants de l’inline cache
CacheRecipe- Suit ce qu’un accès donné a fait et s’il peut être mis en cache
- Des appels à
CacheRecipesont insérés à divers endroits dansContext,ClassObjectetPackage- Pour collecter les informations sur le processus d’accès
- Les fonctions d’évaluation d’AST comme
Dot::evaluatetransmettent àconstructCache<>, avecthis, laCacheRecipeobtenue à partir de l’opération polymorphe qu’elles ont exécutée constructCache- Compile une nouvelle spécialisation de nœud AST selon la
CacheRecipe - Génère divers nœuds AST spécialisés via une mécanique de templates
- Pour un accès à une variable locale, effectue un chargement direct depuis le
storagereçu - Vérifie ensuite via un class check que la classe est identique à celle vue la dernière fois
- Puis effectue un appel direct de la dernière fonction observée
- Si nécessaire, combine aussi des chain steps et des watchpoints
- Compile une nouvelle spécialisation de nœud AST selon la
- Chaque nœud AST mis en cache possède sa propre variante cachée
- Il tente d’abord un appel rapide via l’objet
cache - Le type de l’objet
cacheest déterminé parconstructCache<>
- Il tente d’abord un appel rapide via l’objet
-
Watchpoint
- Présentation d’un exemple avec une variable
xdans une portée lexicale, une classeFooà l’intérieur, et une méthode deFooqui accède àx - Si
Foone contient ni fonction ni variable nomméex, on pourrait croire qu’il est possible de lire directement lexextérieur - Mais une sous-classe peut ajouter un getter
x - Dans ce cas, le résultat de l’accès ne doit plus être le
xextérieur mais le getter - Pour gérer ce type de changement possible, l’inline cache installe à l’exécution un
Watchpoint - Dans cet exemple, on utilise un watchpoint qui surveille si ce nom a été redéfini
- Présentation d’un exemple avec une variable
-
Pourquoi implémenter ces trois fonctionnalités en même temps
- Le nouveau modèle objet seul ne peut guère apporter d’amélioration significative si les inline caches ne fonctionnent pas bien
- Les inline caches eux-mêmes, sans watchpoints, ont peu d’intérêt car il est difficile de gérer en toute sécurité de nombreuses conditions de cache
- Le nouveau modèle objet et les watchpoints doivent donc bien fonctionner ensemble
-
Mise en œuvre et difficultés
- Le travail a commencé par l’écriture d’une version simple de
CacheRecipe, ainsi que par la conception de Storage et des Offsets proches de leur forme finale - L’une des tâches les plus difficiles a été de remplacer la manière d’implémenter les classes intrinsèques
- Exemple des tableaux
- Auparavant,
ArrayObject::tryCallMethodimplémentait toutes les méthodes en interceptant l’appel virtuelObject::tryCallMethod - Dans le nouveau modèle objet,
Objectn’a ni vtable ni méthode virtuelle - À la place,
Object::tryCallMethoddélègue àobject->classObject()->tryCallMethod(object, ...) - Il faut donc, pour fournir les méthodes de
Array, créer la classe Array elle-même avec ces méthodes
- Auparavant,
- En conséquence, une grande partie des fonctionnalités intrinsèques, auparavant dispersées dans l’implémentation, a été recentrée autour de
makerootcontext.cpp - Cela est jugé positif, car les fonctions natives/intrinsèques des objets bénéficient elles aussi des inline caches sans changement particulier
- Effet sur les performances : gain de 4,55x
- À ce stade, les performances sont 5,2 fois plus lentes que CPython 3.10
- 11,7 fois plus lentes que Lua 5.4.7
- 3,3 fois plus lentes que QuickJS-ng 0.14.0
- Et 6,8 fois plus rapides qu’au point de départ
- L’auteur estime que l’écart de Fil-C++ par rapport aux autres interpréteurs a été réduit, globalement, jusqu’au niveau du surcoût propre à Fil-C
- Le travail a commencé par l’écriture d’une version simple de
Optimisation des appels et des chemins d’accès
-
Optimisation n°7 : amélioration de la structure de passage des arguments
- Avant ce changement, l’interpréteur Zef transmettait les arguments de fonction sous la forme de
const std::optional<std::vector<Value>>& - La raison d’être de
optionalétait qu’il fallait distinguer les deux cas suivants dans certains cas limiteso.gettero.function()
- Dans Zef, les deux correspondent généralement à des appels de fonction, mais il existe cette exception
o.NestedClasso.NestedClass()
- Le premier renvoie l’objet
NestedClasslui-même - Le second crée une instance
- Il fallait donc distinguer un appel de fonction sans argument d’un appel de type getter avec un tableau d’arguments vide
- Mais la structure existante était inefficace
- l’appelant faisait une allocation de
vector - le callee réallouait ensuite une arguments scope qui était une copie de ce vecteur
- l’appelant faisait une allocation de
- Le changement introduit le type
Arguments- sa forme est exactement identique à l’arguments scope que le callee créait auparavant
- désormais, c’est l’appelant qui l’alloue directement sous cette forme
- Dans Yolo-C++, cela réduit aussi le nombre d’allocations en supprimant le
mallocdu backing store du vector - Dans Fil-C++,
std::optionallui-même entraîne une allocation sur le tas- même sans
std::optional, passerconst std::vector<>&entraîne aussi une allocation - ce qui serait alloué sur la pile est indiqué comme étant alloué sur le tas
- il est également mentionné que le côté appelant ne préallouait pas la taille du vecteur, ce qui provoquait plusieurs réallocations
- même sans
- Une grande partie du changement a consisté à remplacer les signatures de fonction par
Arguments* - Le gain de performances est de 1,33x
- à ce stade, les performances restent 3,9 fois plus lentes que CPython 3.10
- 8,8 fois plus lentes que Lua 5.4.7
- 2,5 fois plus lentes que QuickJS-ng 0.14.0
- et 9,05 fois plus rapides que le point de départ
- Avant ce changement, l’interpréteur Zef transmettait les arguments de fonction sous la forme de
-
Optimisation n°8 : spécialisation des getters
- Comme Ruby, Zef a des champs d’instance privés par défaut
- Exemple :
class Foo { my f fn (inF) f = inF }- la valeur reçue par le constructeur est stockée dans la variable locale
f, visible uniquement dans l’instance
- la valeur reçue par le constructeur est stockée dans la variable locale
- Même entre instances du même type, il n’est pas possible d’accéder au
fd’un autre objet- exemple :
fn nope(o) o.f println(Foo(42).nope(Foo(666)))- dans
nope,o.fne peut pas accéder aufdeo
- exemple :
- La raison est que les champs fonctionnent de la manière dont ils apparaissent dans la chaîne de scopes des membres de classe
o.fn’est pas une lecture de champ, mais une requête d’appel de méthode nomméef
- On rencontre donc souvent le motif suivant
my ffn f f- autrement dit, une méthode nommée
fqui renvoie la variable localef
- Il existe une syntaxe plus courte :
readable f- forme abrégée de
my fetfn f f
- forme abrégée de
- De nombreux appels de méthode sont en pratique des appels de getter
- Faire fonctionner tous les getters en évaluant l’AST est du gaspillage
- L’optimisation consiste en une spécialisation des getters
- le point central est
UserFunction - une nouvelle méthode
Node::inferGetterpermet d’inférer si le corps d’une fonction est un getter simple
- le point central est
- Règles d’inférence
Block::inferGetterinfère un getter si tout ce qu’il contient peut être inféré comme getterGet::inferGetters’infère lui-même comme getter et renvoie l’offset à chargerContext::tryGetFieldOffsetsne renvoie unOffsetsnon vide que si ce champ existe à coup sûr dans le scope lexical où le getter sera exécutéUserFunctionse résout en une sous-classe spécialisée deFunctionqui lit directement à l’offset connu si le corps de la fonction peut être inféré comme getter
- Le gain de performances est de 5,6 %
- à ce stade, les performances restent 3,7 fois plus lentes que CPython 3.10
- 8,3 fois plus lentes que Lua 5.4.7
- 2,4 fois plus lentes que QuickJS-ng 0.14.0
- et 9,55 fois plus rapides que le point de départ
-
Optimisation n°9 : spécialisation des setters
- L’inférence des setters nécessite un pattern matching sur
fn set_fieldName(newValue) fieldName = newValue - À l’étape d’inférence de
UserFunction, il faut transmettre le nom du paramètre du setter - À l’étape d’inférence de
Set, il faut vérifier qu’il ne s’agit pas d’une écriture dans unClassObject, et aussi que le paramètre du setter est bien utilisé comme source duset - Le gain de performances est de 3,4 %
- à ce stade, Zef est 3,6 fois plus lent que CPython 3.10
- 8 fois plus lent que Lua 5.4.7
- 2,3 fois plus lent que QuickJS-ng 0.14.0
- et 9,87 fois plus rapide que le point de départ
- L’inférence des setters nécessite un pattern matching sur
-
Optimisation n°10 : inlining de
callMethod- Une fonction importante a été inlinée avec un changement d’une seule ligne
- Le gain de performances est de 3,2 %
- à ce stade, Zef est 3,5 fois plus lent que CPython 3.10
- 7,8 fois plus lent que Lua 5.4.7
- 2,2 fois plus lent que QuickJS-ng 0.14.0
- et 10,2 fois plus rapide que le point de départ
-
Optimisation n°11 : table de hachage
- Lorsqu’un inline cache miss se produisait sur un appel de méthode, il fallait descendre dans
ClassObject::tryCallMethodetClassObject::TryCallMethodDirect, deux chemins volumineux et complexes - Le coût de recherche existant était en O(profondeur de la hiérarchie)
- pour chaque classe de la hiérarchie, une recherche dans la table de hachage vérifiait si l’appel devait être résolu comme une fonction membre
- pour chaque classe de la hiérarchie, une autre recherche dans la table de hachage vérifiait si l’appel devait être résolu comme une classe imbriquée
- Le nouveau changement introduit une table de hachage globale utilisant la classe receiver et le symbole comme clé
- un seul lookup permet de renvoyer directement le callee
- dans
classobject.h, cette table globale est consultée d’abord avant de descendre dans l’ensemble detryCallMethodSlow - dans
classobject.cpp, le résultat d’une recherche réussie est enregistré dans la table globale - l’implémentation de cette table de hachage globale reste relativement simple
- Le gain de performances est de 15 %
- à ce stade, Zef est 3 fois plus lent que CPython 3.10
- 6,8 fois plus lent que Lua 5.4.7
- 1,9 fois plus lent que QuickJS-ng 0.14.0
- et 11,8 fois plus rapide que le point de départ
- Lorsqu’un inline cache miss se produisait sur un appel de méthode, il fallait descendre dans
-
Optimisation n°12 : éviter
std::optional- Dans Fil-C++,
std::optionaldoit être alloué sur le tas à cause d’un comportement pathologique du compilateur lié aux unions - En général, LLVM traite de manière souple les types d’accès mémoire des unions, mais cela entre en conflit avec invisicaps
- il arrive que des pointeurs à l’intérieur d’une union perdent leur capability d’une manière difficilement prévisible pour le programmeur
- résultat : dans Fil-C, on peut déclencher un panic de déréférencement d’objet avec une null capability sans erreur explicite du programmeur
- Pour atténuer cela, le compilateur Fil-C++ insère des intrinsics afin que LLVM adopte un comportement conservateur lors du traitement des variables locales de type union
- Ensuite, le pass
FilPizlonatoressaie de rendre possibles des allocations en registre pour les variables locales de type union en effectuant sa propre escape analysis- mais cette analyse n’est pas aussi complète que l’analyse SROA générale de LLVM
- En conséquence, le passage de classes contenant une union, comme
std::optional, conduit souvent à des allocations mémoire dans Fil-C++ - Ce changement évite donc les chemins de code menant à
std::optionalsur le hot path - Le gain de performances est de 1,7 %
- à ce stade, Zef est 3 fois plus lent que CPython 3.10
- 6,65 fois plus lent que Lua 5.4.7
- 1,9 fois plus lent que QuickJS-ng 0.14.0
- Dans Fil-C++,
-
12 fois plus rapide que le point de départ
-
Optimisation #13 : arguments spécialisés
- Toutes les fonctions built-in de Zef prennent 1 ou 2 arguments, et dans l’implémentation native, il n’est donc pas nécessaire d’allouer un objet
Argumentspour les contenir - Les setters prennent eux aussi toujours un seul argument et, lorsqu’une inférence de setter a été effectuée, une implémentation de setter spécialisée peut également recevoir directement l’argument de valeur sans objet
Arguments - Cette modification introduit des types d’arguments spécialisés :
ZeroArguments,OneArgument,TwoArguments- le caller peut ainsi éviter l’allocation d’un objet
Argumentssi le callee n’en a pas besoin
- le caller peut ainsi éviter l’allocation d’un objet
ZeroArgumentsest nécessaire pour le distinguer de(Arguments*)nullptr- auparavant,
(Arguments*)nullptrétait utilisé pour signifier un appel de getter, et cette logique est conservée - désormais,
ZeroArgumentssignifie un appel de fonction sans argument
- auparavant,
- Une grande partie des changements consiste à templatiser les fonctions qui reçoivent des arguments
- une instanciation explicite est effectuée pour
ZeroArguments,OneArgument,TwoArgumentsetArguments* - une bonne partie du code existant utilisait
Value::getArgcomme helper d’extraction des arguments, et des surcharges pour les arguments spécialisés y ont été ajoutées - les modifications du code natif qui utilise des arguments ont été relativement directes
- une instanciation explicite est effectuée pour
- Le gain de performances est de 3,8 %
- à ce stade, Zef est 2,9 fois plus lent que CPython 3.10
- 6,4 fois plus lent que Lua 5.4.7
- 1,8 fois plus lent que QuickJS-ng 0.14.0
- 12,4 fois plus rapide que le point de départ
- Toutes les fonctions built-in de Zef prennent 1 ou 2 arguments, et dans l’implémentation native, il n’est donc pas nécessaire d’allouer un objet
Contournement des pathologies de Fil-C et spécialisations fines
-
Optimisation #14 : amélioration de la slow path de
Value- Un autre contournement d’une pathologie de Fil-C a permis un important gain de vitesse
- Avant la modification, la slow path out-of-line de
Valueétait une fonction membre deValueet nécessitait un argument implicite de typeconst Value* - Avec cette structure, l’appelant devait allouer
Valuesur la pile - En Fil-C++, toutes les allocations sur la pile sont des allocations sur le tas
- Le code appelant la slow path allouait donc
Valuesur le tas
- Le code appelant la slow path allouait donc
- Après la modification, ces méthodes ont été rendues
staticetValueest passé par valeur- Résultat : plus besoin d’allocation séparée
- Impact sur les performances : +10 %
- À ce stade, Zef est 2,6 fois plus lent que CPython 3.10
- 5,8 fois plus lent que Lua 5.4.7
- 1,65 fois plus lent que QuickJS-ng 0.14.0
- 13,6 fois plus rapide que le point de départ
-
Optimisation #15 : déduplication de
DotSetRMW- Suppression d’une partie du code dupliqué
- L’idée était qu’une réduction du code machine dans les fonctions template spécialisées par
constructCache<>pourrait être bénéfique - Résultat réel : aucun impact sur les performances
-
Optimisation #16 : spécialisation de
sqrt- L’inline cache redirige efficacement les appels vers la fonction voulue, mais ne fonctionne que pour les objets
- Pour les non-objets, les fast paths de
Binary<>,Unary<>etValue::callRMW<>reposent sur une vérification indiquant si le receiver est unintou undouble - Cette approche ne s’applique qu’aux opérateurs reconnus par le parseur
- Elle ne s’applique donc pas à une forme comme
value.sqrt
- Elle ne s’applique donc pas à une forme comme
- Avec cette modification,
Dotpeut être spécialisé pourvalue.sqrt - Impact sur les performances : +1,6 %
- À ce stade, Zef est 2,6 fois plus lent que CPython 3.10
- 5,75 fois plus lent que Lua 5.4.7
- 1,6 fois plus lent que QuickJS-ng 0.14.0
- 13,8 fois plus rapide que le point de départ
-
Optimisation #17 : spécialisation de
toString- Application d’une spécialisation de
toStringpresque identique à l’optimisation précédente - Cette modification inclut une logique réduisant le nombre d’allocations lors de la conversion d’un
inten chaîne - Impact sur les performances : +2,7 %
- À ce stade, Zef est 2,5 fois plus lent que CPython 3.10
- 5,6 fois plus lent que Lua 5.4.7
- 1,6 fois plus lent que QuickJS-ng 0.14.0
- 14,2 fois plus rapide que le point de départ
- Application d’une spécialisation de
-
Optimisation #18 : spécialisation des littéraux de tableau
- Un code comme
my whatever = [1, 2, 3]doit allouer un nouveau tableau dans Zef, car les tableaux y sont aliasables et mutables - Avant la modification, l’exécution redescendait l’AST à chaque fois et réévaluait récursivement
1,2,3 - Cette modification spécialise le nœud
ArrayLiteralpour le cas d’allocation d’un tableau constant - Impact sur les performances : +8,1 %
- À ce stade, Zef est 2,3 fois plus lent que CPython 3.10
- 5,2 fois plus lent que Lua 5.4.7
- 1,5 fois plus lent que QuickJS-ng 0.14.0
- 15,35 fois plus rapide que le point de départ
- Un code comme
-
Optimisation #19 : amélioration de
Value::callOperator- La même optimisation que celle qui avait déjà apporté un gain en ne passant pas
Valuepar référence a aussi été appliquée à la slow path decallOperator - Impact sur les performances : +6,5 %
- À ce stade, Zef est 2,2 fois plus lent que CPython 3.10
- 4,9 fois plus lent que Lua 5.4.7
- 1,4 fois plus lent que QuickJS-ng 0.14.0
- 16,3 fois plus rapide que le point de départ
- La même optimisation que celle qui avait déjà apporté un gain en ne passant pas
-
Optimisation #20 : meilleures options C++
- En Fil-C++, désactivation du RTTI inutile et du hardening de libc++
- Aucune modification du code C++ lui-même, uniquement des changements de configuration du système de build
- Impact sur les performances : +1,8 %
- À ce stade, Zef est 2,1 fois plus lent que CPython 3.10
- 4,8 fois plus lent que Lua 5.4.7
- 1,35 fois plus lent que QuickJS-ng 0.14.0
- 16,6 fois plus rapide que le point de départ
-
Optimisation #21 : désactivation des assertions
- En dernière optimisation, les assertions ont été désactivées par défaut
- Le code existant utilisait la macro
ZASSERTpropre à Fil-C- Dans cette structure, les assertions étaient toujours exécutées
- Après la modification, la macro interne
ASSERTest utilisée- Les assertions ne sont exécutées que si
ASSERTS_ENABLEDest défini
- Les assertions ne sont exécutées que si
- Cette modification inclut aussi d’autres changements permettant au code d’être compilé avec Yolo-C++
- Contre toute attente : aucun gain de vitesse
Résultats et limites de Yolo-C++
- La compilation du code avec Yolo-C++ a permis un gain de vitesse de x4
- Mais cette approche est non sound et suboptimal
- Elle n’est pas sound parce que les appels au GC de Fil-C++ sont remplacés par des appels à
calloc - En conséquence, la mémoire n’est pas libérée, et sur des charges suffisamment longues, l’interpréteur finit par épuiser la mémoire
- Dans ScriptBench1, la durée de test est trop courte pour provoquer un épuisement mémoire
- Elle n’est pas sound parce que les appels au GC de Fil-C++ sont remplacés par des appels à
- Elle est suboptimal parce que le véritable allocateur du GC est en réalité plus rapide que
callocde glibc 2.35 - L’article indique donc qu’en ajoutant le vrai GC au port Yolo-C++, il serait possible d’obtenir un gain supérieur à x4
- Cette expérience a été réalisée avec GCC 11.4.0
- À ce stade, Zef est
-
1,9 fois plus rapide que CPython 3.10
-
1,2 fois plus lent que Lua 5.4.7
-
3 fois plus rapide que QuickJS-ng 0.14.0
- 67 fois plus rapide que le point de départ
-
Données brutes de benchmark
- L’unité du temps d’exécution des benchmarks est la seconde
- Le tableau inclut, pour chaque interpréteur,
nbody,splay,richards,deltablue,geomean -
Python 3.10
nbody0.0364splay0.8326richards0.0822deltablue0.1135geomean0.1296
-
Lua 5.4.7
nbody0.0142splay0.4393richards0.0217deltablue0.0832geomean0.0577
-
QuickJS-ng 0.14.0
nbody0.0214splay0.7090richards0.7193deltablue0.1585geomean0.2036
-
Zef Baseline
nbody2.9573splay13.0286richards1.9251deltablue5.9997geomean4.5927
-
Zef Changement n°1 : Opérateurs directs
nbody2.1891splay12.0233richards1.6935deltablue5.2331geomean3.9076
-
Zef Changement n°2 : RMW directs
nbody2.0130splay11.9987richards1.6367deltablue5.0994geomean3.7677
-
Zef Changement n°3 : Éviter IntObject
nbody1.9922splay11.8824richards1.6220deltablue5.0646geomean3.7339
-
Zef Changement n°4 : Symboles
nbody1.5782splay9.9577richards1.4116deltablue4.4593geomean3.1533
-
Zef Changement n°5 : Value Inline
nbody1.4982splay9.7723richards1.3890deltablue4.3536geomean3.0671
-
Zef Changement n°6 : Modèle objet et caches inline
nbody0.3884splay3.3609richards0.2321deltablue0.6805geomean0.6736
-
Zef Changement n°7 : Arguments
nbody0.3160splay2.6890richards0.1653deltablue0.4738geomean0.5077
-
Zef Changement n°8 : Getters
nbody0.2988splay2.6919richards0.1564deltablue0.4260geomean0.4809
-
Zef Changement n°9 : Setters
nbody0.2850splay2.6690richards0.1514deltablue0.4072geomean0.4651
-
Zef Changement n°10 :
callMethodinlinenbody0.2533splay2.6711richards0.1513deltablue0.4032geomean0.4506
-
Zef Changement n°11 : Hashtable
nbody0.1796splay2.6528richards0.1379deltablue0.3551geomean0.3906
-
Zef Changement n°12 : Éviter
std::optionalnbody0.1689splay2.6563richards0.1379deltablue0.3518geomean0.3839
-
Zef Changement n°13 : Arguments spécialisés
nbody0.1610splay2.5823richards0.1350deltablue0.3372geomean0.3707
-
Zef Changement n°14 : Amélioration des chemins lents de Value
nbody0.1348splay2.5062richards0.1241deltablue0.3076geomean0.3367
-
Zef Changement n°15 :
DotSetRMW::evaluatedédupliquénbody0.1342splay2.5047richards0.1256deltablue0.3079geomean0.3375
-
Zef Changement n°16 :
sqrtrapidenbody0.1274splay2.5045richards0.1251deltablue0.3060geomean0.3322
-
Zef Changement n°17 :
toStringrapidenbody0.1282splay2.2664richards0.1275deltablue0.2964geomean0.3235
-
Zef Changement n°18 : Spécialisation des littéraux de tableau
nbody0.1295splay1.6661richards0.1250deltablue0.2979geomean0.2992
-
Zef Changement n°19 : Optimisation de
callOperatorde Valuenbody0.1208splay1.6698richards0.1143deltablue0.2713geomean0.2810
-
Zef Changement n°20 : Meilleure configuration C++
nbody0.1186splay1.6521richards0.1127deltablue0.2635geomean0.2760
-
Zef Changement n°21 : Sans assertions
nbody0.1194splay1.6504richards0.1127deltablue0.2619geomean0.2759
-
Zef en Yolo-C++
nbody0.0233splay0.3992richards0.0309deltablue0.0784geomean0.0686
1 commentaires
Commentaires sur Hacker News
Dans le même esprit, cette page sur les performances de l’interpréteur Wren était assez intéressante
Là où l’article sur Zef se concentre sur les techniques d’implémentation, le côté Wren montre aussi comment la conception du langage elle-même contribue aux performances
J’ai notamment trouvé intéressant que Wren renonce aux dynamic object shapes, ce qui permet le copy-down inheritance et simplifie beaucoup la résolution de méthodes
Personnellement, ça me semble être un compromis tout à fait raisonnable. Une fois une classe créée, à quelle fréquence a-t-on réellement besoin de lui ajouter des méthodes ?
Il existe beaucoup de VM très optimisées pour les langages dynamiques, mais si LuaJIT est si fort, c’est aussi parce que Lua est un langage très petit et très bien adapté à l’optimisation
Il y a bien quelques fonctionnalités difficiles à optimiser, mais elles sont peu nombreuses, donc ça vaut la peine d’y investir des efforts
Python, en revanche, me paraît complètement différent. En forçant un peu le trait, on dirait presque qu’il a été conçu pour minimiser les chances d’un JIT rapide, tant les couches de dynamicité s’empilent et rendent l’optimisation vraiment difficile
Le fait qu’après tant d’années de travail, le JIT de CPython 3.15 sur x86_64 ne soit qu’environ 5 % plus rapide que l’interpréteur par défaut l’illustre assez bien
Cela dit, Ruby n’est pas non plus réputé pour faire de la vitesse sa priorité absolue
À l’inverse, l’idée qu’un type possède un ensemble fermé de fonctions applicables me laisse aussi un peu perplexe
Il existe pas mal de langages où l’on peut définir une fonction arbitraire puis l’utiliser comme une méthode en notation pointée sur une variable dont le type du premier argument correspond
On peut citer par exemple les macros de Nim, les implicit classes et type classes de Scala, les extension functions de Kotlin, ou encore les traits de Rust
Les langages dynamiques complexes sabotent activement cette possibilité de multiples façons, ce qui rend l’optimisation plus difficile
Avec le recul, cela paraît assez évident
En passant du changement #5 au #6, le fait que l’essentiel du gain de performance vienne des inline caches et du modèle objet à hidden classes m’a vraiment rappelé la manière dont V8 ou JSC sont historiquement devenus rapides
Le point où un interpréteur naïf s’effondre, au final, c’est le dispatch dynamique lors de l’accès aux propriétés ; le reste donne presque l’impression d’un rounding error
J’ai aussi apprécié que ce soit présenté de façon à montrer la contribution de chaque étape. Souvent, les articles sur les performances se contentent de jeter le chiffre final et s’arrêtent là
Dans un interpréteur à bytecode, il suffit de patcher un offset stable dans le flux de bytecode, donc l’endroit où réécrire l’IC est assez naturel
Mais ici, l’emplacement du cache est le nœud AST lui-même, et j’ai trouvé marquant que @pizlonator utilise
constructCache<>pour construire sur place des nœuds AST spécialisés au-dessus de nœuds génériquesAu final, ça ressemble à une forme de code auto-modifiant au niveau de l’AST
En contrepartie, cette approche exige des nœuds AST mutables, ce qui entre en conflit avec l’hypothèse d’AST immuables sur laquelle beaucoup de compilateurs s’appuient pour le partage de sous-arbres ou la compilation parallèle
Pour un interpréteur mono-thread, c’est élégant, mais si l’interpréteur modifie les nœuds pendant qu’un thread de fond compile le même AST en JIT, cela semble pouvoir poser problème
À mon avis, il ne représente peut-être pas si bien que ça la majorité du code réel en production
Ce qui me l’a fait penser, c’est le passage où l’optimisation de sqrt apporte 1,6 % d’amélioration
Pour obtenir un tel gain, il faut forcément qu’au moins 1,6 % du temps du benchmark soit déjà consacré à cela, ce qui m’a paru assez surprenant
En regardant le dépôt git, il semble qu’effectivement cela se produise dans la simulation nbody
J’ai lu ça avec encore plus d’intérêt parce que je venais justement de publier la première version de mon propre AST-walking interpreter
Mon objectif était de comprendre, au niveau le plus fondamental, ce qu’il faut pour construire un langage interprété
Je ne voulais pas introduire la complexité des optimisations ; je voulais surtout écrire du Rust que je puisse comprendre moi-même
Mais j’ai été surpris de voir que les performances étaient déjà plutôt bonnes simplement parce que j’utilisais Rust, un langage que j’apprécie
Et le fait que Rust gère ownership et lifetimes m’a donné en prime l’impression de ne pas avoir besoin d’un garbage collector séparé
Bien sûr, pour le moment, sur des aspects comme les closures, je m’appuie de façon assez conservatrice sur
clonepour éviter l’enfer des lifetimes, mais malgré ça, le profil de vitesse et de mémoire me paraît tout à fait correctSi quelqu’un s’intéresse à un tree-walking interpreter simple, facile à comprendre, et basé sur Rust, il peut jeter un œil à mon interpréteur gluonscript
L’article était vraiment excellent
J’ai particulièrement trouvé que l’arc autour d’Arguments, c’est-à-dire la progression de #7 à #13, rejoignait très directement ma propre expérience
Il y a quelque temps, en écrivant en Rust un async step evaluator, j’étais parti du principe que l’emprunt m’apporterait un gain et je m’étais fortement engagé dans
Cow<'_, Input>Sur les microbenchmarks, cela avait l’air bon, mais sur les charges réelles, le discriminant de Cow et toute la complexité liée aux lifetimes se sont propagés à tous les combinators après le premier
await, l’inlining s’est fortement dégradé, et la raison même d’utiliser Cow a disparuJ’ai fini par basculer à la frontière de l’evaluator vers
NoInput / OneInput / MultiInput(Vec); c’était plus rustique visuellement, mais au final j’étais arrivé presque exactement au même point que la séparation ZeroArguments / OneArgument / TwoArguments iciUne question continue de m’intriguer : sur le chemin natif, avez-vous empilé de la spécialisation de type au-dessus de la spécialisation d’arité ?
Par exemple, dans un style binaire, on pourrait peut-être supprimer complètement le test
isIntJ’imagine soit que le calcul taille de code/performance n’était pas favorable, soit que du côté objet les IC capturaient déjà suffisamment bien les chemins chauds, si bien que l’impact du fast path natif n’était pas très grand
Je me demandais lequel des deux cas s’appliquait
C’est un travail vraiment intéressant et très réussi
J’ai moi aussi fait quelque chose d’assez similaire, mais du côté de Scheme, donc avec un langage plus proche du fonctionnel
Ici, c’est l’optimisation des objets qui a donné le plus gros gain, mais dans mon cas, c’était surtout l’optimisation des closures qui faisait la différence
Fait amusant, les méthodes d’optimisation elles-mêmes étaient assez proches
À mon avis, la réponse à la question de savoir comment rendre Scheme suffisamment rapide se trouve en grande partie dans Three implementation models for scheme
Cela dit, ce travail passe dans une certaine mesure par une étape de compilation, donc ce n’est pas un modèle qui interprète directement l’AST original tel quel
C’était intéressant, merci d’avoir partagé
Ça m’a donné envie de creuser ce sujet en détail un jour
Et j’ai aussi trouvé assez drôle et marquant que, d’après GitHub, le dépôt soit à 99,7 % HTML et 0,3 % C++
On dirait presque une preuve que l’interpréteur est vraiment minuscule
La façon dont le code pour le navigateur est généré gonfle inutilement la partie site
Cela dit, l’interpréteur lui-même est vraiment tout petit
Je me demandais si ce travail vous avait appris quelque chose qui pourrait servir à améliorer fil c lui-même
Et j’ai aussi appris que le coût des appels outline pour les méthodes des value objects est assez élevé
J’ai vu que Lua était inclus, mais je me suis dit que ce serait bien d’avoir aussi LuaJIT
En fait, vu le niveau d’ingénierie qu’il y a derrière, c’est même ce à quoi je m’attendrais
Il y avait beaucoup de runtimes qu’on aurait pu inclure, mais on ne les a pas tous mis
Et le fait que PUC Lua soit nettement plus rapide que QuickJS ou Python était aussi assez impressionnant
Je me demandais ce que cela donne en pratique d’utiliser Fil-C, et s’il y a une utilité réelle en conditions réelles
Cela dit, sur ce projet, cela m’a été utile de manière très concrète
Cela a permis d’attraper de façon déterministe plusieurs problèmes de sûreté mémoire, ce qui a rendu la conception du modèle objet bien plus simple que cela ne l’aurait été autrement
Et du C++ avec GC précise m’a vraiment semblé offrir un excellent modèle de programmation
J’avais l’impression d’être environ 1,5× plus productif qu’en C++ classique, et même par rapport à d’autres langages avec GC, j’avais le sentiment d’aller environ 1,2× plus vite
Je pense que c’est parce que l’écosystème d’API de C++ est riche, et que les lambdas, templates et le système de classes sont extrêmement mûrs
Bien sûr, je reconnais aussi que je suis biaisé de plusieurs façons
J’ai moi-même créé Fil-C++, et j’utilise C++ depuis environ 35 ans
Je me demandais ce que désignait le compilateur YOLO-C/C++ mentionné dans l’article
Je n’ai rien trouvé de très concluant en cherchant, et même chatgpt n’avait pas l’air de savoir