Stack vs Register

This is the biggest fork in the road in Section 3, and it produces ADR-002.

Both answers ship in systems used by billions of people. The JVM, CPython, .NET CIL, and WebAssembly are stack machines. Lua, Dalvik, V8's Ignition, SQLite's VDBE, and Erlang's BEAM are register machines. There is no correct answer, only a stated one — and the point of this chapter is that you can state yours.

Three concepts: the two machine models, the cost model, and the considerations that have nothing to do with speed.

Concept 1: The Two Machine Models

1. Concept

In a stack machine, operands are implicit: an instruction consumes the top N values of an operand stack and pushes its result. In a register machine, operands are explicit: each instruction names the slots it reads and the slot it writes.

   a = b + c

   STACK MACHINE (Ember, JVM, CPython, Wasm)     REGISTER MACHINE (Lua, Dalvik, Ignition)

     GET_LOCAL  1        ; push b                  ADD  0, 1, 2      ; R0 = R1 + R2
     GET_LOCAL  2        ; push c
     ADD                 ; pop 2, push 1
     SET_LOCAL  0        ; pop into a

     4 instructions, ~1 byte of operand each        1 instruction, 3 operand fields
     4 dispatches                                   1 dispatch

2. Problem

Both machines have to get b and c into the ALU and the result into a. The question is whether the instruction says where they are, or whether their position is implied by a convention.

3. Mental model

They use the same memory. A stack machine's operand stack and a register machine's register file are both just a Vec<Value> inside the frame. The difference is addressing: implied by stack discipline, or spelled out in the instruction.

That is the observation that dissolves most of the mystery. In fact Lua makes it explicit — Lua's "registers" are stack slots, and a function's register file is a window into the same value stack the C API pushes onto. A register VM is not a machine with registers; it is a stack machine whose instructions address the stack directly.

   Ember's frame                      Lua's frame
   ┌─────────────┐  base+0            ┌─────────────┐  R0
   │ local a     │  ← GET_LOCAL 0     │ local a     │  ← named directly: ADD 0, 1, 2
   ├─────────────┤  base+1            ├─────────────┤  R1
   │ local b     │                    │ local b     │
   ├─────────────┤                    ├─────────────┤  R2
   │ local c     │                    │ local c     │
   ├─────────────┤  ← "top"           ├─────────────┤  R3
   │ temporary   │  ← pushed/popped   │ temporary   │  ← allocated by the COMPILER
   │ temporary   │     by opcodes     │             │
   └─────────────┘                    └─────────────┘
     the top moves at RUN time          the top is known at COMPILE time

The last line is the real difference, and everything else follows from it.

4. Implementation

Ember is a stack machine, so the compiler's job is simple: compiling an expression leaves exactly one value on the stack, and that invariant composes.

#![allow(unused)]
fn main() {
fn compile_expr(&mut self, e: &Expr) -> Result<()> {   // net stack effect: ALWAYS +1
    match e {
        Expr::Int { value, .. } => self.emit(Op::LoadInt(*value as i32), e.span()),
        Expr::Binary { op, lhs, rhs, .. } => {
            self.compile_expr(lhs)?;     // +1
            self.compile_expr(rhs)?;     // +1
            self.emit(binop_code(*op), e.span());   // -2 +1
        }
        // ...
    }
    Ok(())
}
}

Post-order traversal of an expression tree is stack-machine code generation. There is nothing to allocate and nothing to plan. In a register machine the same function must also answer "which register does this result go in?", which means a register allocator, a free-register watermark, and a rule for when a register may be reused.

Lua's is about as simple as register allocation gets — freereg in lcode.c is a watermark that moves like a stack pointer — and it is still a chapter of code with its own invariants (rg -n 'freereg|luaK_reserveregs|luaK_exp2nextreg' lcode.c).

5. Alternatives

The accumulator hybrid is worth a moment: V8's Ignition has a register file and a distinguished accumulator, so ADD r1 means acc = acc + r1. This shortens the common case (chained expressions naturally flow through the accumulator) while keeping explicit addressing available. It is a real third answer, not a compromise.

6. Decision

ADR-002: Ember is a stack machine.

And then the decision that makes this honest: capstone project 1 ports the compiler and VM to a register machine and benchmarks both. You do not have to take anyone's word for the cost, including this book's.

7. Tradeoffs

Concept 2: The Cost Model

1–3. Concept, problem, mental model

A register machine executes fewer instructions; a stack machine executes cheaper instructions. Which wins is an empirical question about your workload, your dispatch technique, and your CPU's branch predictor — which is why it has been measured repeatedly and the answers differ.

Three quantities, and they pull against each other:

The dominant term for an interpreter is usually dispatch: the indirect branch at the top of the loop, which the CPU mispredicts often because the next opcode is data-dependent. Fewer instructions means fewer mispredictions, which is the register machine's real advantage — and it is exactly the advantage that computed goto and other dispatch techniques also attack, from the other side.

4. Implementation — measure it yourself

You cannot resolve this by reading, and you should not try. What you can do is instrument:

#![allow(unused)]
fn main() {
// In the VM's fetch position, behind a feature flag:
self.stats.instructions_executed += 1;
self.stats.by_opcode[op.discriminant()] += 1;
}

ember run --stats tests/golden/programs/fib25.ember

instructions executed: <your number>
top opcodes:
  GET_LOCAL   <n>   (<n>%)
  CALL        ...
  LT          ...
  JUMP_IF_FALSE ...
  ADD         ...

Then do the arithmetic by hand. For each GET_LOCAL/SET_LOCAL pair that feeds a binary operator, a register machine would have emitted nothing — the operand would have been addressed directly. Count how many of your executed instructions are pure operand shuffling. That fraction is the register machine's upper bound on your workload, and computing it costs you an afternoon instead of a rewrite.

Write the number in docs/learning/05-bytecode.md. When you do capstone project 1, you will find out how much of that upper bound is real.

5–7. Alternatives, decision, tradeoffs

The published measurements, and how to read them:

• Ierusalimschy, de Figueiredo & Celes, The Implementation of Lua 5.0 — Lua's own account of moving from a stack machine (5.0's predecessor) to a register machine, including their measured reduction in instruction count. This is the primary source and it is twelve pages. Read their numbers rather than a summary of them.
• Shi, Casey, Ertl & Gregg, Virtual Machine Showdown: Stack Versus Registers (VEE 2005; extended in ACM TACO 2008) — they built a translator from JVM stack bytecode to an equivalent register format and measured both under several dispatch techniques. The headline direction: substantially fewer executed instructions for the register machine, larger bytecode, and a real but workload-dependent net speedup. Get the paper for the actual figures; do not trust a remembered percentage, including this one.

Warning: Both papers measure their VM on their benchmarks with their dispatch technique. A number from either is a data point about that system, not a law. If you find yourself citing "register VMs are 30% faster" without naming the paper, the workload, and the dispatch method, you have turned a measurement into folklore. This is the same discipline Section 7 applies to your own optimizations.

8. Production concerns

• Operand width limits are tighter in a register machine. Lua packs A/B/C into 32 bits, so B and C are 8–9 bits, which is why Lua functions are limited to ~200 locals and constants beyond a small range need an extra instruction. Ember's 8-byte enum has no such pressure — which is a cost (memory) that buys a freedom (no operand-width special cases).
• A register machine's compiler bugs are worse. A stack machine's code generator either balances or it does not, and the validator catches it. A register allocator that reuses a live register produces code that runs and computes the wrong thing. That asymmetry is a real argument for the stack machine in a project where the compiler is new.
• Both models need the same limits. Neither gives you an instruction budget, a depth limit, or memory accounting. Those are VM-structure decisions, orthogonal to this one.

Concept 3: The Considerations That Are Not About Speed

1. Concept

Speed is the argument everyone has. The decisions that actually got made in the JVM and WebAssembly were about something else.

2. Problem

Both formats are designed to be shipped over a network and executed by a machine that did not compile them. That makes verification a hard requirement, not a nicety.

3. Mental model

If you must prove a program is well-formed before running it, you want the property you are proving to be easy to compute in one pass. Stack depth is. Register liveness is not.

4. Implementation

Ember's validator rule 9 — abstract-interpret the stack depth, check it never goes negative, check it agrees at every join, check it ends at zero — is a linear pass with a small amount of state, because at every instruction the depth is a single number that the instruction's documented stack effect updates deterministically.

   offs  op                  depth in   depth out
   0000  LOAD_INT 1                 0           1
   0002  JUMP_IF_FALSE 0008         1           0      ← both paths must agree at 0008
   0003  LOAD_INT 2                 0           1
   0005  JUMP 0009                  1           1
   0008  LOAD_INT 3                 0           1      ← arrives with depth 0. ✔ consistent
   0009  RETURN 1                   1           —      ← both predecessors have depth 1 ✔

The equivalent check for a register machine is "is every register I read definitely assigned on every path?" — a dataflow problem, not a counter.

5–7. Alternatives, decision, tradeoffs

That fourth row matters for Section 7. A JIT wants three-address code with explicit operands, so a stack-based front end pays a conversion pass. V8's Ignition is register-based partly because TurboFan wants it that way — the interpreter's format was chosen to serve the compiler behind it. When Ember reaches the JIT, you will write that conversion, and it is a good moment to reflect on this decision.

8. Production concerns

• WebAssembly went further than "stack machine": it has no raw jumps at all. Control flow is structured — block, loop, if, and br to a labelled depth — which makes validation and single-pass compilation dramatically easier and makes a whole class of malformed-control-flow attacks impossible to express. That is a third design axis, orthogonal to stack-versus-register, and it is the one Ember does not take (Ember has raw JUMP with validated targets).
• The JVM's verifier is a specification-level artifact, hundreds of pages, and it has had real soundness bugs. "Verifiable" is a spectrum, and the cheaper your property is to check, the fewer places the check can be wrong. One more argument for the counter over the dataflow analysis.

9. References

• The WebAssembly design rationale documents (WebAssembly/design, Rationale.md) on why a stack machine and why structured control flow. Short, and unusually candid about tradeoffs.
• The JVM Specification §4.10, "Verification of class Files" — both the type-checking and the older type-inference verifiers.
• The Implementation of Lua 5.0, §7, for the register machine's rationale from the people who switched.
• Dalvik's design talk (Bornstein, Google I/O 2008) — the register argument made for a memory-constrained ARM device.
• V8's Ignition design docs, for the accumulator hybrid and its relationship to TurboFan.

Things to Notice

• A register VM is a stack machine whose instructions address the stack directly. The memory is the same; the addressing is not.
• The difference that generates all the others is whether the top of the frame is known at compile time or moves at run time.
• Stack machines make code generation a post-order walk. That is not a small convenience; it is the entire register-allocation problem, absent.
• Verification, not speed, is why the JVM and Wasm are stack machines. If you only remember the dispatch-count argument, you have half the picture.
• A JIT wants register form. V8 chose its interpreter's format to suit the compiler behind it, which is a design move worth stealing when you have two layers.
• Do not cite a percentage you cannot source. Both papers exist; read them; measure your own.

Validation / Self-check

1. Compile a = b + c for both machines and count instructions, dispatches, and operand bytes.
2. In what sense do both machines use the same memory? What is the actual difference?
3. Why does a stack machine's code generator need no register allocator? Show it in the shape of compile_expr.
4. Name three stack machines and three register machines in production, with one sentence on why each chose what it did.
5. Which quantity does a register machine reduce, and which does it increase? Which usually dominates in an interpreter, and why?
6. Why is stack-depth verification a one-pass counter while the register equivalent is a dataflow analysis?
7. What is WebAssembly's third design axis, beyond stack-versus-register, and what does it buy?
8. Why is V8's Ignition register-based, given that CPython and the JVM are not?
9. State ADR-002's decision, its two strongest rejected arguments, and the experiment that will test it.

Next: Constant Pools and Encoding.