Objects Under the Hood: Shapes, Hidden Classes, Inline Caches

The specification's view: ordered property lists

Since ES2015 the order of own properties is normative. OrdinaryOwnPropertyKeys returns: all array-index keys (canonical numeric strings in the range 0 ≤ i < 2³² − 1) in ascending numeric order; then all other String keys in ascending chronological order of creation; then all Symbol keys in creation order. Object.keys, JSON.stringify, Object.assign, spread, and Reflect.ownKeys all follow it. for…in is the exception: its order is only recommended to match, because it also walks the prototype chain and must skip shadowed and deleted keys, and the specification leaves the exact interleaving implementation-defined.

const o = { b: 1, 2: "two", a: 2, [Symbol("s")]: 3, 1: "one", "-1": "neg", "01": "leading zero" };
o.c = 4;
console.log(Reflect.ownKeys(o).map(String).join("  "));
// Integer-like keys come first in numeric order. "-1" and "01" are NOT array indices
// (not canonical numeric strings), so they are ordinary string keys in insertion order.
delete o.b;
o.b = "re-added";
console.log(Object.keys(o).join("  "), " <- b moved to the end: deletion forgets creation order");

The engine's view: Shape + slots

A dictionary per object would cost a hash lookup for every o.x and give the optimising compiler nothing to specialise on. Instead every engine separates an object into two parts. The Shape (V8 calls it a Map, older literature says hidden class; JavaScriptCore says Structure; SpiderMonkey says Shape) is an immutable, shared descriptor that records, for each property name, its attributes and the offset at which its value lives. The object itself holds a pointer to its Shape plus a fixed-size block of value slots, some allocated in-line in the object header (V8's in-object properties) and the rest in an out-of-line backing store. Two objects created by the same sequence of property additions share one Shape.

Shapes form a transition tree. Starting from the empty-object Shape, adding property x yields a child Shape "has x at slot 0"; adding y to that yields "has x at 0, y at 1". The tree is keyed by (property name, attributes, representation), so {x: 1, y: 2} and {y: 2, x: 1} end up on different Shapes even though they are indistinguishable to the specification. Changing a property's attributes (Object.defineProperty, Object.freeze), changing its representation (Smi → double → tagged), deleting a property, or changing the prototype all move the object to a different Shape, and some of those moves have no cheap child in the tree.

Inline caches: turning a lookup into a compare-and-load

With Shapes in place, the access o.x at a given site in the source can be executed as: load o's Shape; compare it against a cached Shape; if equal, load the slot at the cached offset. That cache is the inline cache (IC), and it is per call site, not per object: the bytecode for function get(o) { return o.x } has one IC for the .x access, and it remembers which Shapes it has seen. ICs pass through states:

Feedback recorded by ICs lives in a per-function FeedbackVector that the interpreter writes and the optimising compilers read. This is the entire basis of speculative optimisation (chapter 8): the compiler emits code that assumes the recorded Shape and inserts a check; if the check fails at runtime, execution deoptimises back to the interpreter. Consequently, a megamorphic site is not merely a slow lookup; it is a site about which the optimiser can prove nothing.

// One access site (`p.x + p.y`) fed with objects of 1, 2, 4, and 8 distinct Shapes.
const N = 1_000_000;

function makeObjects(shapeCount) {
  const out = [];
  for (let i = 0; i < N; i++) {
    const o = {};
    // Give each object a distinct prefix of dummy properties so its Shape differs
    // even though x and y are present on all of them.
    for (let k = 0; k < i % shapeCount; k++) o["pad" + k] = k;
    o.x = i; o.y = 1;
    out.push(o);
  }
  return out;
}

function sumXY(list) {
  let s = 0;
  for (let i = 0; i < list.length; i++) { const p = list[i]; s += p.x + p.y; } // <- one IC site
  return s;
}

for (const shapes of [1, 2, 4, 8]) {
  const list = makeObjects(shapes);
  sumXY(list); sumXY(list);                     // let the IC settle and the JIT tier up
  const t0 = performance.now();
  let r = 0; for (let k = 0; k < 10; k++) r += sumXY(list);
  console.log(String(shapes).padStart(2), "shape(s):", (performance.now() - t0).toFixed(1).padStart(7), "ms", r ? "" : "");
}
console.log("Expect a step change between 4 and 8 shapes (polymorphic -> megamorphic).");

Field representations and the double-boxing problem

A Shape records not only where a field is stored but what representation it has been observed to hold: Smi, Double, HeapObject, or Tagged (anything). V8 uses this to store doubles unboxed in a field when it has only ever seen doubles there. The representation can only generalise (Smi → Double → Tagged), and generalising it changes the Shape for every object sharing it; V8 does this by deprecating the old Shape and lazily migrating instances when they are next touched. A constructor that sometimes assigns this.value = 0 and sometimes this.value = 0.5 will therefore settle on Double; one that sometimes assigns null settles on Tagged and boxes every double written afterwards.

const N = 1_000_000;
class Point { constructor(x) { this.x = x; } }

function fill(list, mixed) {
  for (let i = 0; i < N; i++) list.push(new Point(mixed && (i & 1) ? i + 0.5 : i));
}
function total(list) { let s = 0; for (let i = 0; i < list.length; i++) s += list[i].x; return s; }

for (const mixed of [false, true]) {
  const list = []; fill(list, mixed);
  total(list); total(list);
  const t0 = performance.now();
  let r = 0; for (let k = 0; k < 5; k++) r += total(list);
  console.log(mixed ? "Smi + double mix" : "Smi only       ", (performance.now() - t0).toFixed(1), "ms", r ? "" : "");
}
console.log("The mixed case forces the field representation to Double (or Tagged) for every Point.");

Prototype chains, validity cells, and why `Object.prototype.foo = …` is expensive

A property miss on an object continues on its [[Prototype]] (OrdinaryGet, step 3). For the IC this is a problem: caching the result of a lookup that walked o → A.prototype → Object.prototype requires knowing that nothing along that chain has changed since. V8 handles this by giving each prototype object a validity cell: a small object whose value is invalidated whenever the prototype (or anything above it) is modified. An IC that resolved through the chain caches the receiver Shape, the holder, and a reference to the validity cell, and checks the cell on each hit. Mutating a prototype invalidates every cell below it, which invalidates every IC that depends on them. This is why adding methods to Object.prototype or Array.prototype at runtime, after code has warmed up, is a measurable performance event: it is not that the lookup is slower afterwards, it is that all dependent caches are thrown away simultaneously.

The same mechanism makes prototypes special in the Shape system. V8 marks an object as a prototype the first time it is used as one (Object.create(p), new F() where F.prototype === p, or Object.setPrototypeOf(x, p)), gives it its own unique Shape (so that mutating one prototype does not invalidate ICs for unrelated objects that happened to share its Shape), and switches it to fast mode with a stable Shape if it was in dictionary mode. Objects used as both instance and prototype get the worst of both worlds.

Practical rules that follow from the mechanism

• Initialise every field in the constructor, in the same order, with a value of the representation it will hold for its lifetime (0 vs 0.5 vs null matter). Class fields (x = 0;) do this for you.
• Never delete from an object that flows through hot code; set the property to undefined (or use a Map) instead. delete of the most recently added property is a special case V8 can handle by walking back one transition, but do not rely on it.
• Prefer Map for dynamic-key dictionaries. It is designed to be a hash table and does not perturb the Shape system. Object literals with computed keys go to dictionary mode quickly.
• Keep hot access sites monomorphic by keeping the set of Shapes reaching them small. Duck typing across many unrelated object literals is exactly how a site goes megamorphic.
• Do not mutate built-in prototypes after startup. Polyfills that run before application code are fine; monkey-patching during a hot path invalidates every dependent IC.
• Object.freeze, Object.seal, and Object.preventExtensions change Shape once. Freezing objects at construction is cheap; freezing objects that were already used unfrozen creates a second Shape population.