Hidden Classes and Inline Caches in Dynamic Object Models

An object whose set of properties is decided at run time cannot have a fixed layout known to the compiler. The obvious implementation is a hash table per object, and it works: o.x hashes the string "x", probes, and returns the slot. It also makes every property access a hash computation, a probe sequence, and a dependent load, which is far more expensive than the single load a compiled language emits for a field. Hidden classes and inline caches exist to recover the single load without giving up the dynamism.

From dictionary to shape

The observation behind hidden classes is that objects are created in patterns. A constructor sets the same properties in the same order on every instance, so all instances of a class end up with the same set of property names in the same insertion order. The runtime can record that pattern once and share it.

A hidden class, also called a shape or a map, is a descriptor of an object’s layout: an ordered list of property names, each with an offset into the object’s storage, plus a link to the object’s prototype and a pointer to any per-shape metadata. Every object carries a pointer to its shape. The object’s storage is a flat array of slots, and a property access becomes: load the shape pointer from the object, load the offset from the shape, load the value from the object at that offset.

That is three dependent loads instead of a hash computation, and the shape is shared, so the first two loads usually hit in cache. The remaining cost is that the offset is not a compile-time constant. The fix for that is the inline cache.

Shape transitions

Shapes form a tree. Adding a property to an object that has shape S produces a new shape S' with the new property appended, and the transition is recorded as an edge labelled with the property name. The next object that adds the same property to a shape-S object follows the existing edge instead of allocating a new shape.

S0 {} --"x"--> S1 {x:0} --"y"--> S2 {x:0, y:8}

The transition lookup is a hash lookup on the property name, but it happens only when a property is added, not on every access. Adding a property is a rarer operation than reading one, and the cost is proportional to the number of properties added, so the amortized cost is small.

Deleting a property breaks the tree’s monotonicity, since the resulting layout is not a shape that any sequence of additions produces. Implementations handle deletion by transitioning the object to a dictionary mode, where the shape is replaced by a hash table and subsequent accesses take the slow path. The mode is per-object and usually sticky: once an object has been in dictionary mode, engines rarely convert it back, because the shape tree no longer describes its layout. This is why deleting properties in a hot loop is a recognized performance hazard in JavaScript, and why the language guidance is to set a property to undefined rather than delete it when the intent is to clear a value.

Property order is observable, which constrains the design. Enumeration order in JavaScript is specified: integer-like keys in ascending numeric order first, then string keys in insertion order, then symbols. A shape must therefore record insertion order and distinguish index-like keys, or the enumeration code must reconstruct the order from the shape. Implementations that sort integer keys separately do so because the ordering requirement makes a pure insertion-order list insufficient.

Inline caches keyed by shape

An inline cache is a record attached to a single property access site in the code. It holds the shape the site saw last time and the offset that shape implies. On access, the code compares the object’s shape pointer against the cached one; on a match, it loads directly at the cached offset. On a miss, it falls back to the general lookup and updates the cache.

typedef struct {
    Shape *shape;      /* last shape seen at this site */
    int offset;        /* property offset for that shape */
} IC;

static inline Value load_prop(IC *ic, Obj *o, const char *name) {
    if (o->shape == ic->shape)                 /* monomorphic fast path */
        return o->slots[ic->offset];
    return load_prop_slow(ic, o, name);        /* lookup, then update ic */
}

The comparison is one pointer compare against a value already loaded, and the branch is perfectly predicted when the site is monomorphic. The load of the offset comes from the cache record, which is in the code stream’s vicinity and therefore usually in cache. The result is a property access that costs roughly a compare, a branch, and a load.

A site that sees several shapes is polymorphic. The cache grows into a small array of shape/offset pairs, searched linearly; the usual limit is four or so entries before the site is marked megamorphic and reverted to a generic lookup. The limit is a space-time trade: each additional entry costs a comparison, and beyond a handful of shapes the comparisons exceed the cost of a hash lookup. A megamorphic site is also a signal to the compiler that the code is not worth specializing, which is why megamorphic call sites often stay in the interpreter.

Polymorphic inline caches in the sense described by Hölzle, Chambers, and Ungar go further: each entry carries its own compiled stub, so the fast path for each shape includes the inlined body of the method. That converts a dynamic dispatch into a chain of shape tests, each followed by straight-line code, which removes the call overhead as well as the lookup.

Where the checks come from at the machine level

In a just-in-time compiled function, the inline cache is not a data structure consulted by generated code; it is a sequence of instructions the compiler emits and later patches. The shape check is a compare of the object’s shape field against an immediate, and the miss path is a call to a runtime stub that performs the lookup and patches the site to add the new shape.

Patching is what makes the cache work: the miss path rewrites the site so that the next access with the same shape takes the fast path. Engines record, for each shape, the list of code sites that depend on it, so that a change to a shape’s layout can deoptimize or invalidate the dependent code instead of leaving it reading the wrong offset. The dependency tracking is the same machinery that speculative compilation uses for type feedback, and the two are usually the same subsystem.

An important subtlety: a shape check proves the layout, not the value’s type. If the property holds a value whose type the compiler speculated about, the compiled code needs a second check on the value. This is why compiled property access in a dynamic language often consists of a shape compare, a value tag compare, and then the operation. Both compares are cheap and both are predictable, but they are two branches where a static language needs none.

Arrays and element kinds

The same machinery applies to indexed access, with the index as the “property name” that is not statically known. Engines track an element kind per array: packed small integers, packed doubles, packed values, or holey variants of each. The kind is stored in the array’s shape, and an indexed load checks the kind and then loads at base + index * width with the width implied by the kind. The width is where the value representation shows up in the object model: a packed double array can use 8 bytes per element only because the runtime knows every element is a double and needs no tag.

A store of a different kind transitions the array to a more general kind, and the transition must rewrite the backing store if the element width changes. Storing a double into an integer array requires either widening the array to doubles or boxing the value; engines choose based on the array’s kind and history. The consequence is that the order in which an array receives values affects its subsequent performance, which is observable and is why the guidance to initialize arrays with a consistent type exists.

Holes are the other complication. An array with a hole is not the same as an array of undefined, because in and enumeration distinguish them. Engines represent a holey array with a separate kind so that a load can check for the hole without a per-element sentinel comparison. The check is a bounds comparison plus a kind check, and the hole check folds into the kind.

Limits of the model

Shapes assume that an object’s layout changes monotonically by addition. Operations that violate the assumption, like Object.defineProperty with a non-default attribute, deletion, or setting a property on a sealed object, force the object out of the fast path. Accessors installed after creation similarly change the shape’s kind, because a property that runs code on access cannot be loaded with a plain slot read; the shape records that the property is an accessor and the access becomes a call.

Prototype chains add another dimension. A property that is not on the object may be on its prototype, and the lookup walks the chain. An inline cache can record a hit on a prototype property together with the shape of the holder, but a change to the prototype invalidates the cache. Engines handle this by tracking prototype validity: a shape records whether any of its instances’ lookups depend on a prototype that has since been modified, and the cache check includes that validity. The check is usually folded into the shape pointer comparison by giving the prototype a new shape when it is modified, which invalidates every cached hit that named the old one.

The overall structure is a bet: that programs are mostly monomorphic, that objects are mostly created by constructors that set the same fields, and that layouts rarely change after creation. When the bet holds, property access approaches the cost of a static field access. When it fails, the fallback is a hash lookup that is no faster than the naive implementation, and the machinery that tried to specialize becomes overhead.