Inline Caches and Polymorphic Call Sites

A virtual call through a fixed slot is already fast: two loads and an indirect branch. A call in a language where the receiver’s class is not known until the call executes cannot use that slot directly at the implementation level the compiler sees, and a language where methods can be added to a class at run time cannot assume the slot exists yet or has the same meaning for every receiver. The standard answer is to let each call site remember what it has seen and, on a repeat, take a short path that skips the general lookup. That structure is an inline cache.

It is worth being exact about what the cache buys, because one common account of it is wrong. In a class-based system with a simple class-to-method-table mapping — the arrangement Smalltalk implementations used — a general lookup is already a single indexed load once the class and selector indices are known, so the cache’s saving over it is not asymptotic. Its real value appears in the second half of the problem: because the site stores a constant target, a compiler can turn the indirect call into a direct call and inline the callee, which a general lookup through a table cannot do at a call site the compiler cannot specialise. In a prototype-based system, where a lookup may walk a chain of arbitrary length, the same structure also turns a walk of d links into a single shape comparison. What the cache assumes can stop being true, and knowing when that has happened is the harder half of its design.

The shape of the fast path

A monomorphic inline cache guards one assumption. On the first execution of the call site, the runtime performs a full method lookup for the receiver’s class, stores the resulting target and the class it came from, and calls it. On later executions the site compares the receiver’s class with the stored class; on a match it jumps straight to the stored target, on a mismatch it falls back to the lookup and updates the cache.

The guard is a comparison of one word — a class pointer, or a hidden class identifier in an engine that uses shape objects — and the payoff is that the call no longer needs to consult any table. The comparison is predictable, so the branch is cheap; the stored target is a constant, so a JIT can replace the general lookup with a direct call to it, and can then inline it.

The classical Smalltalk implementation used a slightly different arrangement: the cache held the class and the target, and the lookup routine patched the call site’s inline data rather than the code, so no writable-code permission was needed for the common case. Engines that compile bytecode to machine code go further and rewrite the call sequence itself, replacing a general lookup call with a sequence of a class test and a direct call. This is why a call site’s first few executions are slower than its steady state: the site is being revised while it runs.

From mono to poly to megamorphic

A site that sees exactly one receiver class is monomorphic. A site in a loop over a heterogeneous collection sees several, and the natural extension is to store a small fixed number of class-target pairs and compare against each in turn — a polymorphic inline cache. The limit is small, commonly four entries, chosen so the linear scan stays within a few instructions and fits in one or two cache lines.

Beyond that limit, the site is called megamorphic, and engines generally stop caching and call the general lookup routine. The reason is arithmetic: a linear scan of n entries costs n comparisons, and past a handful the scan costs more than a single lookup through a class’s method table. The transition is not free of consequences for the optimiser either. A polymorphic site can still be inlined by generating a chain of guarded branches, one per cached class, each with its own specialised body. A megamorphic site cannot, so the compiler emits a generic call and loses constant propagation through the receiver for everything downstream.

The practical effect is that dispatch cost is a function of the variety of receivers at a site, not of the number of classes in the program. A program with a thousand classes and monomorphic call sites dispatches as fast as a program with two. A program with one hot loop that mixes five implementations pays the megamorphic penalty in that loop only. This is why megamorphic call sites are a profiling signal worth acting on, and why the remedy is usually to split the loop by type rather than to reduce the number of classes. The fixed-slot dispatch that a statically typed language uses at a monomorphic site is described in vtable layout and the cost of a virtual call.

The mapping problem

An inline cache needs a stable notion of “the class of this receiver” that can be compared in one instruction. In a language with declared classes and no dynamic modification, the class pointer in the object header serves directly. In a language where objects can gain and lose properties, or where classes can be reopened, the identity that matters is the object’s shape: the set of property names, their order, their types, and where they live in memory.

Engines represent shapes as objects of their own, shared by every object with the same layout, and transitions between shapes as a tree: adding a property to a shape produces a new shape, cached so that the same sequence of additions from the same starting shape yields the same shape object. The receiver’s shape pointer is then a single word that identifies its layout exactly. Two objects with the same properties added in a different order have different shapes, which is why construction order matters for performance in such engines and why initialising all fields in a constructor in a consistent order is a real, if unglamorous, optimisation.

The shape also records where each property is, and the access path assumes the shape’s property storage is a small table indexed directly by a per-shape slot number: the engine keeps the first several properties at fixed offsets in the object and, once the object outgrows that, stores the remainder in a dictionary whose lookups are slower. A call site caching, for a given shape, the location at which a property was found turns the access into a load, and the shape check makes it safe. The limit on in-object properties is an engine constant, not a language guarantee, so an object with many properties silently becomes slower to access without any change in program semantics.

Invalidation is the difficult half

Everything above assumes the cache’s stored assumption stays true. In a language where a class can gain a method, replace a method, or change its prototype chain at run time, it does not.

The standard mechanism is a dependency: when a call site caches a target obtained from a class’s method table, it registers a dependency on that table entry. When the entry is replaced, the runtime walks the registered sites and clears them. The walk is proportional to the number of sites that depend on the entry, so a program that adds a method to a widely used class invalidates a large number of sites at once, and the cost appears as a pause at the point of modification rather than at the call sites. An engine can bound that cost by invalidating lazily — marking the entry’s version and having each site re-check the version on next execution — which turns a burst of work into a small per-call overhead.

Prototype mutation is harder because a method lookup can traverse several links, and a change anywhere in the chain changes the result for every object that delegates through it. Engines handle this by tracking prototype validity: a prototype object carries a flag, and a site that cached a target found through it checks the flag rather than re-walking. Writing to the prototype clears the flag and invalidates dependents. This is the mechanism behind the advice, in prototype chains and delegation-based dispatch, that mutating shared prototypes is expensive: it is not merely a style preference, it converts every dependent site from a guarded direct call back into a general lookup.

There is a third case that catches implementations out: a cache can be invalidated by a change to a class the site has never seen. Adding a method to a superclass changes the resolution of a call for subclasses that do not override it, and those subclasses’ cached targets are now stale even though their own definitions did not change. Correct invalidation therefore has to propagate through the inheritance graph, not just touch the modified class. Engines that get this wrong produce the classic bug where a program behaves differently after a warm-up period, because a cache populated during warm-up was never cleared.

Guards, speculation, and deoptimisation

A JIT can go beyond caching the target and speculate on the receiver’s class: emit the callee’s body inline, guarded by a class check, and place a deoptimisation path at the guard’s failure branch. The failure path reconstructs the interpreter state from the optimised frame and resumes in the interpreter at the same bytecode. Deoptimisation is what makes aggressive inlining safe in the presence of dynamic dispatch, and its cost is why engines prefer to inline only sites that have proven stable.

Speculation interacts with invalidation in a way worth stating: an inlined body is only valid while the class’s method is unchanged, so the compiled code must be invalidated not only when the receiver’s class changes but when the inlined callee’s definition changes. A method replacement therefore has to reach into compiled code and discard it, which is a stronger requirement than clearing a cache entry, and it is the reason many engines simply discard the whole optimised function containing the inlined call.

Where the cost lands

The steady-state cost of a monomorphic inline cache is one compare and one branch, and the call itself is direct. A polymorphic site with four entries costs a short chain of compares, still cheaper than a table lookup. A megamorphic site costs the full lookup: computing the selector’s index, loading the entry from the receiver’s class table, and an indirect call, plus the loss of inlining for everything the callee would have enabled.

The costs that matter are therefore not per-call arithmetic but the second-order effects: loss of inlining, loss of escape analysis on the receiver, and the pause when a widely depended-on method table entry changes. A design that keeps call sites monomorphic — by keeping collections homogeneous, by splitting code paths per type early, by avoiding method replacement on hot classes — keeps the fast path available without any change to the language. A design that relies on dynamic method replacement for its architecture will pay invalidation costs proportional to how widely the replaced methods are used, and no amount of engine tuning removes that proportionality.