Comment les caches polymorphes en ligne fonctionnent-ils avec des types mutables?

Question

Un cache en ligne polymorphe (PIC) fonctionne en mettant en cache la méthode actuelle par le type de l'objet, afin d'éviter les procédures de recherche coûteuses (généralement une recherche hashtable).

Comment peut-on gérer la comparaison de type si les objets de type sont mutables (c'est-à-dire que la méthode peut être modifiée de singe dans quelque chose de différent au moment de l'exécution)? La seule idée que j'ai trouvée est un "compteur de classes" qui s'incrémente à chaque fois qu'une méthode est ajustée, mais cela semble être exceptionnellement cher dans un environnement fortement corrigé, car cela tue tous les PIC pour cette classe, même si les méthodes pour eux n'ont pas été modifiées.

Je suis sûr qu'il doit y avoir une bonne solution à ce problème, car ce problème est directement applicable à JavaScript, et AFAIK les trois grandes machines virtuelles JavaScript ont des PIC.

Answer 1

En V8, je supposerais que le monkeypatching changerait la "classe cachée" ("map" est la terminologie SELF) de l'objet. Cela fonctionnerait dans votre singe patché l'objet lui-même.

Si votre singe a patché la classe (pouvez-vous faire cela est JS?), Je suppose que cela invalide tous les PIC, car c'est probablement rare. Alternativement, il pourrait recompiler l'ancienne méthode pour envoyer directement à la nouvelle méthode (après une vérification de type je suppose)

En passant, je ne pense pas que les autres "big 3" utilisent des PIC, en fait. Je présume que vous voulez dire squirrelfish et tracemonkey. Le premier est un interprète, et le second se concentre sur l'approche du traçage, et je ne me souviens pas d'avoir entendu parler des PIC. En fait, je ne pense pas que tracemonkey fasse quoi que ce soit de cool pour les objets, mais je peux me tromper.

Answer 2

inférence de type est utilisé:

SpiderMonkey utilise principalement l'inférence de type pour déterminer les propriétés sont accessibles; Dans les cas où l'inférence de type ne trouve pas la forme exacte de l'objet accédé, SpiderMonkey utilise un PIC (caches polymorphes en ligne) pour stocker le résultat de la recherche.

Une autre forme de rétroaction de profilage sont les caches polymorphes en ligne de Baseline JIT. Les caches en ligne polymorphes sont une technique classique pour optimiser la répartition dynamique qui provient de la communauté Smalltalk.

De-optimisation est le nom du processus qui se produit lorsque l'inférence de type échoue:

Bien sûr, JavaScript étant un langage typé dynamiquement, ocassionally l'hypothèse de la classe cachée de l'objet sera incorrect, et dans ce cas, V8 "dés-optimisera" et retournera à la version originale de l'appel de méthode dans lequel la classe cachée des objets est vérifiée.

compilateurs multiples sont nécessaires pour que cela fonctionne:

Techniquement, cela signifie que le compilateur est en fait deux compilateurs: un compilateur de base et un « optimiseur ». (Ou même plus, si nous parlons de JSC et SpiderMonkey). Le concept est assez solide et peut donner des performances incroyables, mais il y a une nuance: le code optimisé peut être "désoptimisé" à divers endroits, pas seulement au point d'entrée, ce qui signifie que l'environnement (variables locales, arguments, contexte) cartographié et déplacé.Ion, étant le compilateur d'optimisation, ne supporte pas la compilation dans les vérifications en mode débogage. En effet, la mise en œuvre d'un tel support est d'une utilité douteuse, car ses optimisations rendraient au mieux les invocations d'invocation. Pour prendre en charge le mode de débogage, les codes optimisés sur la pile sont désoptimisés et renvoyés à Baseline. C'est-à-dire que la trame Ion sur la pile est remplacée par une trame de base reconstruite correspondant au même emplacement dans lequel le code Ion est en cours d'exécution.

Debugging se fait via deoptimization dynamique:

Nous pouvons faire mieux. Le rêve des années 90, incarné dans le langage de soi, est vivant en JavaScript. Nous pouvons adapter la désoptimisation dynamique de Self via la technique de remplacement sur pile pour déboguer même du code optimisé. L'idée centrale d'un debug mode OSR est simple: lorsque le débogage est requis, nous désoptimisons et recompilons le code JITED sur la pile, en corrigeant les adresses de retour au fur et à mesure. On pourrait dire qu'il est presque élégant, sinon pour la violence exigeante qu'il inflige sur les cadres de la pile.

Tenir compte de la fonction JavaScript suivante:

function foo(o) { return o.f + o.g; } 

Dans cet exemple, la propriété des accès peut conduire à quoi que ce soit d'une simple charge à partir d'endroits bien connus dans le tas à des invocations de getters ou même les traps DOM compliqués, comme si o étaient un objet document et f étaient le nom d'un élément dans la page. Le JIT de base exécutera initialement ces accès de propriété en tant que répartition polymorphe complète. Mais comme il le fait, il enregistrera les étapes qu'il prend, et modifiera ensuite les accès de tas sur place pour être des caches des étapes nécessaires pour répéter un accès similaire dans le futur. Par exemple, si l'objet a une propriété f au décalage 16 de la base de l'objet, le code sera modifié pour vérifier d'abord rapidement si l'objet entrant est constitué d'une propriété f au décalage 16, puis effectuer le chargement. Ces caches sont dits en ligne car ils sont représentés entièrement en tant que code machine généré. Ils sont dits polymorphes car si différentes structures d'objets sont rencontrées, le code machine est modifié pour activer les types d'objets précédemment rencontrés avant de faire une recherche de propriété entièrement dynamique. Lorsque le DFG compile ce code, il vérifiera si le cache en ligne est monomorphe - optimisé pour une seule structure d'objet - et si c'est le cas, il émettra juste une vérification de cette structure d'objet suivie de la charge directe. Dans cet exemple, si o était toujours un objet avec les propriétés f et g aux décalages invariants, alors le DFG aurait seulement besoin d'émettre un contrôle de type pour o suivi de deux charges directes.

Références

• Deoptimize me not, v8

• Javascript Hidden Classes and Inline Caching in V8

• Debugging in the Time of JITs

• IonMonkey: Evil on your behalf | JavaScript

• Optimization killers · petkaantonov/bluebird Wiki

• Optimizing Dynamically-Typed Object-Oriented Languages with Polymorphic Inline Caches (pdf)

• Deoptimization for Dynamic Language JITs on Typed, Stack-based Virtual Machines (pdf)

• Javascript var vs let (de)optimization/slowdown issue in v8 and SpiderMonkey

• chakracore msjunit: Test deoptimization after inlined call.

• chakracore msjunit: Test inlining and deoptimization of functions accessing and modifying the arguments object in strict mode with mismatched arguments count

• Nested Refinement Types for JavaScript (pdf)

• Introducing the WebKit FTL JIT | WebKit