V8 iii, polymorphic inline cache PICs

Key points: MONOMORPHIC calls outperform POLYMORPHIC and MEGAMORPHIC calls!

This chapter is not part of the main thread (objects), but it is helpful to understand the V8 mechanics (and object access patterns) and is recommended.

If you’re not interested in this, you can skip the next chapter: Trickery V8 iv and migrate objects to Fast Mode

Let’s start with getX, a method that reads the value of an object property:

function getX(point) {
    return point.x;
}
Copy the code

We can roughly think of the above code in V8 as equivalent to the following code:

function getX(point) {
    return Runtime_Load(point, "x");
}
Copy the code

Assuming that the value passed in is always a normal object (unproxy, undefined, etc.), V8 Runtime_Load is expressed in pseudocode, which can be abbreviated to something like the following:

1. Get instance_descriptors from the object’s
   
2. Instance_descriptors iterates to get the location of the key store (within the object or in properties).
3. Calls specific methods to read property values.

Use (JavaScript) pseudocode to express:

function Runtime_Load(obj, key) { var desc = obj.map().instance_descriptors(); var desc_number = -1; for (var i = 0; i < desc.length; i++) { if (desc.GetKey(i) === key) { desc_number = i; break; } } if (desc_number === -1) { return undefined; } var detail = desc.GetDetails(desc_number); if (detail.is_inobject()) { return obj.READ_FIELD(detail.offset()); } else { return obj.properties().get(detail.outobject_array_index()); }}Copy the code

There’s nothing wrong with doing it once, but if it’s done 100 times, 1,000 times, 10,000 times…

for (var i = 0; i < 10000; i++) {
    getX({x : i});
}
Copy the code

We find that in most cases the object structure JSObject<Map> (Hidden Class) passed in by calling getX is the same, and the property #x is accessed in the same location.

Based on this discovery, we store the location of the property #x and its corresponding JSObject<Map> (reference), so that the location of the property #x can be obtained the next time without a Runtime_Call, saving a lot of lookups.

In other words, this can be abbreviated to something like the following:

1. Determines whether the
   
2. Again, read directly from the cache location.
3. If not, call Runtime_Load.

Use (JavaScript) pseudocode to express:

function getX(point) {
    return LoadIC_x(point);
}
Copy the code

The LoadIC_x:

function LoadIC_x(obj) { if (obj.map() === cache.map) { if (cache.offset >= 0) { return obj.READ_FIELD(cache.offset); } else { return obj.properties().get(cache.index); } } else { return Runtime_LoadIC_Miss(obj, "x"); }}Copy the code

Also change the implementation of Runtime_Load (which not only gets the attribute value, but also caches the location where it finds the attribute value) to Runtime_LoadIC_Miss:

Function Runtime_LoadIC_Miss(obj, key) {//... ... cache = {map : obj.map()}; if (detail.is_inobject()) { cache.offset = detail.offset(); / /... ... } else { cache.index = detail.outobject_array_index(); / /... ... }}Copy the code

Is that enough for all the scenarios that need to be optimized?

Let’s look at an example:

for (var i = 0; i < 10000; i++) { if (i % 2) { getX({x : 1}); } else { getX({x : 1, y : 2}); }}Copy the code

In this example, the cache hit ratio is 0 because the <Map> of the object is constantly changing.

We modify Runtime_LoadIC_Miss to change the cache from a single store to a hash table mode, and cache all <Map> that it encounters and where its attribute values are stored.

Function Runtime_LoadIC_Miss(obj, key) {//... ... var cache = {map : obj.map()}; if (detail.is_inobject()) { cache.offset = detail.offset(); caches.push(cache); / /... ... } else { cache.index = detail.outobject_array_index(); caches.push(cache); / /... ... }}Copy the code

Change the LoadIC_x implementation:

function LoadIC_x(obj) {
    for (var i = 0; i < caches.length; i++ ) {
        if (obj.map() === caches[i].map) {
            if (caches[i].offset >= 0) {
                return obj.READ_FIELD(caches[i].offset);
            } else {
                return obj.properties().get(caches[i].index);
            }
        }
    }
    return Runtime_LoadIC_Miss(obj, "x");
}
Copy the code

This will always hit the cache no matter how the object structure (<Map>) changes, so the hit ratio of the cache increases, but at the same time (LoadIC_x) the increase in the number of branches will lead to an increase in the time (compared to a single cache).

Little knowledge:


X is called a callsite, “x” is called a message named “X”, and the actual point (whether {x: 1} or {x: 1, y: 2}) is called the callsite receiver.

To summarize, the execution of many operations in JavaScript is extremely complex, but the variation of receiver type (

V8 optimizes different types of code execution with different types of inline caching (ICS), including the following types:

• AnyLoad
• LoadIC
• KeyedLoadIC
• LoadGlobalIC
• AnyStore
• StoreIC
• KeyedStoreIC
• StoreGlobalIC
• CallIC
• BinaryOpIC
• CompareIC
• ToBooleanIC

Obj [expression] creates Keyed correlation ics

obj.x                // LoadIC(x)
obj["x"];            // LoadIC(x)

obj.x = 1;           // StoreIC(x)
obj["x"] = 1;        // StoreIC(x)

var key = "_";
obj[key + "x"];      // KeyedLoadIC(x)
obj[key + "x"] = 1;  // KeyedStoreIC(x)
Copy the code

The IC presents different states according to the type of information received (receiver type) :

• When the IC is first created, it is in its initial state (not called) and receives no type information.
• When called:
• If one type of information is received, it will migrate to MONOMORPHIC mode.
• The packets that receive more than 1 and less than 4 types will be migrated into POLYMORPHIC mode.
• It migrates to MEGAMORPHIC mode when it receives more than four types of information.

As V8 defines kMaxPolymorphicMapCount = 4 and kMaxKeyedPolymorphism = 4, the boundary between polymorphic and polymorphic pattern patterns is defined when the four types of information are received.

As can be seen from the two examples at the beginning of the article, MONOMORPHIC calls outperform POLYMORPHIC and MEGAMORPHIC!

Finally, polymorphic inline caching (PICs) was not invented by V8, Optimizing Dynamically Typed Object-oriented Languages With Polymorphic Inline Caches [PDF].

This is also an important part of PGO (FDO) optimization (gathering type information for optimizing the compiler TurboFan), as outlined in profile-Guided Optimization theory.

Why is an object optimized for fast mode by setting it as a function prototype? And the relationship to inline caching? Welcome to the next chapter (main line) :

• Acrobacy V8 iv, move objects to Fast mode