Prototype Chain Guards and Validity Cells

An own property access is self-contained. The receiver’s layout says where the value is, and if the layout is what the code expected, the load is correct. An inherited property access is not self-contained. The receiver’s layout says nothing about the property, because the property is not there; the answer depends on an object the receiver points to, and on that object’s prototype, and so on to the end of the chain.

The obvious guard is to check the whole chain. Read the receiver’s layout, follow the prototype link, read that layout, follow the next link, and compare each against what the code expects. That is a load per link and a compare per link, on every execution of the access. For a chain of three it is six memory operations where the own-property case needs two, and the chain can be longer.

The alternative is to check nothing per access and instead make the runtime responsible for noticing when the assumption breaks. That requires a shared cell whose value is compared once, at the point the optimized code is created, and whose invalidation is broadcast when anything that would break the assumption happens.

The assumption being cached

Consider obj.name where name is not an own property of obj but is a property of obj’s prototype at offset 16. Compiled code that loads from offset 16 of the prototype is correct as long as four things hold: obj’s layout still has no own name, the prototype is still the same object, the prototype’s layout still has name at offset 16, and nothing between them has changed.

The first and third are layout facts and can be checked by comparing layout pointers. The second is an identity fact and is checked by comparing the prototype pointer. The fourth is implied by the others if the chain is exactly one link.

Checking all of them per access costs three compares and three loads. The validity cell replaces them with one compare, and the price is that the runtime must be able to invalidate the cell when any of the underlying facts changes.

What a validity cell holds

A validity cell is a small object with a current value and a list of things that depend on it. The dependent is usually a compiled code object, sometimes a specific deoptimization point within it, and sometimes an inline cache entry in interpreted code.

struct validity_cell {
    uint32_t state;              /* bumped on every invalidation */
    struct dependent *deps;      /* compiled code that assumed this state */
};

static inline int cell_still_valid(struct validity_cell *c, uint32_t seen) {
    return c->state == seen;
}

The compiled code embeds the state value it observed at compile time and compares it against the cell’s current state. A mismatch jumps to the deoptimization path. Invalidation is a store of a new state value plus a walk of the dependency list to mark or discard the dependents.

Two details make this work in practice. The state is monotonically increasing rather than a boolean, so that a cell can be invalidated, re-validated by a later compilation, and invalidated again without the compiled code’s embedded value accidentally matching a stale state. And the dependency list is per cell, not global, so invalidating one assumption does not require scanning all compiled code.

The cost at invalidation is proportional to the number of dependents, and that number can be large for a prototype that many functions read through. The runtime handles this by marking the cell and letting the dependents discover the invalidation lazily where it can, or by patching the entry points of the dependent code so that the next call takes a slow path. Patching entry points avoids walking a long list at the moment of invalidation, at the cost of a check on entry.

Why the prototype’s layout cannot simply change

The clean design would be for the prototype’s layout to be replaced whenever a property is added, so that any compiled code holding the old layout pointer fails its guard naturally. That works for code that reads an own property of the prototype, because the guard is on the prototype’s layout and the layout is what changed.

It does not work for code that reads a property through the prototype, because such code may not be checking the prototype’s layout at all. If it relies on the cell, the layout pointer it holds is the receiver’s, which has not changed. Adding a property to the prototype has to invalidate the cell, and the cell’s invalidation is what makes the code deoptimize.

There is a second reason the layout-change approach is insufficient. Adding a property to a prototype can change the answer to an access in a way that is not a layout change on the receiver and not a layout change at a fixed offset. Consider a chain where obj has no name, its prototype has no name, and the prototype’s prototype has name at offset 8. A compiled access walks two links and loads offset 8 of the grandparent. Now an own name is added to the prototype, at offset 0. The access now resolves one link earlier, at a different offset, and the compiled code’s two-link walk is wrong even though the grandparent’s layout never changed.

The invalidation has to be triggered by the assignment, which means the assignment path must consult the cells that depend on the prototype’s property set. Implementations keep such a cell on the prototype’s layout: the cell stands for the prototype’s property set as the compiled code observed it, and adding any property invalidates it.

The cost of the assignment path

Every property store to a prototype now has to check whether the addition changes any cached lookup. The check is not a search over all names; it is a lookup of the name in the layout’s transition edges, and if the name is not present, a new layout is created and the cell on the old layout is invalidated.

In practice the cell belongs to the prototype rather than to each site, so one invalidation covers every compiled access that resolved through it, whether or not that access reads the property that was added. The invalidation is a store and a list walk, proportional to the number of compiled sites that resolved an access through that prototype. A per-name cell would be more precise and would need an index from name to the sites that mention it; the per-prototype cell trades that precision for a smaller structure. Programs that build prototypes incrementally in a hot loop pay the walk on every addition, which is why the usual advice is to define all prototype members at once and then stop touching the prototype.

Assignment to an existing property on a prototype is a different case. If the property already exists, the layout does not change, and no cell is invalidated. The value at the offset changes, but compiled code reads the value at access time, so the new value is observed. This is why mutating a prototype’s field is cheap while adding a field is expensive, and why the distinction between the two is worth understanding when reading profiler output that shows deoptimizations clustered at one function.

Accessors on the chain make it worse

If the inherited property is an accessor, the compiled access cannot be a load at all. It has to call the getter with the receiver as this. The call target is the function stored in the accessor slot, and that function may be replaced at any time, which is another fact that needs a cell.

Engines usually compile such an access as a call to the getter with a guard on the getter’s identity, or do not inline it at all and go through a generic path. Inlining a getter is valuable when the getter is a simple field read, which is a common pattern for classes that expose a field through a getter, and the inlining requires a cell that is invalidated if the getter is replaced.

The replacement case is the reason the accessor’s slot is not simply read on each access. A getter that is called millions of times can be inlined once, with the assumption that it will not be replaced; the assumption is registered on a cell, and replacing it deoptimizes the callers.

Interaction with the receiver’s own layout

The cell-based scheme does not replace the receiver guard. The receiver’s layout still has to be checked, because a different receiver with the same prototype may have own properties that shadow the inherited one, or may be an object of a completely different type.

So a compiled inherited access has two checks: the receiver’s layout against the expected value, and the cell’s state against the expected value. Two compares, one load of the prototype pointer, and one load of the field. That is more than the own-property case’s one compare, but it is constant in the length of the chain, which is the property that matters. A chain of ten links costs the same as a chain of two, because the runtime resolved the walk at compile time and the cell covers the whole path.

The resolution at compile time is what makes this possible. The compiler, given a receiver layout, walks the prototype chain in the same way the interpreter would, finds the property, and records the offset and the objects traversed. Those objects are then registered as dependencies of the compiled code, either through one cell per object or through a combined cell. A change to any of them invalidates.

Where this shows up as a correctness requirement

The mechanism is a performance optimization, but its absence is a correctness bug, and that is the useful way to think about it. Without the cell, compiled code that reads an inherited property is correct only if the prototype chain never changes after compilation. Languages that allow prototype mutation, which is most of the dynamic object-oriented ones, guarantee that it can change at any time, so the cell is the only thing standing between the optimization and wrong answers.

The same requirement appears in the array representation, where the length and the element kind have to be invalidated when a write changes them, as described in Array Element Kinds and Representation Transitions. And it appears in shape identity, where two layouts that are structurally equal but arrived at by different histories must not be conflated, which is the subject of Shape Identity, Interning, and Structural Equality.