Mise en cache en ligne - Inline caching
La mise en cache en ligne est une technique d'optimisation utilisée par certains environnements d'exécution de langage et développée pour la première fois pour Smalltalk . L'objectif de la mise en cache en ligne est d'accélérer la liaison de méthode d'exécution en mémorisant les résultats d'une recherche de méthode précédente directement sur le site d'appel . La mise en cache en ligne est particulièrement utile pour les langages à typage dynamique où la plupart sinon la totalité des liaisons de méthodes se produisent au moment de l'exécution et où les tables de méthodes virtuelles ne peuvent souvent pas être utilisées.
Liaison de méthode d'exécution
La fonction ECMAScript suivante reçoit un objet, appelle sa méthode toString et affiche les résultats sur la page dans laquelle le script est intégré.
function dump(obj) {
document.write(obj.toString());
}
Puisque le type de l'objet n'est pas spécifié et à cause d'une surcharge potentielle de la méthode , il est impossible de décider à l'avance quelle implémentation concrète de la méthode toString va être appelée. Au lieu de cela, une recherche dynamique doit être effectuée au moment de l'exécution. Dans les environnements d'exécution de langage qui n'emploient aucune forme de mise en cache, cette recherche est effectuée chaque fois qu'une méthode est appelée. Étant donné que les méthodes peuvent être définies plusieurs étapes dans la chaîne d'héritage , une recherche dynamique peut être une opération coûteuse.
Pour obtenir de meilleures performances, de nombreux environnements d'exécution de langage utilisent une forme de mise en cache non en ligne dans laquelle les résultats d'un nombre limité de recherches de méthodes sont stockés dans une structure de données associative. Cela peut considérablement augmenter les performances, à condition que les programmes exécutés soient "compatibles avec le cache" (c'est-à-dire qu'il existe un ensemble limité de méthodes qui sont fréquemment appelées). Cette structure de données est généralement appelée cache de recherche de méthode de premier niveau .
Mise en cache en ligne
Le concept de mise en cache en ligne est basé sur l'observation empirique que les objets qui se produisent sur un site d'appel particulier sont souvent du même type. Dans ces cas, les performances peuvent être grandement améliorées en stockant le résultat d'une recherche de méthode "en ligne", c'est-à-dire directement sur le site d'appel. Pour faciliter ce processus, les sites d'appel se voient attribuer différents états. Au départ, un site d'appel est considéré comme "non initialisé". Une fois que le moteur d'exécution du langage atteint un site d'appel non initialisé particulier, il effectue la recherche dynamique, stocke le résultat sur le site d'appel et change son état en "monomorphe". Si le moteur d'exécution du langage atteint à nouveau le même site d'appel, il récupère l'appelé à partir de celui-ci et l'appelle directement sans effectuer d'autres recherches. Pour tenir compte de la possibilité que des objets de types différents puissent apparaître sur le même site d'appel, le moteur d'exécution du langage doit également insérer des conditions de garde dans le code. Le plus souvent, ils sont insérés dans le préambule de l'appelé plutôt que sur le site d'appel pour mieux exploiter la prédiction de branche et pour économiser de l'espace grâce à une copie dans le préambule par rapport à plusieurs copies sur chaque site d'appel. Si un site d'appel qui est à l'état "monomorphe" rencontre un type autre que celui qu'il attend, il doit revenir à l'état "non initialisé" et effectuer à nouveau une recherche dynamique complète.
L'implémentation canonique est une charge de registre d'une constante suivie d'une instruction d'appel. L'état "non initialisé" est mieux appelé "non lié". Le registre est chargé avec le sélecteur de message (généralement l'adresse d'un objet) et l'appel est à la routine d'exécution qui recherchera le message dans la classe du récepteur actuel, en utilisant le cache de recherche de méthode de premier niveau ci-dessus . La routine d'exécution réécrit ensuite les instructions, en modifiant l'instruction de chargement pour charger le registre avec le type du récepteur actuel, et l'instruction d'appel pour appeler le préambule de la méthode cible, maintenant "reliant" le site d'appel à la méthode cible . L'exécution se poursuit alors immédiatement après le préambule. Une exécution ultérieure appellera directement le préambule. Le préambule dérive alors le type du récepteur actuel et le compare à celui du registre; s'ils sont d'accord, le récepteur est du même type et la méthode continue de s'exécuter. Sinon, le préambule appelle à nouveau le run-time et diverses stratégies sont possibles, l'une étant de relier le site d'appel pour le nouveau type de récepteur.
Les gains de performances proviennent du fait d'avoir à faire une comparaison de type, au lieu d'au moins une comparaison de type et une comparaison de sélecteur pour le cache de recherche de méthode de premier niveau, et de l'utilisation d'un appel direct (qui bénéficiera de la prélecture d'instructions et du pipe-line) par opposition à l'appel indirect dans une recherche de méthode ou une distribution vtable .
Mise en cache en ligne monomorphique
Si un site d'appel particulier voit fréquemment différents types d'objets, les avantages en termes de performances de la mise en cache en ligne peuvent facilement être annulés par la surcharge induite par les fréquents changements d'état du site d'appel. L'exemple suivant constitue le pire des cas pour la mise en cache en ligne monomorphe:
var values = [1, "a", 2, "b", 3, "c", 4, "d"];
for (var i in values) {
document.write(values[i].toString());
}
Là encore, la méthode toString est appelée sur un objet dont le type n'est pas connu à l'avance. Plus important encore, le type de l'objet change à chaque itération de la boucle environnante. Une mise en œuvre naïve de la mise en cache en ligne monomorphe ferait donc constamment défiler les états «non initialisé» et «monomorphe». Afin d'éviter que cela ne se produise, la plupart des implémentations de la mise en cache en ligne monomorphe prennent en charge un troisième état souvent appelé état «mégamorphique». Cet état est entré lorsqu'un site d'appel particulier a vu un nombre prédéterminé de types différents. Une fois qu'un site d'appel est entré dans l'état "mégamorphique", il se comportera exactement comme il l'a fait dans l'état "non initialisé" à l'exception qu'il n'entrera plus jamais dans l'état "monomorphe" (certaines implémentations de la mise en cache en ligne monomorphe changeront " mégamorphiques "rappellent les sites" non initialisés "après un certain laps de temps ou une fois qu'un cycle complet de ramasse-miettes est effectué).
Mise en cache en ligne polymorphe
Pour mieux gérer les sites d'appels qui voient fréquemment un nombre limité de types différents, certains environnements d'exécution de langage utilisent une technique appelée mise en cache polymorphe en ligne. Avec la mise en cache en ligne polymorphe, une fois qu'un site d'appel qui est dans son état "monomorphe" voit son deuxième type, plutôt que de revenir à l'état "non initialisé", il passe à un nouvel état appelé "polymorphe". Un site d'appel "polymorphe" décide laquelle d'un ensemble limité de méthodes connues à invoquer en fonction du type qui lui est actuellement présenté. En d'autres termes, avec la mise en cache polymorphe en ligne, plusieurs résultats de recherche de méthode peuvent être enregistrés sur le même site d'appel. Étant donné que chaque site d'appel dans un programme peut potentiellement voir tous les types du système, il existe généralement une limite supérieure au nombre de résultats de recherche enregistrés sur chaque site d'appel. Une fois cette limite supérieure atteinte, les sites d'appels deviennent «mégamorphiques» et aucune mise en cache en ligne n'est plus effectuée.
L'implémentation canonique est une table de sauts qui se compose d'un préambule qui dérive le type de récepteur et d'une série de comparaisons constantes et de sauts conditionnels qui sautent au code suivant le préambule de la méthode appropriée pour chaque type de récepteur. La table de saut est généralement allouée pour un site d'appel particulier lorsqu'un site d'appel monomorphe rencontre un type différent. La table de saut aura une taille fixe et pourra croître, en ajoutant des cas au fur et à mesure que de nouveaux types sont rencontrés jusqu'à un petit nombre maximum de cas tels que 4, 6 ou 8. Une fois qu'il atteint sa taille maximale, exécution pour un nouveau type de récepteur "tombera" la fin et entrera dans le temps d'exécution, généralement pour effectuer une recherche de méthode en commençant par le cache de méthode de premier niveau.
L'observation qu'ensemble, les caches en ligne monomorphes et polymorphes collectent des informations de type de récepteur par site d'appel comme effet secondaire de l'optimisation de l'exécution du programme a conduit au développement de l' optimisation adaptative dans Self , où l'exécution optimise les «points chauds» dans le programme utilisant les informations de type dans les caches en ligne pour guider les décisions d'inlining spéculatives.
Mise en cache en ligne mégamorphique
Si un environnement d'exécution utilise à la fois la mise en cache en ligne monomorphe et polymorphe, à l'état stable, les seuls envois non liés se produiront seront ceux des envois tombant aux extrémités des caches en ligne polymorphes. Étant donné que ces envois sont lents, il peut maintenant être rentable d'optimiser ces sites. Un cache en ligne mégamorphique peut être implémenté en créant du code pour effectuer une recherche de méthode de premier niveau pour un site d'appel particulier. Dans ce schéma, une fois qu'un envoi tombe à la fin d'un cache en ligne polymorphe, un cache mégamorphique spécifique au sélecteur du site d'appel est créé (ou partagé s'il en existe déjà un), et le site d'envoi est de nouveau lié pour l'appeler. Le code peut être beaucoup plus efficace qu'une sonde de recherche de méthode de premier niveau normale puisque le sélecteur est maintenant une constante, ce qui diminue la pression du registre, le code pour la recherche et la distribution est exécuté sans appeler dans le temps d'exécution, et la distribution peut bénéficier de la prédiction de branche .
Des mesures empiriques montrent que dans les grands programmes Smalltalk, environ 1/3 de tous les sites d'envoi des méthodes actives restent non liés, et sur les 2/3 restants, 90% sont monomorphes, 9% polymorphes et 1% (0,9%) sont mégamorphiques.