Polymorphic and Megamorphic Inline Caches

A monomorphic site is a site that has seen one layout, and its fast path is one comparison. Real programs pass more than one kind of object to the same function, so the interesting question is what happens on the second kind. The answer has three stages, and the transitions between them are the runtime’s judgement about how much speculation is still worth paying for.

The stages are named for the number of layouts a site remembers. Monomorphic: one. Polymorphic: a small number, conventionally between two and four, sometimes more. Megamorphic: too many to enumerate, at which point the site stops remembering layouts and starts doing a real lookup with a small side cache.

The polymorphic chain

When a second layout arrives at a monomorphic site, the runtime has two choices: recompile the site into a form that handles both, or discard the site’s speculation and revert to the generic path. The first is almost always better, because two layouts at a site usually means the site is called from two places with two kinds of object, and both are hot.

The resulting code is a chain. The cached layout entries are checked in order; the first match dispatches to a block that loads from that layout’s offset. The check for entry n happens only after entries 0 through n−1 have failed, so the cost of a hit is proportional to its position in the chain.

  guard layout_A  -> load [obj + 24]
  guard layout_B  -> load [obj + 32]
  guard layout_C  -> load [obj + 16]
  otherwise       -> call runtime lookup(obj, "x")

Ordering therefore matters, and the order is not arbitrary. Implementations that count hits reorder entries so the most frequent layout is checked first, or sort at compile time by observed frequency. A site whose layouts are all equally frequent pays the average position, which is half the chain length; a site with one dominant layout and two rare ones pays nearly the monomorphic cost. Without reordering, a chain built in the order layouts were first seen can put the dominant layout last, which is the worst arrangement and one that occurs naturally when a rare shape appears early in a program’s execution.

The dispatch target differs per layout, so the chain cannot be a single branch with a computed offset. Each case needs its own load, because the offset is a constant baked into that case. The optimizer can still merge the results: if all cases load a value of the same representation into the same register, the join point is a phi node and the rest of the computation is shared.

What the polymorphic case buys and what it costs

The gain over the generic path is the same as in the monomorphic case, diluted. The layout check replaces a name hash and a probe, and the load is a constant offset. For a chain of two, the cost is roughly two compares and one load, against a hash and a probe for the generic path. That is still a substantial win.

The cost is code size. Each case duplicates the load and any immediately following computation that depends on the loaded value’s representation. A function with several polymorphic property accesses multiplies those cases, and the multiplication is per site, not per function, so a function with four polymorphic sites and three layouts each has eighty-one possible paths through the code. The optimizer usually does not duplicate the whole function; it duplicates only the blocks that depend on the guarded value, and rejoins as early as it can. But the code growth is real, and it competes with instruction cache capacity, which on common architectures is measured in tens of kilobytes for the first level.

The second cost is the guard chain’s length in the common case. If the layouts are equally likely and the chain has four entries, the average hit is at position 2.5, which is 2.5 compares and 2.5 branches per access. A branch misprediction costs on the order of ten to twenty cycles on a modern core, and a well-predicted chain costs nearly nothing per compare, so the chain is cheap when the distribution is skewed and expensive when it is uniform. That is the argument for reordering, and it is also the argument for giving up when the distribution is flat and the chain grows.

The megamorphic stub

Past a threshold, the runtime stops extending the chain. The site is marked megamorphic, and access goes through a stub that performs a real lookup with a small cache in front of it.

The stub’s cache is typically a global or per-isolate table holding, for the property the stub was built for, a mapping from layout to offset. When the stub is built per property name, the layout pointer is the only key it needs, so the lookup is: hash the pointer, index the table, compare the stored layout, and on a match load from the stored offset. On a miss, the stub calls the full runtime lookup and inserts the result.

This is a hash lookup again, but a much cheaper one than the per-object table. The key is a pointer, so the hash can be a shift and a mask of the pointer’s bits rather than a hash of name bytes. The table is shared across all sites accessing the same property name, so its hit rate is high even when each individual site is megamorphic. And the table’s entries are inserted once and rarely evicted, so the probe sequence is short. A miss in this table is a full runtime lookup, and how the site is rewritten afterwards is described in Cache Miss Handling and Patching Code at the Access Site.

The reason the threshold exists is that the chain’s cost grows linearly with the number of layouts while the stub’s cost is roughly constant. Somewhere around four to eight entries the lines cross. The exact number depends on the relative cost of a compare-and-branch against a hash-and-probe, and engines choose it by measurement rather than by derivation. V8’s inline cache states, for instance, run through uninitialized, monomorphic, polymorphic, and megamorphic, and the polymorphic state holds only a handful of entries before the site is promoted; the specific limit is a tuning constant that has changed across releases.

Why megamorphism is not a failure

A megamorphic site is slower than a monomorphic one and the difference is not small, but it is still faster than the generic lookup path with no cache at all, and it is correct for every receiver. The runtime has not given up on the site; it has changed the shape of its speculation from “these specific layouts” to “whatever layouts have been seen recently, in a table”.

The distinction matters for how the site behaves under changing input. A polymorphic chain is fixed at the moment it was compiled; a new layout at the site causes a miss, and enough misses cause a recompile that may push the site to megamorphic. A megamorphic stub adapts continuously, because its table is populated at run time.

The cost that does not go away is the loss of downstream specialization. A megamorphic load returns a value whose type is not known, so the optimizer cannot unbox it, cannot keep it in a register as a float, and cannot inline operations on it. The load itself is a fraction of the total cost; the loss of specialization around it is usually the larger part.

Shapes of polymorphism that occur

Three patterns account for most polymorphic sites.

The first is a family of classes with a common interface. A function that reads .length from an array, a string, and a typed array sees three layouts at one site, and the property is at a different offset in each. The chain handles it, and the site is genuinely polymorphic because the function is genuinely used on three kinds.

The second is a class hierarchy where subclasses add fields. A base class with fields at offsets 0 through 16 and a subclass with two more fields has a different layout, and a site reading a base-class field sees both layouts. If the base fields are at the same offsets in both, which the transition tree arrangement usually ensures, the site could in principle use one offset for both, but the guard still has to check both layouts. Exploiting the shared prefix would need a single guard that accepts several layouts at once; few engines offer one, and most pay the chain instead.

The third is the accidental case: the same logical record built in two different orders by two different code paths. This produces two layouts that no design intended, and the fix is in the program, not the runtime, as described in Hidden Classes and the Transition Tree Behind Property Writes.

Interaction with the feedback the optimizer reads

The count of layouts at a site is itself recorded, because the optimizer needs it. A site that the interpreter saw as polymorphic over three layouts may be compiled with three cases, and the compiled code carries the same count so that a fourth layout triggers a deoptimization rather than a silent miss.

This is why warm-up matters and why it is not merely about the cost of interpretation. The feedback collected during warm-up determines the shape of the compiled code, and a program that changes the kinds of objects it passes to a function after that function has been optimized pays for deoptimization and recompilation. The mechanism that records and consumes this feedback is covered in Type Feedback and the Speculation Budget; the point here is that the polymorphic and megamorphic states are not only run-time behaviours but inputs to the compiler’s decisions.