Cet article est issu du blog de Luke Wagner. L’article original a été écrit en anglais par Luke Wagner.
J’ai récemment fini un projet visant à améliorer la manière dont SpiderMonkey implémente les accès de variable, ainsi j’ai pensé qu’il était temps d’expliquer comment cela fonctionne désormais. En m’inspirant du billet de mraleph ainsi que du livre Structure et Interprétation de Programmes, je vais illustrer l’implémentation en utilisant JavaScript comme langage d’implémentation. Par conséquent, je vais traduire du JavaScript qui utilise des accès de variable complexe en du JavaScript qui n’en utilise pas, un peu comme les premiers compilateurs C++ traduisaient le C++ vers du C.
Avant de commencer, laissez-moi vous montrer l’étendue du problème. Par variable, je me réfère non seulement aux variables introduites par var, mais aussi à celles introduites par let, const, catch, les déclarations de fonction, et les arguments des fonctions. Par accès de variable, je veux dire une lecture ou une écriture. Un accès de variable peut prendre l’une des formes suivantes :
- Un accès local (c.-à-d. un accès à une variable dans la même fonction) :
function add(x,y) { return x+y }
- Un accès non local (c.-à-d. un accès à une variable d’une fonction englobante) :
function add(x,y) { return (function() { return x+y })() }
- Un accès depuis du code généré dynamiquement :
function add(x,y) { return eval("x+y") }
- Un accès après une modification dynamique de portée via un eval direct non strict :
function add(a,b) { eval("var x="+a+", y="+b); return x+y }
- Un accès dynamique aux arguments de la fonction via l’objet arguments :
function add(x,y) { return arguments[0]+arguments[1] }
- Une inspection inattendue par un débogueur (via Firebug, la nouvelle primitive de débogage de Firefox, ou directement depuis du JavaScript privilégié utilisant la nouvelle interface Debugger) :
dbg.onDebugerStatement = function(f) { return f.eval("x+y") }
Afin de ne pas allonger ce petit billet de façon démesurée, je vais prétendre/supposer qu’il y a seulement des evals (non strict, direct) et ignorer les evals stricts et indirects ainsi que le mot-clé with (qui généralement désoptimise comme si c’était un eval). Je vais aussi ignorer les let et les optimisations des accès de variables globales, ainsi que les bizarreries que SpiderMonkey fait pour la portée des fonctions et pour le débogueur.
Le pire des cas
Pour s’en sortir, nous devons avant tout voir jusqu’à quel niveau de détail on doit aller dans le pire des cas. Considérons la fonction suivante :
function bizarre() {
eval("var x = 42");
return function xPlus1() { var z = x + 1; return z }
}
Ici, eval ajoute dynamiquement x à la portée de la fonction bizarre où il sera lu par xPlus1. Vu que eval peut aussi être appelé avec une chaîne construite dynamiquement, on doit, en général, traiter la portée d’une fonction comme un tableau associatif de noms de variables vers les valeurs de chacune. (Fait intéressant, les noms de variables rajoutés avec eval peuvent être supprimés en utilisant le mot clé delete, ainsi ce tableau associatif peut grossir et se réduire lors de l’exécution !) Afin de rendre cela un peu plus concret, nous allons implémenter les portées en JavaScript en utilisant les objets Map de ES6. Nous allons donner à chaque fonction son propre tableau associatif qui sera stocké dans une variable locale nommée « portée ». (Oui, nous utilisons une variable pour implémenter des variables ; mais nous allons seulement utiliser un petit nombre fini d’entre elles, on peut les voir comme des registres.)
function bizarre() {
// la portée de 'bizarre' est initialement vide.
var portée = new Map;
// eval("var x = 42") correspond à l'exécution de :
portée.set('x', 42);
return function xPlus1() {
// les vars sont remontées, donc la portée initialement contient 'z'.
var portée = new Map([['z', undefined]]);
// var z = x + 1
portée.set('z', portée.get('x') + 1); // oops!
// retourne z
return portée.get('z');
}
}
Comme le commentaire l’indique, il y a un problème dans xPlus1 : x n’est pas dans la portée de la fonction xPlus1, il est dans la portée de bizarre ! Pour corriger cela nous devons faire deux choses :
- Ajouter une propriété englobant à toutes les portées indiquant la portée de la fonction englobante (ou l’objet global si la fonction n’est pas englobée). Dans le code précédent la fonction bizarre n’est pas englobée (car globale) mais elle englobe la fonction xPlus1.
- Remplacer les utilisations de portée.get par un algorithme de recherche qui parcourt la liste chaînée de portées.
function bizarre() {
// la portée de 'bizarre' est initialement vide.
var portée = new Map;
portée.englobant = window;
// eval("var x = 42") correspond à l'exécution de :
scope.set('x', 42);
var tmp = function xPlus1() {
// les vars sont remontées, donc la portée initialement contient 'z'.
var portée = new Map([['z', undefined]]);
portée.englobant = xPlus1.englobant;
// var z = x + 1
portée.set('z', recherche(portée, 'x') + 1);
// retourne z
return recherche(portée, 'z');
}
tmp.englobant = portée;
return tmp;
}
function recherche(portée, nom) {
while (portée instanceof Map && !portée.has(nom))
portée = portée.englobant;
return portée.get(nom);
}
Notez que sans être en mesure d’utiliser des accès de variables non locales (vu que c’est ce que l’on implémente), nous devons attacher la portée de la fonction bizarre à l’objet de la fonction xPlus1. Ce n’est pas une simple astuce ; c’est une part fondamentale de l’implémentation des langages ayant une portée lexicale ainsi que des fonctions du premier ordre. De manière générale, nous pouvons établir la relation suivante (désolé pour l’ASCII-art) :
Portée de fonction | * ^ 0 or 1 | | englobant | appel | | | V 1 | 1 Objet de fonction | * | | évaluation de | V 1 Fonction anonyme (lambda)
Chaque fonction anonyme peut être évaluée plusieurs fois, chaque évaluation produisant un objet de fonction auquel est associé sa portée de fonction. Chacun de ces objets de fonction peut être appelé de multiples fois, et chacun de ces appels produit une portée. En utilisant le langage, il est facile d’entrevoir un concept de function (lambda), mais heureusement cet exemple illustre qu’il y a en fait 3 concepts de « function » en jeu ici : la portée, l’objet, et lambda.
Avec ces changements, nous avons réussi à gérer les ravages de eval, mais à quel prix ? Chaque accès de variable implique un appel à un algorithme qui recherche dans des tables de hachage! Heureusement, ce problème n’est pas si différent d’un accès de propriété des objets et les mêmes solutions peuvent être utilisées : des structures cachées et des caches. Je ne vais pas rentrer dans le détail de ces techniques, étant donné qu’il y a déjà plein de bonnes explications disponibles (des caches furent utilisés pour améliorer les accès de nom depuis Firefox 3). Même avec ces optimisations, la recherche des noms de variable n’est pas aussi rapide qu’on l’aurait souhaité, et nous avons toujours besoin de créer un objet Map à chaque appel.
En résumé, nous avons géré le pire des cas, mais nous aimerions faire mieux sur du code dans un cas plus simple.
Accès rapide de variable locale
Maintenant, voyons comment améliorer les accès de variables locales quand tous les accès sont locaux. Avec cette contrainte, JavaScript commence à ressembler à du C et nous pouvons utiliser les mêmes techniques qu’un compilateur C : stocker toutes les variables dans une pile et accéder à chaque variable par son emplacement dans la pile.
Dans une première itération (très brouillon), nous allons créer un tableau pour chaque groupe d’arguments et de variables, transformant ainsi :
foo(13, 42);
function foo(x,y) {
var a = x + y;
return bar(a);
}
en :
foo([13, 42]);
function foo(args) {
var vars = [undefined];
vars[0] = args[0] + args[1];
return bar([vars[0]]);
}
La deuxième étape consiste à éviter de créer tous ces tableaux temporaires en utilisant un grand tableau, partagé entre toutes les fonctions actives. Il y a plusieurs façons de le faire (correspondant à différentes conventions d’appels) ; nous allons juste voir un cas simple ici :
// exécuté avant le première appel de fonction :
var pile = [];
pile.push(13); // pousse 'x'
pile.push(42); // pousse 'y'
foo(/* nombre d'arguments poussés = */ 2);
function foo(numArgs) {
// Ajoute les arguments manquants
for (var i = numArgs; i < 2; i++)
pile.push(undefined);
// Retire les arguments en trop
for (var i = numArgs; i > 2; i--)
pile.pop();
// analogue au registre du pointeur sur cadre (en anglais frame pointer)
var cadre = pile.length;
// pousse la variable locale 'a'
pile.push(undefined);
// var a = x + y:
pile[cadre + 0] = pile[cadre - 2] + pile[cadre - 1];
// prépare la pile pour appeler 'bar(a)' :
pile.push(pile[cadre + 0]); // pousse 'a'
return bar(/* nombre d'arguments poussés = */ 1);
// dans cette convention d'appels, l'appelé dépile ses arguments.
pile.pop(); // dépile 'a'
pile.pop(); // dépile 'y'
pile.pop(); // dépile 'x'
}
Avec cette stratégie, un compilateur à la volée peut faire de bien meilleures optimisations. À commencer par le fait que chaque lecture ou écriture depuis ou vers la pile dans le code JavaScript précédent peut être compilée vers une unique lecture ou écriture du CPU. Cela est possible en cachant l’adresse de pile[cadre] dans un registre et en ajoutant le « + INDEX » dans l’instruction de lecture. Encore mieux, les compilateurs modernes de JavaScript peuvent utiliser un algorithme d’allocation de registre qui évite les lectures et les écritures. (Firefox intègre un allocateur de registre depuis la version 3.5.)
En bref, nous pouvons concevoir des accès de variables relativement efficaces, mais seulement dans un cadre bien limité.
Accès rapide aux variables non locales
Alors que nous ne devrions pas attendre beaucoup d’efficacité des fonctions utilisant eval et arguments, es demandes de la section précédente sont extrêmement exigeantes et rentrent en conflit à la fois avec l’écriture fonctionnelle (langage) et l’isolation par modules qui sont des classiques du développement en JavaScript. Dans cette section, on va donc s’intéresser à l’accès aux variables non locales.
Nous commençons par observer qu’en l’absence de eval et autres étrangetés, il n’y a nul besoin de recherche dynamique dans les portées : nous savons exactement où chercher pour accéder à la variable dans la liste des portées. La première étape consiste à considérer chaque fonction définie globalement comme un arbre de fonctions imbriquées, donnant à chaque nœud (fonction) de l’arbre un vecteur de variables définies dans sa portée.
function add3(arg1, arg2, arg3) {
function addInner(innerArg1) {
function innermost() { return innerArg1 + arg2 + getArg3() };
return innermost();
}
function getArg3() {
return arg3;
}
return addInner(arg1);
}
we can distill the following tree:
nous pouvons le simplifier avec l’arbre suivant:
function add3: [arg1, arg2, arg3, addInner, getArg3] |\_ function addInner: [innerArg1, innermost] | \_ function innermost: [] \_ function getArg3: []
L’étape suivante consiste en l’inclusion des utilisations, telles les feuilles d’un arbre, liées à la définition ayant le même nom la plus profondément imbriquée. Plutôt que de dessiner des flèche en ASCII-art, nous allons représenter un lien entre l’utilisation et la définition avec 2 coordonnées :
- sauts = le nombre de nœuds dans l’arbre à passer pour obtenir le nœud de la fonction qui contient la définition.
- index = l’index de la définition dans le tableau de définition de la fonction.
Lier les utilisations aux définitions dans l’arbre précédent donne :
function add3: [arg1, arg2, arg3, addInner, getArg3]
|\_ function addInner: [innerArg1, innermost]
| |\_ function innermost: []
| | |\_ "innerArg1" {hops=1, index=0}
| | |\_ "arg2" {hops=2, index=1}
| | \_ "getArg3" {hops=2, index=4}
| \_ "innermost": {hops=0, index=1}
|\_ function getArg3: []
| \_ "arg3" {hops=1, index=2}
|\_ "addInner" {hops=0, index=3}
|\_ "getArg3" {hops=0, index=4}
\_ "arg1" {hops=0, index=0}
function add3: [arg1, arg2, arg3, addInner, getArg3]
|\_ function addInner: [innerArg1, innermost]
| |\_ function innermost: []
| | |\_ "innerArg1" {sauts=1, index=0}
| | |\_ "arg2" {sauts=2, index=1}
| | \_ "getArg3" {sauts=2, index=4}
| \_ "innermost": {sauts=0, index=1}
|\_ function getArg3: []
| \_ "arg3" {sauts=1, index=2}
|\_ "addInner" {sauts=0, index=3}
|\_ "getArg3" {sauts=0, index=4}
\_ "arg1" {sauts=0, index=0}
Et pour la dernière étape, on supprime toutes les variables utilisées uniquement de manière locale. Nous pouvons supprimer des portées entières si elles sont vides ; nous avons juste besoin d’être attentifs à ne pas les compter parmi les sauts. Faire cette transformation produit l’arbre final suivant :
function add3: [arg2, arg3, getArg3]
|\_ function addInner: [innerArg1]
| \_ function innermost:
| |\_ "innerArg1" {hops=0, index=0}
| |\_ "arg2" {hops=1, index=0}
| \_ "getArg3" {hops=1, index=2}
|\_ function getArg3:
| \_ "arg3" {hops=0, index=1}
\_ "getArg3" {hops=0, index=2}
function add3: [arg2, arg3, getArg3]
|\_ function addInner: [innerArg1]
| \_ function innermost:
| |\_ "innerArg1" {sauts=0, index=0}
| |\_ "arg2" {sauts=1, index=0}
| \_ "getArg3" {sauts=1, index=2}
|\_ function getArg3:
| \_ "arg3" {sauts=0, index=1}
\_ "getArg3" {sauts=0, index=2}
Avec cette analyse, nous avons toutes les informations nécessaires pour compiler un programme efficacement. Pour les variables uniquement locales que nous avons supprimées lors de la dernière étape, nous pouvons utiliser directement la pile (comme vu dans la deuxième section). Pour les variables avec un accès non local, nous pouvons représenter une liste chaînée de portée (comme vu dans la première section), sauf que maintenant, nous représentons les portées comme des vecteurs au lieux de tableaux associatifs. Pour compiler un accès à une variable, nous utilisons les coordonnées {sauts, index} : les sauts nous donnent le nombre de portées englobantes à suivre, et l’index nous donne l’emplacement dans le vecteur de la portée.
Appliquer ce schéma sur l’exemple original (en omettant le mot clé arguments (manquant/en trop) qui dérange) produit le code JavaScript suivant (avec les accès aux portées mis en rouge)
function add3() {
var cadre = arguments.length;
// la portée optimisée de add3 est: [arg2, arg3, getArg3]
var portée = [pile[cadre-2], pile[cadre-1], undefined];
portée.englobant = window;
// initialise 'addInner':
pile.push(function addInner() {
var cadre = arguments.length;
// la portée optimisée de addInner est: [innerArg1]
var portée = [pile[cadre - 1]];
portée.englobant = addInner.englobant;
// pousse la locale 'innermost'
pile.push(function innermost() {
// la portée de innermost n'existe plus après optimisation.
var portée = innermost.englobant;
// retourne innerArg1 {hops=0, index=0} +
// arg2 {hops=1, index=0} +
// getArg3() {hops=1, index=2}
return portée[0] +
portée.englobant[0] +
(portée.englobant[2])();
});
pile[cadre].englobant = scope;
// retourne innermost()
var returnValue = (pile[cadre])();
pile.pop(); // dépile 'innermost'
pile.pop(); // dépile 'innerArg1'
return returnValue;
});
pile[cadre].englobant = portée;
// initialise 'getArg3' {hops=0, index=2}:
scope[2] = function getArg3() {
// la portée de getArg3 n'existe plus après optimisation.
var portée = getArg3.englobant;
// retourne arg3 {hops=0, index=1}
return portée[1];
}
portée[2].englobant = portée;
// retourne addInner(arg1)
pile.push(stack[cadre - 3]);
var returnValue = (pile[cadre])();
pile.pop(); // dépile 'addInner'
pile.pop(); // dépile 'arg3'
pile.pop(); // dépile 'arg2'
pile.pop(); // dépile 'arg1'
return returnValue;
}
Les experts en performances JavaScript vont prétendre qu’ajouter une propriété nommée sur un tableau va causer une désoptimisation sur certains moteurs JavaScript (y compris SpiderMonkey, avant que le bug 586842 ne le corrige). Partons du principe que ce n’est pas le cas ; dans le cas contraire, nous pouvons simplement réserver portée0 pour le lien vers la portée englobante.
Cette stratégie est bien pour la compilation à la volée de plusieurs points de vue :
- Si une variable est seulement accédée localement, elle peut toujours vivre sur la pile et recevoir toutes les optimisations.
- Chaque expression .englobant est compilée en une simple instruction de chargement depuis la mémoire. De plus, quand plusieurs accès partagent la même portée, le compilateur peut les factoriser dans la même traversée de portée englobante.
- Vu qu’un accès de variable non local est plus simple avec cette représentation qu’avec un tableau associatif, IonMonkey est capable d’optimiser les accès avec des algorithmes tels que LICM, GVN et DCE (voir article sur IonMonkey)
En résumé, nous avons optimisé les accès non locaux tout en conservant un accès rapide aux variables locales. Il existe d’autres optimisations liées aux portées qui permettent de réduire la chute brutale de performances pour les utilisation de eval et de arguments, mais je pense qu’il est bon de s’arrêter là.
Prochaines étapes
Le récent projet d’optimisation des portées nous permet de nous mettre au niveau des autres machines virtuelles JavaScript. Je devrais aussi noter que les langages fonctionnels font cela depuis des lustres. Je me réjouis à l’idée qu’il reste des optimisations simples auxquelles je pense, en partie pour éviter de construire un objet de portée, ainsi que d’autres un peu plus avancées que nous pouvons tirer des langages fonctionnels. Ayant des idées d’optimisations simples, je me réjouis d’avance qu’elles se concrétisent bientôt ; elles permettraient entre autres d’éviter de construire un objet de portée, tandis que des améliorations plus avancées pourraient être tirées des langages fonctionnels.
Dans SpiderMonkey
Si cela vous intéresse de voir le code de tout ça dans SpiderMonkey, vous pouvez commencer par suivre l’un des liens suivants :
- Les coordonnées {sauts, index} sont appelées ScopeCoordinate.
- Les divers objets de portées sont décrits par cet arbre en ASCII-art. (Attention, pour des raisons purement historiques, nous utilisons la même représentation pour les objets et les portées. Suite au mécanisme des portées, qui est généré pour les portées à la compilation, les portées sont bel et bien implémentées avec des vecteurs.)
- L’optimisation des accès non locaux est effectuée avec l’instruction (byte-code) ALIASEDVAR. Référez-vous à ses implémentations dans l’interpréteur et dans IonMonkey.
- La partie d’analyse préliminaire est un peu fouillis (et devrait être réécrite dans un futur proche). Cependant, la partie importante de cette analyse se trouve vers la fin, là où sont émises les instructions ALIASEDVAR (dans la fonction EmitAliasedVarOp).
