Comment créer un interpréteur rapide pour un langage dynamique

• 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 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 0xffff000000000000 sur les entiers
  • 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

• 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

• 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::evaluate redéfinie à plusieurs endroits
  • Abus de chaînes de caractères
    • Le nœud AST Get stocke une std::string décrivant le nom de variable
    • Cette chaîne est utilisée à chaque accès à la variable
  • Abus de tables de hachage
    • L’exécution de Get effectue une recherche dans std::unordered_map avec une clé de type chaîne
  • 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

• 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 DotCall portant le nom de l’opérateur, mais génère à la place des nœuds AST distincts pour chaque opérateur
  • Dans Zef, a + b et a.add(b) sont identiques
    • À l’origine, a + b était parsé comme DotCall(a, "add") avec l’argument b
    • Chaque opération arithmétique entraînait une recherche de chaîne du nom de la méthode d’opérateur
    • DotCall transmettait cette chaîne à Value::callMethod
    • Value::callMethod effectuait plusieurs comparaisons de chaînes
  • Après modification, le parseur génère des nœuds Binary<> et Unary<>
    • Des templates et des lambdas sont utilisés pour fournir des surcharges distinctes de Node::evaluate selon l’opérateur
    • Chaque nœud appelle directement le fast path de Value correspondant à cet opérateur
    • Par exemple, a + b appelle Binary<lambda for add>::evaluate, puis Value::add
  • 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

• Optimisation n°2 : appel direct des opérateurs RMW

  • Les opérateurs classiques sont devenus plus rapides, mais les formes RMW comme a += b utilisaient 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]
  • Chaque appel virtuel utilise la macro SPECIALIZE_NEW_RMW
    • SetRMW pour id += value
    • DotSetRMW pour expr.id += value
    • SubscriptRMW pour expr[index] += value
  • 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, dot et subscript, 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
  • 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

• Optimisation n°3 : éviter les vérifications IntObject

  • Le goulot d’étranglement venait du fait que le fast path de Value utilise isInt(), dont le isIntSlow() interne effectue un appel virtuel à Object::isInt()
  • La représentation initiale des valeurs comportait quatre cas
    • tagged int32
    • tagged double
    • IntObject pour les int64 impossibles à représenter en int32
    • tous les autres objets
  • Même dans le cas d’IntObject, c’était Value qui 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
  • Après optimisation, le fast path de Value ne prend en compte que int32 et double
    • La logique de traitement d’IntObject a été déplacée dans IntObject lui-même
    • Cela évite les appels à isInt() qui survenaient à chaque dispatch de méthode
  • 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

• Optimisation n°4 : Symbol

  • À l’origine, l’interpréteur utilisait std::string presque 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 famille Object::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 Symbol hash-consed
  • Une nouvelle classe Symbol a été ajoutée
    • Implémentée dans symbol.h et symbol.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
  • 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"
  • De nombreuses signatures de fonctions ont été modifiées pour utiliser Symbol* à la place de const 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

• 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.h est qu’il utilise des headers qui doivent eux-mêmes inclure value.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, ClassObject et Context afin 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

• Modèle objet

  • Auparavant, un objet Context était alloué pour chaque portée lexicale
    • Chaque Context possédait une table de hachage contenant les variables de cette portée
  • Les objets avaient une structure plus complexe
    • Chaque objet possédait une table de hachage associant à des Context les classes dont il est une instance
  • Cette structure était nécessaire à cause de l’héritage et des portées imbriquées
    • Quand Bar hérite de Foo, Bar et Foo capturent des portées différentes
    • Ils peuvent aussi avoir des champs privés différents portant le même nom
  • 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
  • Context existe toujours, mais il est désormais créé à l’avance lors de la passe resolve de 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

• Inline cache

  • Technique consistant, à un emplacement de code comme expr.name, à mémoriser le type dynamique de expr vu la dernière fois ainsi que le dernier offset auquel name a é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

• 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 à CacheRecipe sont insérés à divers endroits dans Context, ClassObject et Package
    • Pour collecter les informations sur le processus d’accès
  • Les fonctions d’évaluation d’AST comme Dot::evaluate transmettent à constructCache<>, avec this, la CacheRecipe obtenue à 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 storage reç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
  • 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 cache est déterminé par constructCache<>

• Watchpoint

  • Présentation d’un exemple avec une variable x dans une portée lexicale, une classe Foo à l’intérieur, et une méthode de Foo qui accède à x
  • Si Foo ne contient ni fonction ni variable nommée x, on pourrait croire qu’il est possible de lire directement le x exté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 x exté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

• 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::tryCallMethod implémentait toutes les méthodes en interceptant l’appel virtuel Object::tryCallMethod
    • Dans le nouveau modèle objet, Object n’a ni vtable ni méthode virtuelle
    • À la place, Object::tryCallMethod dé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
  • 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

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 limites
    • o.getter
    • o.function()
  • Dans Zef, les deux correspondent généralement à des appels de fonction, mais il existe cette exception
    • o.NestedClass
    • o.NestedClass()
  • Le premier renvoie l’objet NestedClass lui-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
  • 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 malloc du backing store du vector
  • Dans Fil-C++, std::optional lui-même entraîne une allocation sur le tas
    • même sans std::optional, passer const 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
  • 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

• 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
  • Même entre instances du même type, il n’est pas possible d’accéder au f d’un autre objet
    • exemple : fn nope(o) o.f
    • println(Foo(42).nope(Foo(666)))
    • dans nope, o.f ne peut pas accéder au f de o
  • 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.f n’est pas une lecture de champ, mais une requête d’appel de méthode nommée f
  • On rencontre donc souvent le motif suivant
    • my f
    • fn f f
    • autrement dit, une méthode nommée f qui renvoie la variable locale f
  • Il existe une syntaxe plus courte : readable f
    • forme abrégée de my f et fn f f
  • 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::inferGetter permet d’inférer si le corps d’une fonction est un getter simple
  • Règles d’inférence
    • Block::inferGetter infère un getter si tout ce qu’il contient peut être inféré comme getter
    • Get::inferGetter s’infère lui-même comme getter et renvoie l’offset à charger
    • Context::tryGetFieldOffsets ne renvoie un Offsets non vide que si ce champ existe à coup sûr dans le scope lexical où le getter sera exécuté
    • UserFunction se résout en une sous-classe spécialisée de Function qui 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 un ClassObject, et aussi que le paramètre du setter est bien utilisé comme source du set
  • 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

• 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::tryCallMethod et ClassObject::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 de tryCallMethodSlow
    • 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

• Optimisation n°12 : éviter std::optional

  • Dans Fil-C++, std::optional doit ê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 FilPizlonator essaie 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::optional sur 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

• 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 Arguments pour 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 Arguments si le callee n’en a pas besoin
  • ZeroArguments est 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, ZeroArguments signifie un appel de fonction sans argument
  • Une grande partie des changements consiste à templatiser les fonctions qui reçoivent des arguments
    • une instanciation explicite est effectuée pour ZeroArguments, OneArgument, TwoArguments et Arguments*
    • une bonne partie du code existant utilisait Value::getArg comme 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
  • 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

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 de Value et nécessitait un argument implicite de type const Value*
  • Avec cette structure, l’appelant devait allouer Value sur 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 Value sur le tas
  • Après la modification, ces méthodes ont été rendues static et Value est 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<> et Value::callRMW<> reposent sur une vérification indiquant si le receiver est un int ou un double
  • Cette approche ne s’applique qu’aux opérateurs reconnus par le parseur
    • Elle ne s’applique donc pas à une forme comme value.sqrt
  • Avec cette modification, Dot peut être spécialisé pour value.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 toString presque identique à l’optimisation précédente
  • Cette modification inclut une logique réduisant le nombre d’allocations lors de la conversion d’un int en 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

• 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 ArrayLiteral pour 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

• Optimisation #19 : amélioration de Value::callOperator

  • La même optimisation que celle qui avait déjà apporté un gain en ne passant pas Value par référence a aussi été appliquée à la slow path de callOperator
  • 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

• 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 ZASSERT propre à Fil-C
    • Dans cette structure, les assertions étaient toujours exécutées
  • Après la modification, la macro interne ASSERT est utilisée
    • Les assertions ne sont exécutées que si ASSERTS_ENABLED est défini
  • 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 est suboptimal parce que le véritable allocateur du GC est en réalité plus rapide que calloc de 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

  • nbody 0.0364
  • splay 0.8326
  • richards 0.0822
  • deltablue 0.1135
  • geomean 0.1296

• Lua 5.4.7

  • nbody 0.0142
  • splay 0.4393
  • richards 0.0217
  • deltablue 0.0832
  • geomean 0.0577

• QuickJS-ng 0.14.0

  • nbody 0.0214
  • splay 0.7090
  • richards 0.7193
  • deltablue 0.1585
  • geomean 0.2036

• Zef Baseline

  • nbody 2.9573
  • splay 13.0286
  • richards 1.9251
  • deltablue 5.9997
  • geomean 4.5927

• Zef Changement n°1 : Opérateurs directs

  • nbody 2.1891
  • splay 12.0233
  • richards 1.6935
  • deltablue 5.2331
  • geomean 3.9076

• Zef Changement n°2 : RMW directs

  • nbody 2.0130
  • splay 11.9987
  • richards 1.6367
  • deltablue 5.0994
  • geomean 3.7677

• Zef Changement n°3 : Éviter IntObject

  • nbody 1.9922
  • splay 11.8824
  • richards 1.6220
  • deltablue 5.0646
  • geomean 3.7339

• Zef Changement n°4 : Symboles

  • nbody 1.5782
  • splay 9.9577
  • richards 1.4116
  • deltablue 4.4593
  • geomean 3.1533

• Zef Changement n°5 : Value Inline

  • nbody 1.4982
  • splay 9.7723
  • richards 1.3890
  • deltablue 4.3536
  • geomean 3.0671

• Zef Changement n°6 : Modèle objet et caches inline

  • nbody 0.3884
  • splay 3.3609
  • richards 0.2321
  • deltablue 0.6805
  • geomean 0.6736

• Zef Changement n°7 : Arguments

  • nbody 0.3160
  • splay 2.6890
  • richards 0.1653
  • deltablue 0.4738
  • geomean 0.5077

• Zef Changement n°8 : Getters

  • nbody 0.2988
  • splay 2.6919
  • richards 0.1564
  • deltablue 0.4260
  • geomean 0.4809

• Zef Changement n°9 : Setters

  • nbody 0.2850
  • splay 2.6690
  • richards 0.1514
  • deltablue 0.4072
  • geomean 0.4651

• Zef Changement n°10 : callMethod inline

  • nbody 0.2533
  • splay 2.6711
  • richards 0.1513
  • deltablue 0.4032
  • geomean 0.4506

• Zef Changement n°11 : Hashtable

  • nbody 0.1796
  • splay 2.6528
  • richards 0.1379
  • deltablue 0.3551
  • geomean 0.3906

• Zef Changement n°12 : Éviter std::optional

  • nbody 0.1689
  • splay 2.6563
  • richards 0.1379
  • deltablue 0.3518
  • geomean 0.3839

• Zef Changement n°13 : Arguments spécialisés

  • nbody 0.1610
  • splay 2.5823
  • richards 0.1350
  • deltablue 0.3372
  • geomean 0.3707

• Zef Changement n°14 : Amélioration des chemins lents de Value

  • nbody 0.1348
  • splay 2.5062
  • richards 0.1241
  • deltablue 0.3076
  • geomean 0.3367

• Zef Changement n°15 : DotSetRMW::evaluate dédupliqué

  • nbody 0.1342
  • splay 2.5047
  • richards 0.1256
  • deltablue 0.3079
  • geomean 0.3375

• Zef Changement n°16 : sqrt rapide

  • nbody 0.1274
  • splay 2.5045
  • richards 0.1251
  • deltablue 0.3060
  • geomean 0.3322

• Zef Changement n°17 : toString rapide

  • nbody 0.1282
  • splay 2.2664
  • richards 0.1275
  • deltablue 0.2964
  • geomean 0.3235

• Zef Changement n°18 : Spécialisation des littéraux de tableau

  • nbody 0.1295
  • splay 1.6661
  • richards 0.1250
  • deltablue 0.2979
  • geomean 0.2992

• Zef Changement n°19 : Optimisation de callOperator de Value

  • nbody 0.1208
  • splay 1.6698
  • richards 0.1143
  • deltablue 0.2713
  • geomean 0.2810

• Zef Changement n°20 : Meilleure configuration C++

  • nbody 0.1186
  • splay 1.6521
  • richards 0.1127
  • deltablue 0.2635
  • geomean 0.2760

• Zef Changement n°21 : Sans assertions

  • nbody 0.1194
  • splay 1.6504
  • richards 0.1127
  • deltablue 0.2619
  • geomean 0.2759

• Zef en Yolo-C++

  • nbody 0.0233
  • splay 0.3992
  • richards 0.0309
  • deltablue 0.0784
  • geomean 0.0686