Inline Caches

The oldest idea in dynamic-language optimization — Deutsch and Schiffman, 1984 — and still the one with the best return. It is also the technique your profile most likely says to build first.

The Problem

for i = 1, #candidates do
  local a = candidates[i]
  local s = a.semantic_score     -- what does this cost?
end

a.semantic_score is: hash the key string, probe the table, compare, return. Or, for userdata: look up the metatable, find __index, call a native function, look up an accessor table, call the accessor. Three to six operations for what a static language does with one mov and a compile-time offset.

And it does that 10,000 times, for the same shape of object, every time.

The Idea

At any given call site, the object is almost always the same shape as it was last time. So cache the answer at the site, with a guard that checks the assumption.

   site: a.semantic_score        (bytecode offset 0042)

   ┌─────────────────────────────────────────┐
   │ cached_shape: Article-userdata          │  ← the GUARD
   │ cached_slot:  accessor #1               │  ← the ANSWER
   └─────────────────────────────────────────┘

   if shape(a) == cached_shape { use accessor #1 }     // fast: one compare
   else { full lookup; update the cache }              // slow: fall back

The cache lives at the instruction, not in the object. That is what "inline" means — the cache is inline in the code stream — and it is why two different sites reading the same field have independent caches.

The Three States

Named by the Self team in 1991 and still the vocabulary V8 uses:

   uninitialized ──first hit──▶ monomorphic ──miss──▶ polymorphic ──overflow──▶ megamorphic
                                     ▲                     │
                                     └────── hit ──────────┘        (megamorphic is TERMINAL)

Megamorphic must be terminal. A site that oscillates between polymorphic and megamorphic pays the cache-update cost forever and the lookup cost. Once a site has seen five shapes, it has told you what kind of site it is.

What Is a "Shape"?

This is the question, and Ember's answer is deliberately simpler than V8's.

Decision: B for userdata, C for tables.

B is where the win is, because userdata field access is the expensive path and every instance of a type has an identical shape. There is no transition problem: an Article is always an Article.

C is weaker than V8's hidden classes — it caches for one table, not for a shape shared by many tables — so a site iterating over 10,000 distinct tables stays megamorphic where V8 would be monomorphic. Say that explicitly: Ember's table cache helps the "same table, many reads" pattern (a config table, a module table, self in a loop) and not the "many tables, same shape" pattern. If your profile says the second one dominates, hidden classes are the upgrade, and they are a much larger project.

Invalidation

Every cache needs an invalidation story, and a cache without one is a correctness bug.

#![allow(unused)]
fn main() {
pub struct Table {
    // ...
    /// Incremented on any STRUCTURAL change: a new key, a deleted key, a
    /// metatable change, or a rehash that moves entries. NOT on a value update
    /// to an existing key — that does not change where the value LIVES.
    version: u32,
}
}

That distinction is the one to get right:

Get the first row wrong and every field assignment invalidates every cache — which turns the optimization into a pessimization on write-heavy code, silently.

For userdata (approach B) there is no invalidation at all: a type's accessor table is built once and never changes. That is the second reason B is the better bet.

Where the Cache Lives

#![allow(unused)]
fn main() {
// The bytecode gains a cache index. The caches live in a side array on the
// Proto, NOT in the instruction stream, so `Op` stays 8 bytes and `Chunk`
// stays immutable and shareable between closures.
Op::GetFieldCached(u16 /* constant */, u16 /* cache slot */),

pub struct Proto {
    // ...
    pub caches: Vec<Cell<InlineCache>>,   // one per cached site
}
}

Note: CPython 3.11+ takes the other option and puts cache entries between instructions in the code array, which is why its instruction stream became variable-stride. Ember uses a side array because Chunk is shared by every closure over a Proto — and a shared, mutable side array is fine (caches are a hint, and a stale one is only a miss) while a mutable instruction stream would need more care. Note the tradeoff; it is a real fork.

A cache is a hint, never a source of truth. If a cache is wrong, the guard fails and you take the slow path. That property is what lets caches be shared, unsynchronized, and discarded at any time.

Production Concerns

• Correctness first: the guard must be complete. A guard that checks the table id but not the version is wrong. Write the test that mutates the table's shape between two reads at the same site.
• Caches must not keep objects alive. A cache holding a GcRef is a GC edge — either trace it, or (better) store a weak identity like the table's stable id and treat a mismatch as a miss. Ember stores the id, so caches are not roots. That is a deliberate simplification and it removes a whole class of leak.
• Megamorphic sites should be cheap. Once terminal, the check should be a single branch that skips the cache entirely, not a scan of four dead entries.
• The cache is per Proto, and Protos are shared across engines if you ever add a bytecode cache. A cache populated by one engine and read by another is still correct (it is a hint, and the guard checks) but the ids must be engine-local or the guard must include an engine id. Think about this before Lab 22's cache goes cross-engine.
• Instrument it. --trace-ic printing per-site state transitions and miss reasons is what turns "the cache did not help" into "the cache went megamorphic at offset 0042 because the loop iterates over distinct tables".

Relation to Real Systems

LuaJIT's absence from the cache column is instructive: a trace compiler does not need inline caches because it specializes an entire path at once, guarding on types at the trace head. Two different answers to the same problem, and knowing that is what makes the JIT chapter land.

Things to Notice

• The cache lives at the site, not in the object. That is what "inline" means.
• A guard plus a slow path is the entire technique, and every later optimization in this section is the same shape with a bigger payoff and a harder way back.
• Megamorphic is terminal, or you pay both costs forever.
• Value updates must not invalidate; structural changes must. Getting that backwards turns the optimization into a pessimization on write-heavy code.
• Ember's table cache is weaker than hidden classes, and saying which pattern it helps is more useful than claiming it is an inline cache.
• Storing an id rather than a handle keeps caches out of the GC's root set. A deliberate simplification that removes a leak class.
• A trace compiler does not need this at all. Two answers to one problem.

Validation / Self-check

1. What does a.semantic_score cost without a cache, for a table and for userdata?
2. Why is the cache at the site rather than in the object?
3. Name the three states, and say what must happen when a site reaches the third.
4. Give Ember's two notions of "shape" and why each was chosen for its case.
5. Which table operations bump the version and which must not? What breaks if you get the first row wrong?
6. Which pattern does Ember's table cache help, and which does it not? What is the upgrade?
7. Why is a cache allowed to be stale, and what property does that buy?
8. Why does Ember store a stable id rather than a GcRef in the cache?
9. Why does LuaJIT not need inline caches?

Next: Runtime Specialization.