Dispatch

Three concepts: the fetch-decode-execute loop, dispatch techniques, and where the instruction budget goes.

This is the loop every Ember program runs in. It executes more times than any other code you will write, which makes it the one place where a constant factor matters — and the one place where it is easiest to make an unmeasured change and believe you improved something.

Concept 1: Fetch, Decode, Execute

1. Concept

The VM's main loop does three things, forever: fetch the instruction at ip, decode it into an operation and operands, and execute it.

#![allow(unused)]
fn main() {
loop {
    self.budget.tick()?;                   // ← the sandbox lives here. Concept 3.
    let op = code[ip];                     // FETCH
    ip += 1;
    match op {                             // DECODE (free, for a typed enum) + EXECUTE
        Op::LoadConst(k) => self.push(constants[k as usize]),
        Op::GetLocal(s)  => self.push(self.stack[base + s as usize]),
        Op::Add          => self.binary_add()?,
        Op::Jump(t)      => ip = t as usize,
        Op::Return(n)    => if self.pop_frame(n)? { return Ok(()) },
        // ...
    }
}
}

2. Problem

The loop must be fast and correct, and those pull in opposite directions. Correct means every opcode checks its preconditions, propagates errors with spans, and keeps ip, the stack, and the frame stack consistent. Fast means doing as little as possible per instruction — ideally, the dispatch plus the work and nothing else.

3. Mental model

The loop is a software CPU. ip is the program counter, stack is the register file plus the operand area, and the match is the instruction decoder. Everything you know about how a CPU goes fast — branch prediction, cache locality, keeping hot state in registers — applies here, one level up.

4. Implementation

Ember's real loop, with the three details that matter:

#![allow(unused)]
fn main() {
pub fn run(&mut self) -> Result<()> {
    // (1) Hoist the hot state into LOCALS. `self.frames.last_mut().ip` is three
    //     indirections; a local is a register. This is the single largest
    //     mechanical speedup available in an interpreter loop, and it costs
    //     nothing but the discipline of syncing back on every exit path.
    let mut ip = self.frame().ip;
    let mut base = self.frame().base;
    let mut chunk = self.frame().proto.chunk.clone_ref();

    macro_rules! sync { () => { self.frame_mut().ip = ip; } }   // before ANY call that
                                                                // can observe self.frames
    loop {
        self.budget.tick()?;
        let op = chunk.code[ip];
        ip += 1;

        match op {
            Op::GetLocal(s) => { let v = self.stack[base + s as usize]; self.stack.push(v); }
            Op::Add => {
                // (2) Errors need the SPAN of the instruction, which lives in the
                //     parallel `lines` array at the ip we just consumed.
                sync!();
                let b = self.pop(); let a = self.pop();
                self.push(arith::add(a, b).map_err(|e| self.at(e, ip - 1))?);
            }
            Op::Call(argc, nres) => {
                sync!();                                   // (3) the callee will read our ip
                self.do_call(argc, nres, ip - 1)?;
                ip = self.frame().ip; base = self.frame().base;
                chunk = self.frame().proto.chunk.clone_ref();
            }
            Op::Return(n) => {
                if self.pop_frame(n)? { return Ok(()); }
                ip = self.frame().ip; base = self.frame().base;
                chunk = self.frame().proto.chunk.clone_ref();
            }
            // ...
        }
    }
}
}

The three details:

1. Hoisting ip, base, and the chunk into locals lets LLVM keep them in registers. Reading self.frames.last().unwrap().ip on every instruction is a bounds check plus two pointer dereferences, on the hottest path in the program. Measure this one in Section 7; it is usually the largest single win available and it requires no cleverness.
2. sync!() before anything that can observe the frame. The traceback builder reads frame.ip, so if a sync!() is missing, an error reports the last synced instruction — an error message that points at the wrong line, with no other symptom. Put sync!() in every arm that can fail or call, and add a debug assertion in the error constructor that frame.ip == ip.
3. Re-hoisting after Call and Return, because the current frame changed. Forgetting this is the classic "the VM executes the caller's next instruction inside the callee" bug.

Warning: Hoisting is a correctness hazard, not just an optimization. The rule is: any code that can read self.frames must see a synced ip. Write it down, and prefer a sync!() you did not need over one you forgot. Section 7 can prove which are unnecessary with a benchmark; a missing one produces wrong diagnostics forever.

5–7. Alternatives, decision, tradeoffs

Decision: start with A in Lab 11, move to B once the differential tests pass. Get it right, then get it fast, and have the tests that prove the change was behaviour-preserving. That ordering is the whole method.

Concept 2: Dispatch Techniques

1. Concept

Dispatch is the mechanism that gets from "the opcode is Add" to the code that adds. It is one indirect branch, executed once per instruction, and it is historically the dominant cost in an interpreter.

2. Problem

An indirect branch is hard for a CPU to predict, because the target depends on data — the next opcode. A mispredicted branch costs on the order of a dozen cycles, and if it happens on every instruction, dispatch dominates everything else you do.

3. Mental model

A switch-based loop has one indirect branch site, which the predictor sees taking every possible target. Threaded code replicates the dispatch into the tail of every handler, so each site sees only the successors that actually follow that opcode — and opcode successors are highly correlated (GET_LOCAL is usually followed by GET_LOCAL or an arithmetic op). More sites, better prediction per site.

   SWITCH DISPATCH                        THREADED / COMPUTED-GOTO DISPATCH

   loop:                                  op_add:    ...do the add...
     op = code[ip++]                                 goto *handlers[code[ip++]]
     switch (op) {          ← ONE         op_getlocal: ...do the load...
       case ADD: ...; break    indirect                goto *handlers[code[ip++]]
       case SUB: ...; break    branch     op_sub:    ...
     }                        for the                 goto *handlers[code[ip++]]
     goto loop                whole VM
                                          ← ONE indirect branch PER OPCODE

4. Implementation — and a real Rust limitation

Rust's match on a fieldless-discriminant enum compiles to a jump table, which is option A below. The techniques that beat it in C are not directly available in stable Rust, and this is worth knowing rather than discovering:

So Ember uses A, not because it is best in the abstract but because it is what the language offers portably and safely. Say that in your journal rather than pretending it was a free choice — "we picked the only safe portable option" is an honest and common engineering position.

5–7. Alternatives, decision, tradeoffs

Decision: match in a loop, and Section 7 measures D before considering anything exotic.

Two pieces of context that keep this from being a disappointment:

The gap has narrowed. The classic measurements showing large wins for threading (Ertl & Gregg, early 2000s) were taken on CPUs whose indirect-branch predictors were far weaker than today's. Modern predictors (ITTAGE-style, in Intel and AMD parts from roughly the mid-2010s onward) track long branch histories and predict a single dispatch site much better than their predecessors. Several interpreter authors have reported the switch-versus-threading gap shrinking substantially on recent hardware.

But do not take that on faith either — including from this book. If you want to know what dispatch costs your VM on your CPU, the measurement is:

# Total instructions retired and branch mispredictions, for one benchmark.
perf stat -e instructions,branches,branch-misses \
    ./target/release/ember run tests/golden/programs/fib25.ember

Divide branch-misses by your VM's executed-instruction count (from --stats). If it is a small fraction, dispatch is not your problem and threading would buy you nothing. That single ratio decides whether this entire topic is relevant to your workload, and it takes two minutes.

8. Production concerns

• Exhaustiveness is a feature. No _ => unreachable!() in the dispatch match. Adding an opcode must be a compile error in vm.rs, not a runtime panic in production.
• The match arms should stay small. A giant arm inlined into the loop bloats it and hurts instruction-cache behavior for every other opcode. Push cold, complex work (do_call, metamethod fallbacks, table rehash) into #[inline(never)] functions and keep the hot arms to a few lines. This is the interpreter version of "keep the hot path hot," and it is measurable.
• Do not put the budget check inside the arms. One check in the fetch position is complete; forty checks in forty arms is thirty-nine chances to miss one. See Concept 3.
• Panics in the loop are unacceptable. Every index into stack, constants, and code must be either validated in advance (the validator) or bounds-checked with an error. A panic in the dispatch loop is an aborted host process.

9. References

• Ertl & Gregg, The Structure and Performance of Efficient Interpreters (Journal of Instruction-Level Parallelism, 2003), and Optimizing Indirect Branch Prediction Accuracy in Virtual Machine Interpreters (PLDI 2003). The primary sources on dispatch cost — read them for method as much as for numbers, and note the hardware they used.
• CPython's Python/ceval.c, the USE_COMPUTED_GOTOS / DISPATCH() macros. Option B in production, with a #if fallback to option A for compilers that lack the extension.
• Lua's luaV_execute in lvm.c: a switch with a vmdispatch/vmcase macro layer that becomes computed goto when the compiler supports it. Read the macros at the top of the file first.
• The Rust become (explicit tail calls) RFC and tracking issue, for the state of option C.

Concept 3: Where the Budget Goes

1. Concept

The instruction budget is the sandbox's answer to while true do end. It is a counter, decremented once per instruction, that turns an unbounded execution into an ErrorKind::Limit.

2. Problem

A host embedding Ember will run scripts it did not write, on a request path, with a latency budget. "This script might not terminate" is not an acceptable property. Neither is "it terminates but takes four seconds."

3. Mental model

There is exactly one place in the VM where every unit of work passes: the fetch. Put the check there and the coverage is complete by construction — you do not have to audit anything, now or when you add an opcode.

Contrast with the tree walker, which had to put a tick on each loop's back-edge and on each call because it has no fetch. That is a real, under-appreciated thing bytecode gives you: a single choke point.

4. Implementation

#![allow(unused)]
fn main() {
#[inline(always)]
fn tick(&mut self) -> Result<()> {
    // A saturating decrement plus one predictable branch. When budgeting is
    // disabled, `remaining` is u64::MAX and the branch is never taken — which
    // the predictor learns immediately, so the disabled cost is ~free.
    if self.budget.remaining == 0 {
        return Err(self.limit_error("instruction budget exhausted"));
    }
    self.budget.remaining -= 1;
    Ok(())
}
}

Two refinements worth knowing about, both deferred to Section 5:

• Check every N instructions instead of every one. Decrement a counter and test only when it hits zero, refilling from the real budget. Costs precision (you may overrun by N−1) and buys a branch. Whether it is worth it is a Section 7 measurement.
• Charge non-uniformly. ADD is not CONCAT of two megabyte strings, and NEW_TABLE is not free. A budget that charges 1 per instruction under-counts allocation-heavy scripts. Section 5 pairs the instruction budget with a memory budget for exactly this reason, and that pairing — not a cleverer instruction charge — is the right fix.

5–8. Alternatives, decision, production concerns

Decision: A, deterministic and default-on in the Engine. B/C available to hosts as an additional backstop, never as the primary control.

Determinism decides it, again: the same script with the same inputs must fail at the same point on every machine, or you cannot reproduce a production failure locally. This is the third time that criterion has settled a design question in this curriculum (the recursion limit and table iteration order are the others), which is a sign it belongs in docs/architecture.md as a stated principle rather than being re-derived each time.

Production concerns:

• The budget does not cover host functions. A registered Rust function that sleeps for a minute is invisible to the counter. Section 5 addresses this by charging a configurable cost per host call and by documenting, loudly, that host-function cost is the host's responsibility. This is a real limit of what a sandbox can promise and it belongs in the threat model, not in a footnote.
• ErrorKind::Limit, never Runtime. The host distinguishes "the script has a bug" from "the script hit our wall". Declared in Lab 0 for this moment.
• A budget of zero must not be a budget of infinity. Off-by-one here means an unbounded script. Test --max-instructions 0 explicitly.

9. References

• Lua's lua_sethook with LUA_MASKCOUNT — Lua's mechanism for exactly this, implemented as a count-down hook checked in the VM loop. Read luaV_execute's luai_threadyield/hook handling.
• mlua's and rlua's documentation on instruction limits and how they surface hook errors to a Rust host — the same problem, solved at the binding layer.
• V8's TerminateExecution API, for how a production engine handles "stop this script now" from another thread, and what it guarantees (and does not) about where execution stops.

Things to Notice

• ip in a local is the biggest free win in an interpreter, and it is a correctness hazard (the sync rule) as much as an optimization.
• Rust cannot do computed goto. That is a real constraint, it is not a failure of your design, and the honest response is to measure branch-misses before assuming it matters.
• Interpreter dispatch folklore predates modern branch predictors. Numbers from 2003 describe 2003 hardware. Re-measure before you believe.
• The fetch position is the only complete place for a budget check, and it is a structural advantage of bytecode over tree walking that has nothing to do with speed.
• Determinism has now settled three design questions — the recursion limit, the budget mechanism, and table iteration order. When one criterion keeps deciding things, promote it to a written principle.
• A sandbox cannot bound what it cannot see. Host functions are outside the budget, and saying so is part of the design.

Validation / Self-check

1. Write the fetch-decode-execute loop from memory. Where does the budget check go, and why nowhere else?
2. Why is hoisting ip into a local a correctness hazard? What is the rule, and what is the symptom of breaking it?
3. What must be re-hoisted after CALL and RETURN, and what happens if you forget?
4. Name five dispatch techniques and say which are available in stable Rust. Why is computed goto not?
5. What single measurement tells you whether dispatch is worth optimizing in your VM? Give the command.
6. Why should hot match arms stay small, and where should complex work go?
7. Why is a wall-clock deadline rejected as the primary execution limit? Which other two decisions were settled by the same criterion?
8. What does the instruction budget not bound, and where must that be documented?

Next: Lab 9 — Bytecode and the Disassembler.