Arbre de traces

Un arbre de traces est une structure de données utilisé pour la compilation à la volée de code source. Les arbres de traces sont utilisés pour tracer (enregistrer dans une trace) le code exécuté sur les points chauds, et le compiler. Quand les point chauds du code sont à nouveau exécutés, le code compilé est exécuté à la place. Toutes les instructions exécutées sont tracées, même à travers les appels de fonctions et c'est le chemin d'exécution complet qui est compilé. Ce qui est bien différent de la compilation d'une seule fonction. Le compilateur peut glaner plus d'informations que l'optimiseur peut mettre à profit pour supprimer le coût superflu que représente les appels de méthodes. Chaque fois que le code compilé fait un appel à du code non encore compilé, l'interpréteur reprend la main pour continuer l'exécution.

Principe de fonctionnement détaillé

Il a été inventé par Andreas Gal à l'Université de Californie à Irvine^[1].

La technique classique de compilation à la volée consiste à compiler en code natif les méthodes exécutées le plus souvent: ce sont les "points chauds". Toutes les instructions des méthodes "chaudes" sont alors compilées. C'est le principe de fonctionnement de HotSpot, la machine virtuelle Java de Sun Microsystems.

L'utilisation des traces d'exécutions repose sur l'observation que la majorité du temps passé lors de l'exécution d'un programme se situe dans les boucles. Le principe consiste donc a optimiser l'exécution des boucles.

L'interpréteur exécute le code jusqu'à rencontrer une boucle. Chaque fois qu'il en rencontre une, il se rappelle d'elle et compte le nombre de fois ou cette boucle a été exécutée. Lorsque le nombre d'exécution de la boucle dépasse un certain seuil, l'interpréteur enregistre une trace d'exécution du code de la boucle, c'est-à-dire qu'il enregistre toutes les instructions exécutées par l'itération de la boucle, même à travers les appels de fonction. Lorsque l'interpréteur termine l'exécution de cette itération, la trace est complète. Elle est alors compilée en code natif, et sera utilisée lors de la prochaine itération de la boucle.

Même avec du code très générique (acceptant aussi bien des entiers, des flottants et des chaînes de caractères), la trace enregistrée est spécialisée pour le type des données et donc le code natif l'est aussi. Afin de pouvoir utiliser une trace existante, le type des données doit donc être le même. Si le type des données diffère, il s'agit d'une nouvelle trace.

De la même manière, un changement de résultat pour un test présent dans la trace signifie que la trace compilée n'est plus valable pour l'itération courante. L'exécution de cette trace est alors abandonnée et la solution de repli est enclenchée : le contrôle retourne à l'interpréteur qui reprend l'exécution là où elle s'est arrêtée. Si le nombre d'exécution de la nouvelle trace exécutée par l'interpréteur dépasse un certain seuil, alors la trace sera enregistrée puis compilée en code natif. Finalement elle sera ajoutée a l'arbre des traces compilées disponibles.

A noter que la récursion étant une forme de boucle, elle se prête également à la même technique d'optimisation.

Les avantages d'une trace compilée par rapport à l'interprétation du code sont:

• l'interpréteur est très générique, donc beaucoup de tests de types doivent être réalisés lors de l'exécution. Une trace compilée pour un type n'a pas besoin de ces tests a l'exécution, sauf si le type de données peut changer lors de l'exécution et provoquer l'abandon de l'exécution d'une trace (en JavaScript, le dépassement d'entier donne pour résultat un objet de type Number, il s'agit d'un changement de type). De plus, la spécialisation de type permet d'utiliser les instructions spécifiques des processeurs. Cela permet d'atteindre une vitesse d'exécution proche du langage C non optimisé à partir de code JavaScript^[2].
• les appels de méthodes présents dans le code ne sont pas enregistrés dans la trace car ils sont inutiles pour le code natif compilé.

La compilation à la volée n'est intéressante que lorsque le temps de compilation du code plus l'exécution du code natif est inférieur au temps d'interprétation pure du code. D'où:

• le déclenchement de l'enregistrement des traces lorsque le chemin est suffisamment chaud
• l'abandon de l'enregistrement d'une trace si elle devient trop longue^[3].

Notes et références

Voir aussi

• TraceMonkey, le moteur d'exécution JavaScript inclus dans Mozilla Firefox basé sur les arbres de trace.

• Portail de la programmation informatique