Inline caches

Deep dive

How it works

Parts:

• site cache — per access site (bytecode operand or patched stub): up to k (shape, slot or target) entries plus a state
• shape id — object layout token compared at every access (shapes)
• generic lookup — shape dictionary and prototype chain, run only on a miss
• stub cache — global fixed-size table keyed by (shape, name) for megamorphic sites
• feedback reader — the optimizing JIT, which turns site states into guards

Operations:

1. Each access site (a bytecode operand or a patched code stub) owns a cache, initially empty.
2. Execute: load the object's shape id, compare against cached ids. Hit: load the cached slot (or call the cached target).
3. Miss: do the generic lookup (shape dictionary, prototype chain), then add (shape, slot) to the site.
4. State transitions: uninit -> mono -> poly as new shapes arrive; past the bound (4 in the code below) the site goes mega and stops growing.
5. Megamorphic sites use a global, fixed-size, hash-indexed stub cache keyed by (shape, name): a hash and compare per access, no per-site entries.
6. A lookup that went through the prototype chain must also be invalidated when a prototype changes (validity cell or prototype shape check).
7. The optimizing JIT reads the site's state as feedback. Mono or small poly: inline the shape check(s) and the load behind a guard. Mega: emit a generic access.
8. A failed guard deoptimizes to the interpreter, which runs the IC again and may widen it. Repeated failures make the JIT stop speculating at that site.

 o.x   shape(o) == S1 ? slot 0 :      per-site: [S1->0] [S2->2] ... (<=4)
                S2 ? slot 2 : miss    miss -> lookup -> add entry; >4 -> mega
                                      mega -> global (shape,name) hash table

Origin: Deutsch and Schiffman cached the receiver class and method at each send site in Smalltalk-80 (monomorphic). Hölzle, Chambers and Ungar (Self) let a site hold several entries: polymorphic inline caches.

Code

Property get with a per-site IC (mono, poly bounded to 4, mega), a global stub cache, and a check against the slow dictionary path.

use std::collections::HashMap;

type ShapeId = u32;
type Name = u32; // interned property name

/// Shape = hidden class: maps property name -> slot index.
struct Shape { slots: HashMap<Name, usize> }
struct Object { shape: ShapeId, slots: Vec<i64> }

struct Heap { shapes: Vec<Shape> }

impl Heap {
    /// Reference slow path: dictionary lookup in the shape.
    fn slow_get(&self, o: &Object, name: Name) -> Option<i64> {
        let slot = *self.shapes[o.shape as usize].slots.get(&name)?;
        Some(o.slots[slot])
    }
}

const POLY_MAX: usize = 4;
const STUB_SIZE: usize = 1024; // power of two

#[derive(Clone, Copy, PartialEq, Debug)]
enum Kind { Uninit, Mono, Poly, Mega }

/// Global stub cache for megamorphic sites: (shape, name) -> slot, direct-mapped.
struct StubCache { tab: [Option<(ShapeId, Name, usize)>; STUB_SIZE] }
impl StubCache {
    fn idx(s: ShapeId, n: Name) -> usize {
        ((s.wrapping_mul(0x9E37_79B1)) ^ n.wrapping_mul(0x85EB_CA6B)) as usize & (STUB_SIZE - 1)
    }
}

/// One cache per `obj.name` site in the bytecode.
struct Site { name: Name, entries: Vec<(ShapeId, usize)>, mega: bool }

impl Site {
    fn new(name: Name) -> Self { Site { name, entries: Vec::new(), mega: false } }
    fn kind(&self) -> Kind {
        if self.mega { Kind::Mega } else {
            match self.entries.len() { 0 => Kind::Uninit, 1 => Kind::Mono, _ => Kind::Poly }
        }
    }

    fn get(&mut self, heap: &Heap, stubs: &mut StubCache, o: &Object) -> Option<i64> {
        if !self.mega {
            // Fast path: compare the shape id, then load the slot. No hashing.
            for &(s, slot) in &self.entries {
                if s == o.shape { return Some(o.slots[slot]); }
            }
        } else {
            let i = StubCache::idx(o.shape, self.name);
            if let Some((s, n, slot)) = stubs.tab[i] {
                if s == o.shape && n == self.name { return Some(o.slots[slot]); }
            }
        }
        self.miss(heap, stubs, o)
    }

    #[cold]
    fn miss(&mut self, heap: &Heap, stubs: &mut StubCache, o: &Object) -> Option<i64> {
        let slot = *heap.shapes[o.shape as usize].slots.get(&self.name)?; // runtime lookup
        if !self.mega {
            if self.entries.len() < POLY_MAX {
                self.entries.push((o.shape, slot)); // uninit->mono->poly
            } else {
                self.entries.clear(); // fifth shape: give up on per-site cache
                self.mega = true;
            }
        }
        if self.mega {
            stubs.tab[StubCache::idx(o.shape, self.name)] = Some((o.shape, self.name, slot));
        }
        Some(o.slots[slot])
    }
}
fn main() {
    // 6 shapes; shape k has property 1 ("x") at slot k % 3, and shape 5 lacks it.
    let mut shapes = Vec::new();
    for k in 0..6u32 {
        let mut m = HashMap::new();
        if k != 5 { m.insert(1, (k % 3) as usize); }
        m.insert(2, 2);
        shapes.push(Shape { slots: m });
    }
    let heap = Heap { shapes };
    let obj = |s: u32| Object { shape: s, slots: vec![10 * s as i64, 20 * s as i64 + 1, 30 * s as i64 + 2] };
    let mut stubs = StubCache { tab: [None; STUB_SIZE] };
    let mut site = Site::new(1);
    assert_eq!(site.kind(), Kind::Uninit);
    let seq = [(0u32, Kind::Mono), (0, Kind::Mono), (1, Kind::Poly), (2, Kind::Poly),
        (3, Kind::Poly), (1, Kind::Poly), (4, Kind::Mega), (0, Kind::Mega), (5, Kind::Mega)];
    for (s, want) in seq {
        let o = obj(s);
        assert_eq!(site.get(&heap, &mut stubs, &o), heap.slow_get(&o, 1));
        assert_eq!(site.kind(), want);
    }
    assert_eq!(site.kind(), Kind::Mega); // mega is sticky
}

Compiled and run (stable Rust). Real engines patch machine code or keep the cache in a feedback vector, and drop entries when a shape is deprecated.

Complexity and constants

• Hit: one load of the shape id, one compare per cached entry, one slot load. Poly: linear scan of at most k entries (k about 4).
• Miss: the full lookup, order of a hash probe per shape or prototype hop, plus the cache update; amortized away when sites are stable.
• Memory: an entry is a shape id plus an offset or target, order of 8-16 bytes; one feedback vector per function.
• Megamorphic: one hash, one table load, two compares; a cache miss when the stub table is cold.
• Cost drivers: compares per hit, branch mispredictions when a poly site alternates, cache misses on the object header, code size when guards are inlined.

Efficiency

• Cost: a hit is a handful of instructions (load shape id, compare, load slot), L1-resident when the object is hot; a miss costs a dictionary or prototype-chain lookup. Bound: latency and branch prediction, not bandwidth. No measured figures here; they vary per engine.
• Levers:
  • keep sites monomorphic — skips the lookup entirely (Bynens) — build objects with the same property order, so they share one shape
  • inline the guard and load in optimized code — removes call and dispatch (Pizlo, JSC post) — hot mono or low-poly sites
  • bound polymorphism, add a global stub cache above the bound — caps scan length and code size — always
  • share the cache across objects of one shape — one miss warms every instance — constructors, class-like code
  • keep the cache inside the bytecode stream — no extra pointer chase (PEP 659) — interpreters
• Naive -> standard -> state of the art: hash lookup per access · full dictionary cost every time; per-site mono/poly IC · compare and load on a hit; IC feedback plus JIT-inlined guarded access with deopt on failure · the access can shrink to a guard and a load, and guards can be hoisted or folded.

Implementation notes

• Shape ids must be cheap to compare: a pointer or small integer, never a structural compare.
• Store the slot offset, not the property name; cache negative results and prototype hits as separate entry kinds.
• Adding or deleting a property or changing a prototype must invalidate dependent ICs: shape transitions plus validity cells or watchpoints.
• Put the miss path out of line (#[cold]); keep the hit path small enough to inline into the interpreter loop.
• Cheap to run: few entries, no allocation on hit, update only on miss. Count executions before caching so one-shot code never pays.

Pitfalls

• Assigning the same fields in different orders creates different shapes and makes sites polymorphic.
• Adding properties late, or delete, can push an object into dictionary mode, which defeats ICs.
• One megamorphic callee can make its callers' feedback useless.
• Deopt loops: speculate, fail, reoptimize with the same guess. Engines cap retries.
• Caching on the receiver's shape alone returns stale results after a prototype change.

Variants and alternatives

In production

• Browsers: V8 keeps a feedback vector per function with the four states, uses a global stub cache for megamorphic accesses, and TurboFan reads the feedback (blog); JavaScriptCore has structure-based ICs in Baseline code, which DFG and FTL consume (WebKit blog); SpiderMonkey records CacheIR stubs in Baseline and builds Warp code from them (docs).
• Python: CPython 3.11+ specializing adaptive interpreter rewrites bytecodes such as LOAD_ATTR to specialized forms with inline cache entries; failed guards fall back to the adaptive form (PEP 659).
• Ruby: YJIT guards on the receiver's class or shape in generated code, with side exits when they fail (3.2 notes).
• Smalltalk and Self virtual machines: the origin of monomorphic and polymorphic caches at send sites (see Sources).

Implementations

Sources

• L. Peter Deutsch, Allan M. Schiffman, Efficient Implementation of the Smalltalk-80 System, POPL 1984. paper
• Urs Hölzle, Craig Chambers, David Ungar, Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches, ECOOP 1991. paper
• Mark Shannon, PEP 659 - Specializing Adaptive Interpreter. pep
• Mathias Bynens, JavaScript engine fundamentals: Shapes and Inline Caches. article
• Filip Pizlo, Speculation in JavaScriptCore, WebKit blog. post