JITimplementation

Inline Caches

Cache the resolved answer at the call site itself, guarded by a check of the key that produced it. One target is monomorphic and nearly free; a few is polymorphic and still cheap; many is megamorphic, and the right response is to stop caching rather than to cache harder.

The question

A dynamic call has to look up its target every time. How does caching that lookup at the call site work, and why does it stop working when the site sees too many things?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

The call site stops being a pure instruction and becomes a small mutable data structure attached to that instruction: a key that was observed, the result that was resolved for it, and a fallback. The instruction stream is now self-modifying in a controlled way — code that carries its own memory of what happened here before. That representation exists to answer a question a static call site cannot express: not "what could this call reach" but "what did *this particular site* reach, and can I reuse that answer".

What this phase may assume or do

A cache hit may bypass the general lookup only if the cached key is *sufficient* to determine the result — the key must capture everything the lookup depends on. For a property access that means the receiver's complete shape, not merely that it has a property of that name, since the same name can resolve to a data slot on one shape and an accessor on another. Any change that could invalidate a cached entry must either be captured by the key or must invalidate the cache directly. And the cache must be updated safely with respect to other threads: a partially written entry that a concurrent execution can observe is a correctness bug, not a stale-cache performance problem.

Key points

  • An inline cache stores the resolved result at the call site, keyed by what was observed, and checks the key before reusing it.
  • It works because most sites see one receiver shape for their entire lifetime — an empirical regularity, not a guarantee.
  • Monomorphic is one comparison; polymorphic is a short chain; megamorphic means giving up, and giving up is the correct policy.
  • A megamorphic site is valuable information in the negative direction: it tells the compiler not to speculate there.
  • Inline caching needs no compiler at all — an interpreter can do it, and a specializing interpreter is largely this.
  • What a JIT adds is inlining through the cached target, which unlocks every cross-procedural optimization behind it.
  • A cache miss costs a lookup; a failed compiled guard costs a deoptimization, which is why caching is the more liberal technique.
  • The key must be strong enough to capture every change that could invalidate the entry, or explicit invalidation is required.
  • Caches are per site, so code structure decides their effectiveness: one generic helper that everything calls sees every shape.

The lookup that is the same answer every time

A dynamic call or property access has to resolve something before it can act: which method does this name refer to for this receiver, at what offset does this field live in this object. In a dynamically typed language that resolution can be substantial — walking a prototype chain, consulting a hash table, checking for accessors — and it happens on every execution of the site.

The observation that makes inline caching work is empirical and strong: at the overwhelming majority of sites, the answer is the same every time. The same site sees the same receiver shape, and therefore resolves to the same target, on execution after execution. So resolve once, remember the answer *at the site*, and on subsequent executions check whether the key is the same and reuse it if so.

The check is a guard in the sense of [[guards]] — one comparison, well predicted — and the reuse eliminates the entire lookup. That is the whole idea, and it dates to Smalltalk implementations in the 1980s, well before the JITs that later depended on it. It is worth noticing that an inline cache is useful even without any compiler: a purely interpreted system can inline-cache its own bytecode, which is exactly what a specializing interpreter does.

A monomorphic inline cache at one property-access site
1site_47:                          // one cache per site, not per shape
2  if (shape_of(obj) == site_47.key) {
3    v = load [obj + site_47.offset]   // hit: one compare, one load
4  } else {
5    v = slow_lookup(obj, "x")         // miss: full resolution
6    site_47.key    = shape_of(obj)    // and rewrite the cache for next time
7    site_47.offset = resolved_offset
8  }

The cache belongs to the *site*, not to the shape and not to the object. Two call sites reading the same property on the same objects have independent caches, which is why one polluted site does not slow the others — and why a single generic helper that everything calls funnels every shape through one site and ruins it for all its callers.

One, a few, and too many

implementationThe chain limit before a site is declared megamorphic is a small engine constant — a handful of entries — and differs between V8, JavaScriptCore, HotSpot and Ruby, and between versions of each. HotSpot inlines bimorphically, handling two receiver types before falling back to a virtual call. None of these thresholds is a documented stable interface, and code tuned to a specific one is tuned to a specific build.

The three states are the lesson, and each is a different policy rather than a different amount of the same policy.

Monomorphic — the site has seen one key. The cache is one comparison and a direct use of the cached result. This is the case worth designing for, and it is the common one: measurements of typical object-oriented programs consistently find that most sites see exactly one receiver type over their lifetime.

Polymorphic — the site has seen a few. The cache becomes a short chain of key comparisons, each with its own result, checked in order. Two or four entries is still dramatically cheaper than a full lookup, and a compiler can still inline all of them behind their respective guards. The cost is linear in the chain length, which is why the chain has a limit.

Megamorphic — the site has seen many. Extending the chain further stops paying: the comparisons cost more than the lookup they are avoiding, and the site's branch behaviour becomes unpredictable. So the cache gives up and switches to a general mechanism — typically a global hash-table cache keyed by shape and name, shared across all sites, or a straight uncached lookup. Giving up is the correct policy here, and recognising when to give up is as much of the design as caching is.

The three states, and why each policy is right for its casetypical
StateStructure at the siteCost of a hitWhat the compiler can do with it
UninitializedNo key yetn/a — first execution always missesNothing; no profile information exists
MonomorphicOne key, one resultOne comparisonGuard and inline the single target — the largest available win
PolymorphicA short chain of key/result pairsUp to N comparisons, N smallInline two or so behind guards; dispatch for the rest
MegamorphicNo per-site cache; a shared table or a plain lookupA hash lookup, or the full resolutionNothing — and knowing not to try is the value

Inline caches are speculation without a JIT

It is worth being precise about how this relates to the rest of the module, because inline caching is frequently described as a JIT technique and is not one. Every ingredient of [[speculative-optimization]] is present — an observed fact, a cheap sufficient check, a fallback — and none of it requires a compiler. A bytecode interpreter can maintain caches in its instruction stream and get most of the benefit; that is precisely what the specialization described in [[interpreter-performance]] is.

What a JIT adds is *consequences*. An interpreter's inline cache saves the lookup and nothing else. A compiler that reads the same cache state as profile data can go much further: if the site is monomorphic, emit a guard and a direct call, then inline through it — and inlining is the transformation that unlocks constant propagation, escape analysis and everything else across what used to be a call boundary. The cache told it which target to inline; the guard makes it legal.

The failure modes also differ, and the difference matters. An inline-cache miss is cheap: fall through to the slow lookup, update the entry, continue in the same frame. A failed guard in compiled code is a [[deoptimization]] — a frame reconstruction and a discarded compilation. So inline caching is the smaller bet, with a much cheaper downside, which is why it is used far more liberally than full speculation and why it exists in systems that have no optimizing compiler at all.

  • An inline cache needs no compiler; it is a per-site memo with a guard, and interpreters use it directly.
  • A JIT consumes cache state as type feedback, which is where [[why-runtime-information-helps]] gets most of its input.
  • The monomorphic case is what enables speculative inlining, which is the largest structural transformation available to the optimizer.
  • A cache miss costs a lookup; a failed guard in compiled code costs a deoptimization. Same idea, wildly different downside.
  • Megamorphic sites are informative in the negative direction: they tell the compiler not to speculate, which prevents a compile that would immediately deoptimize.
  • Because caches live per site, code structure directly determines how well they work — one shared generic helper concentrates every shape onto one site.

Invalidation, and the ways a cache lies

implementationV8 keys inline caches on hidden-class ("map") identity and maintains dependency groups so that a prototype mutation can invalidate dependent code and caches; HotSpot's inline caches are keyed on the receiver's class and are patched at safepoints; Ruby uses a global constant-cache generation counter that a redefinition bumps, invalidating every cache at once. Each of these is a different point on the same tradeoff between key precision and invalidation cost, and all have changed across versions.

A cache is only correct while the resolution it recorded remains the right answer, and in a language that permits mutation at run time that is not automatic. Redefining a method, adding a property to a prototype, or changing a data property into an accessor can all make a cached entry wrong. If the key does not capture the change, something has to invalidate the cache explicitly.

This is why the key is usually a *shape* rather than a class or a type name. A shape is a runtime-managed description that changes identity when the object's layout changes, so a mutation that would invalidate a cached offset also changes the key and turns a would-be wrong answer into an ordinary miss. Where that is not enough — a prototype mutated after many objects share its shape — engines maintain explicit invalidation, either by bumping a generation counter that all keys incorporate or by tracking dependencies from caches to the cells they resolved through.

The subtler correctness question is concurrency. The cache is mutable data in the instruction stream, written by whichever thread happens to miss. If a concurrent execution can observe a half-written entry — a new key with the old offset — it takes a fast path that is wrong. Engines address this with single-word atomic updates, with a validity flag written last, or by only mutating caches at safepoints. It is a genuine memory-model problem, sitting inside what looks like a pure optimization.

How it works

The steps, in the order the compiler takes them.

  • Attach a small mutable record to each cacheable site: a key field, a result field, and a state — uninitialized, monomorphic, polymorphic or megamorphic.
  • On execution, compare the receiver's shape against the cached key; on a hit, use the cached result directly.
  • On a miss from the uninitialized state, perform the full resolution, store the key and result, and move the site to monomorphic.
  • On a miss from monomorphic, resolve again and extend the site to a short chain of key/result pairs, moving it to polymorphic.
  • On a miss that would exceed the chain limit, discard the per-site entries, mark the site megamorphic, and route it to a shared table or a plain lookup thereafter.
  • Key the cache on a shape or class identity that changes whenever the resolution could change, so most invalidation is automatic.
  • For changes a key cannot capture — a prototype mutated, a method redefined — maintain explicit invalidation via dependencies or a generation counter incorporated into every key.
  • Update the cache with a single atomic store, or write a validity flag last, so no concurrent execution can observe a partially written entry.
  • Expose the cache state to the compiler as type feedback, so that a monomorphic site becomes a guard and a direct call, and a megamorphic site becomes a decision not to speculate.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • One generic dispatch helper that every call in the system funnels through has a single site that sees every shape. It goes megamorphic, nothing above it inlines, and the slowdown appears across the whole application with no individual hot spot to point at.
  • A cache is keyed on something weaker than the full shape — "has a property called x" — and a hit returns an offset that is wrong for this object, producing a wrong value with no error.
  • A prototype is mutated after objects sharing its shape are in wide use, and without an invalidation mechanism cached entries continue to return the old resolution.
  • A cache entry is written non-atomically and a concurrent thread reads a new key with a stale result, taking a fast path that is wrong for it — a data race whose symptom is a wrong answer under load and never in testing.
  • Objects are given their properties in different orders on different code paths, producing several shapes for what the programmer thinks of as one type, and every site that touches them is polymorphic instead of monomorphic.
  • A site oscillates just below the megamorphic threshold, rewriting its chain constantly, so the cache maintenance costs more than the lookups it avoids.
  • Caches accumulate per site across a large program and their memory becomes significant in a constrained runtime, particularly when polymorphic chains are retained for sites that are executed rarely.

When it helps

  • Dynamic dispatch of any kind: method calls in dynamically typed languages, interface calls, property access on objects with runtime-managed layout.
  • Sites that are monomorphic in practice, which empirically is most of them — and where the cache converts a lookup into a comparison.
  • Interpreters with no compiler at all, where the technique delivers a large fraction of its value with none of the JIT machinery.
  • Feeding a compiler: the cache state is exactly the type feedback that speculative inlining needs, collected as a side effect of making the interpreter faster.
  • Deciding not to optimize. A megamorphic site prevents a speculative compile that would have deoptimized immediately, which is a saving that never appears in any benchmark.

When it hurts

  • Genuinely polymorphic sites — dispatchers, serializers, framework hooks — where the chain never settles and the maintenance is pure overhead.
  • Programs that mutate structure at run time, where invalidation is frequent and each invalidation discards work.
  • Memory-constrained runtimes, where a per-site record for every cacheable site in a large program is a real cost.
  • Highly concurrent workloads, where cache updates from multiple threads are both a correctness hazard and a source of contention on shared cache lines.
  • Reasoning about performance, because the same source code is fast or slow depending on which shapes have flowed through it — a property of history rather than of the code.

What it costs

Every one of these is paid by something.

  • An inline cache buys the elimination of a full lookup and pays a comparison per execution plus a mutable record per site, in memory that scales with program size rather than with hotness.
  • A longer polymorphic chain buys coverage of more shapes and pays linearly in comparisons and unpredictably in branch behaviour, which is why the limit is small.
  • A precise key — the full shape — buys automatic invalidation for most mutations and pays with more shapes, and therefore more misses, than a coarser key would produce.
  • A coarse key with explicit invalidation buys fewer misses on stable code and pays with an invalidation mechanism and, when it fires, wholesale discarding of caches that were still valid.
  • Exposing cache state as compiler feedback buys speculative inlining and pays by coupling the interpreter's data structures to the compiler's assumptions, so that a change to either can silently degrade the other.

What else you could do

What a different compiler or language does instead, and when that is better.

  • A virtual method table: a fixed-offset indirect call with no caching, which is what statically typed languages with single inheritance use. Constant cost, no adaptation, and no information for a compiler to use.
  • A global lookup cache keyed by shape and name, shared across all sites. Lower memory, no per-site adaptation, and it is what megamorphic sites fall back to.
  • Static resolution: sealed classes, final methods, or a whole-program analysis proving a single implementation, which removes the dispatch entirely — [[devirtualization]] and [[whole-program-optimization]].
  • Monomorphization at compile time, which produces a separate specialized copy per concrete type and makes every call direct — [[monomorphization]], at the cost of code size.
  • Full speculative compilation with a guard and a deoptimization exit, which is what a JIT does on top of the cache: a larger bet with a larger payoff and a far more expensive failure — [[speculative-optimization]].

See it for yourself

The flag, dump or tool that shows you this directly.

  • V8: --trace-ic prints every inline-cache state transition with the site and the shapes involved, which is the single most direct way to watch a site go monomorphic and then megamorphic.
  • V8: %HaveSameMap(a, b) under --allow-natives-syntax tells you whether two objects share a shape, which is usually the answer to "why is this site polymorphic".
  • HotSpot: -XX:+PrintInlining reports bimorphic inlining and the refusals, and a "megamorphic" refusal at a hot site explains a great deal.
  • JavaScriptCore: --dumpDisassembly and the JSC shell's tracing options show the polymorphic chains as generated stubs.
  • Ruby: RubyVM::InstructionSequence disassembly shows the call sites, and the global constant-cache generation counter is bumped on redefinition — a coarse invalidation you can observe by measuring the cost of redefining a method in a loop.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "An inline cache caches the value." It caches the *resolution* — which target, which offset — not the data at that offset. The load still happens; what is skipped is working out where to load from.
  • "Megamorphic means the cache failed." It means the cache correctly concluded that caching does not pay here. Continuing to extend the chain would be the failure.
  • "Inline caches are a JIT feature." They predate JIT compilation and work in a pure interpreter. What a JIT adds is inlining through the cached target, which is a separate and larger thing.
  • "A polymorphic site is nearly as good as a monomorphic one." For the lookup, roughly. For the compiler, not at all: a monomorphic site can be inlined behind one guard, and a four-way polymorphic site usually cannot.
  • "Two objects with the same fields have the same shape." Only if the fields were added in the same order and by the same transitions. Constructing the same logical type two different ways produces two shapes and turns every site that sees both polymorphic.

Misconceptions

The claim, and what is actually true.

Inline caching is an optimization the compiler performs.
It is a runtime data structure updated during execution, and it works with no compiler at all. A compiler consumes its state as feedback, which is a separate use of the same mechanism.
A megamorphic site should be optimized by making the cache bigger.
Past a small number of entries the comparisons cost more than the lookup they avoid, and the branch becomes unpredictable. The correct response is to stop per-site caching and use a shared table or a plain lookup.
Inline caches are safe because a wrong cache just causes a miss.
Only if the key is sufficient and updates are atomic. A key that under-determines the resolution produces a wrong answer on a hit, and a non-atomically updated entry produces one under concurrency.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

Every time a program calls a method on an object, something has to work out which method that is. Since the answer is nearly always the same at any given place in the code, the system writes the answer down right there at that spot, along with a note about which kind of object it was for. Next time, it checks the note — one comparison — and skips the search. If the note stops matching too often, it stops keeping notes there, because checking many notes is slower than searching.

practical

The practical consequences are about code shape. Construct objects the same way every time, so they share a shape and sites stay monomorphic — adding properties conditionally after construction is the most common way to create several shapes for one logical type. Avoid the single generic helper that every call in the system routes through: its sites see every shape in the program and go megamorphic, which costs not just that function but every caller that could have inlined it. And when something is slow for no visible reason, --trace-ic will often show a site transitioning to megamorphic at exactly the moment the slowdown began.

advanced

The deeper point is that an inline cache is the minimal viable unit of the entire speculation architecture, and studying it in isolation clarifies what the rest of the module adds. It has the observation, the key, the guard and the fallback — but the fallback is local, so a wrong bet costs a lookup rather than a frame reconstruction. That makes the technique nearly free to apply liberally, which in turn is what allows it to serve as the profiling substrate for everything above it. There is an elegance in this: the mechanism that makes the interpreter faster is the same mechanism that tells the compiler what to assume, so the profiling is not overhead added for the compiler's benefit but a by-product of an optimization the interpreter wanted anyway. Systems where the profiler and the optimizer share a data structure like this tend to be the ones where speculation works well, and the historical record supports it: Self, Smalltalk and the JavaScript engines that descended from that lineage all built the caches first and the speculative compilers on top of them.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationChain limits, what constitutes a key, and how invalidation works differ across V8 (hidden-class identity plus dependency groups), HotSpot (receiver class, patched at safepoints, bimorphic inlining), JavaScriptCore (generated stub chains) and Ruby (a global generation counter). All have changed between versions, and none of the thresholds is a stable interface.
typicalThe claim that most sites are monomorphic is an empirical regularity measured on mainstream object-oriented and dynamic programs, and it is the entire basis for the technique. It does not hold for dispatchers, serializers, reflective code or framework internals, and those are exactly the sites that go megamorphic and drag their callers down with them.
simplifiedAtlasLang resolves calls by name in a module-level map and has no inline caches, no shapes and no objects, so the code in this lesson is illustrative rather than produced by our toolchain. What our VM does show is the underlying cost being avoided: CALL add / 2 performs a name lookup on every execution, visible at /compilers/vm.

If you were asked this in an interview

  • What exactly does an inline cache cache, and what is the key?
  • Why does a site become megamorphic rather than growing its chain further?
  • An inline cache needs no JIT. What does a JIT add on top of one?
  • Two objects have the same fields and a site that sees both is polymorphic. How is that possible?
  • What could make a cached entry wrong, and what are the two ways of dealing with it?

Connections

DSAhash-table
Computer Architecturebranch-predictionbranch-mispredictioncache-linesmemory-hierarchy
Concurrencydata-racesmemory-model
Performancecpu-profilingjit-and-warmup
Domains that do not exist yet
  • Programming Languages & Runtime Internals — Hidden classes and shape transitions: how a runtime assigns objects a layout identity, and what makes two objects share one
    The key an inline cache compares is a runtime-managed object shape, created and transitioned by the object model as properties are added. Whether two objects share a shape — and therefore whether a site is monomorphic — is decided entirely by that model, so the object model determines the effectiveness of a compiler technique it knows nothing about.
  • Programming Languages & Runtime Internals — Method lookup and dispatch: prototype chains, method resolution order, and the tables an uncached lookup actually walks
    The cache exists to skip a lookup whose cost and correctness rules belong to the runtime's dispatch semantics. What may be cached, and what invalidates a cached entry, follows directly from how the language defines lookup — so the cache design is downstream of a dispatch design owned there.