Lab 28: Inline Caches (Milestone 14)

Background

You will add monomorphic inline caches to field access — if your profile says to. If it says CALL or ADD dominates, do Lab 29 first and come back.

Why This Lab Matters

It is the first optimization with a real correctness hazard. A cache without invalidation produces wrong answers, not slow ones.
The mono/poly/megamorphic vocabulary transfers to every dynamic runtime you will ever read.
The protocol gets its first real test: if the measurement says no, you revert.

Prerequisites

Section 6 complete: baseline committed, profile taken, CI green.
Inline Caches read.

Predict First

What fraction of your policy benchmark's instructions are GET_FIELD? (You measured this.)
a.semantic_score where a is userdata — how many operations without a cache? With one?
t.x = 5 where x already exists. Should the cache be invalidated?
A loop over 10,000 different tables reading the same field. Does Ember's table cache help?
What is the speedup you expect on policy_10k? Write a number.

Step 1: The Hypothesis, Written First

<!-- docs/learning/14-performance.md -->
## Optimization: inline caches on GET_FIELD

BASELINE   policy_10k: <your number> ms
           GET_FIELD is 31.2% of executed instructions (opcode profile, Lab 27)

HYPOTHESIS GET_FIELD on userdata costs ~5 operations (metatable lookup, __index
           call, accessor table probe, accessor call, marshal). A monomorphic
           cache keyed on TypeId reduces it to ONE compare plus the accessor
           call. If GET_FIELD is 31% of instructions and we remove ~60% of its
           cost, policy_10k should improve by roughly 15-20%.

PREDICTION <your number> ms

Write the predicted number before measuring. A hypothesis you can be wrong about is what makes the measurement informative; without one, whatever you get looks like insight.

Step 2: The Cache Structure

#![allow(unused)]
fn main() {
#[derive(Copy, Clone)]
pub enum InlineCache {
    Uninit,
    Mono { shape: Shape, answer: CacheAnswer },
    Mega,                                        // TERMINAL
}

#[derive(Copy, Clone, PartialEq, Eq)]
pub enum Shape {
    UserData(TypeId),          // all instances of a type share a shape, by construction
    Table { id: u64, version: u32 },
}

pub struct Proto {
    // ...
    /// One per cached site. A SIDE array: Chunk stays immutable and shareable,
    /// which matters because Lab 22's bytecode cache may share Protos.
    pub caches: Vec<Cell<InlineCache>>,
}
}

#![allow(unused)]
fn main() {
Op::GetField(k) => {
    let recv = self.pop();
    let cache = self.current_caches()[cache_slot].get();
    let v = match (cache, self.shape_of(recv)) {
        (InlineCache::Mono { shape, answer }, Some(s)) if s == shape => {
            self.apply_cached(answer, recv)?          // ← THE FAST PATH
        }
        (InlineCache::Mega, _) => self.index_slow(recv, k)?,   // don't even try
        (_, shape) => {
            let (v, answer) = self.index_slow_recording(recv, k)?;
            self.update_cache(cache_slot, cache, shape, answer);
            v
        }
    };
    self.push(v);
}
}

Mega is terminal — a site that has seen too many shapes stops updating, or it pays the update cost forever and the lookup cost.

Step 3: Invalidation

#![allow(unused)]
fn main() {
impl Table {
    /// Bumped on STRUCTURAL change only. NOT on a value update to an existing
    /// key — that does not change where the value lives, and invalidating on it
    /// turns the optimization into a pessimization on write-heavy code.
    fn bump_version(&mut self) { self.version = self.version.wrapping_add(1); }
}
}

Operation	Bump?
`t.x = 5` where `x` exists	no
`t.y = 5` where `y` is new	yes
`t.x = nil`	yes
`setmetatable`	yes
rehash / array migration	yes

For userdata there is no invalidation at all — a type's accessor table is built once. That is the second reason userdata caching is the better bet.

Warning: Write the invalidation tests before the fast path. A cache that returns a stale answer is a wrong-answer bug, and it will only appear on the fifth read after a shape change — which no casual test will do.

Step 4: Measure

cargo bench -- --baseline v0.1

Fill in your numbers:

Benchmark	Before	After	Δ
`policy_10k`
`field_access`
`fib_25` (control — no field access)
`table_build` (write-heavy — watch for a regression)

Two controls, and both matter. fib_25 should not move at all; if it did, something else changed and your attribution is wrong. table_build is the pessimization check: if invalidation is too aggressive, write-heavy code gets slower and a single-benchmark measurement would not show it.

Step 5: Decide, and Record

Three possible outcomes, and all three are acceptable results:

MEASUREMENT  policy_10k: <before> → <after>  (<±%>)
             field_access: <±%>
             fib_25 (control): <±%>   ← must be ~0
             table_build: <±%>        ← must not regress

TRADEOFF     +140 lines; a Cell<InlineCache> per site (~8 bytes × sites);
             a version field on every Table (+4 bytes); an invalidation
             invariant that must be maintained forever.

DECISION     KEEP / REVERT

If the win is under ~5%, revert. 140 lines and a permanent invariant is not worth 3%, and the recorded revert stops you (or the next person) from trying it again in March.

The Trace

$ ember run --trace-ic --stats benches/policy.ember

--- inline cache report (policy.ember) ---
site      opcode      state          hits        misses   reason
0042      GET_FIELD   Mono           4,119,988      453    warm-up
0051      GET_FIELD   Mono           4,119,995      446    warm-up
0063      GET_INDEX   Mega                   0   205,027   >4 distinct table shapes
0071      GET_FIELD   Mono             409,602        1
...
hit rate: 96.8%   megamorphic sites: 1

Read site 0063. It went megamorphic because the loop indexes a different table on every iteration — exactly the pattern Ember's table cache does not help. The report told you that in one line, which is why --trace-ic is a deliverable and not a nicety.

And the correctness demonstration, which is more convincing than any test:

$ ember run --trace-ic -e '
local t = {x = 1}
local function read() return t.x end
read() read() read()           -- warms the cache: Mono
t.y = 2                        -- STRUCTURAL change: version bumps
return read()'

site 0007  GET_FIELD  Uninit → Mono{Table{id:3, version:0}}   (hit, hit)
table#3 version 0 → 1   (new key "y")
site 0007  MISS  cached version 0, actual 1  → re-cache Mono{version:1}
1

The miss is the guard working. Comment out bump_version on the new-key path and this returns 1 anyway (the slot happens not to have moved) — until a rehash moves it, and then it returns garbage. Try it: add enough keys to force a rehash and watch the uninvalidated cache return the wrong value. That five-minute experiment is worth more than the test.

Expected Output

$ cargo test --test inline_cache
test cache_hit_returns_the_same_value_as_the_slow_path ... ok
test structural_change_invalidates ... ok
test value_update_does_not_invalidate ... ok
test megamorphic_is_terminal ... ok
test caches_are_not_gc_roots ... ok

$ cargo test --test differential
test backends_agree_on_the_whole_corpus ... ok      ← the backstop

PREDICTION. What hit rate for each? What speedup?

RESULT. Record both. Then write the sentence for docs/limitations.md:

- Inline caches key on table IDENTITY, not on shape. They help repeated reads of
  the same table (config, modules, `self` in a loop) and not iteration over many
  distinct tables of the same shape. Hidden classes would fix the second case;
  see docs/adr/ADR-0NN.

Knowing which pattern your optimization helps is more valuable than the speedup, because it is what lets a user restructure their code.

Test

#![allow(unused)]
fn main() {
#[test]
fn cache_hit_returns_the_same_value_as_the_slow_path() {
    // Every cached read is checked against an uncached one. THE correctness test.
    let mut e = engine_with_userdata_and_tables();
    for _ in 0..100 {
        assert_eq!(e.eval::<f64>("return a.semantic_score").unwrap(),
                   e.eval_uncached::<f64>("return a.semantic_score").unwrap());
    }
}

#[test]
fn structural_change_invalidates() {
    assert_eq!(run("local t = {x = 1}
                    local function r() return t.x end
                    r() r() r()          -- warm
                    t.y = 2              -- structural
                    for i = 1, 40 do t['k'..i] = i end   -- force a REHASH
                    return r()"), "1");
}

#[test]
fn value_update_does_not_invalidate() {
    // The pessimization check: 100,000 value updates must not cause 100,000
    // cache misses.
    let stats = run_with_ic_stats("local t = {x = 1}
                                   for i = 1, 100000 do t.x = i local _ = t.x end");
    assert!(stats.ic_misses < 100, "value updates invalidated the cache: {} misses",
            stats.ic_misses);
}

#[test]
fn megamorphic_is_terminal() {
    let stats = run_with_ic_stats("local function r(t) return t.x end
                                   for i = 1, 1000 do r({x = i}) end");
    assert!(stats.ic_updates < 10, "a megamorphic site kept updating: {}", stats.ic_updates);
}

#[test]
fn caches_are_not_gc_roots() {
    with_gc_stress(|| {
        // A table read through a warm cache, then dropped, must be collectable.
        let mut e = Engine::new();
        e.execute("do local t = {x = 1} local function r() return t.x end r() r() end").unwrap();
        let before = e.heap_census().tables;
        e.collect();
        assert!(e.heap_census().tables < before, "a cache kept a table alive");
    });
}
}

Challenge Extensions

Polymorphic caches. Up to four entries, linear scan. Measure on a site that reads two shapes alternately — the case a monomorphic cache handles worst.
Hidden classes. Give tables a shape object shared by all tables with the same key set, with transitions on insert. This is V8's design and it fixes the "many tables, one read" case. It is a big project; scope it and write the ADR before starting.
Cache GET_GLOBAL. Globals are a table read on every access. A version counter on the globals table plus a per-site cache is the same mechanism. Measure: how much of a policy's time is global lookup?
Cache method calls. SELF_FIELD is GET_FIELD plus a dup; caching it caches method dispatch, which is the case object-oriented Lua code hits hardest.
Feed the cache to a JIT. Lab 30's compiled code can assume the cached shape and guard on it — which is exactly what V8's feedback vectors are for.

Deliverables

The hypothesis and predicted number written before measuring.
InlineCache with Uninit/Mono/Mega; Mega terminal; caches in a side array.
Shape::UserData(TypeId) and Shape::Table { id, version }.
Version bumped on structural changes only; the five-row table implemented and tested.
Invalidation tests written before the fast path.
Caches store a stable id, not a GcRef; the not-a-root test passes under --gc-stress.
--trace-ic reporting per-site state, hits, misses, and the miss reason.
The four-benchmark table including two controls.
The decision recorded — keep or revert — with the tradeoff.
The one-table/many-table experiment, and the resulting docs/limitations.md sentence.
Differential tests green.

Validation / Self-check

What did your hypothesis predict, and how wrong was it?
Which table operations invalidate and which must not? What is the symptom of getting the first row wrong?
Why is there no invalidation for userdata caches?
Why must Mega be terminal?
Why store a stable id rather than a GcRef? What does that buy the collector?
Which pattern does your cache help, and which does it not? What is the upgrade path?
Why are two controls needed rather than one?
If the win had been 3%, what would you have done, and why does recording that matter?

Next: Lab 29 — Specialized Opcodes.

Open-Source Engineer & Contributor

Lab 28: Inline Caches (Milestone 14)

Background

Why This Lab Matters

Prerequisites

Predict First

Step 1: The Hypothesis, Written First

Step 2: The Cache Structure

Step 3: Invalidation

Step 4: Measure

Step 5: Decide, and Record

The Trace

Expected Output

Debugging Steps

Wrong values after a table grows

Write-heavy code got slower

The hit rate is near zero

`--gc-stress` fails after adding caches

The differential test fails

`policy_10k` improved but `fib_25` also improved

Experiment

Test

Challenge Extensions

Deliverables

Validation / Self-check