VMtypical

Stack VM vs Register VM

Register VMs execute fewer instructions; each instruction is larger and costs more to decode. The win is real, modest and workload-dependent, and the decision usually turns on who writes the code generator rather than on throughput.

The question

Which should I build — a stack VM or a register VM — and what actually differs?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

Two executable formats for the same program, differing in exactly one thing: where an instruction's operands are located. The stack form locates them by convention (top of stack); the register form locates them by encoding (operand fields). Everything else people attribute to the choice — speed, verifiability, generator complexity — follows from that single difference.

What this phase may assume or do

Either format is a legal target for the same source provided the emitted program preserves observable behavior. The formats impose different well-formedness preconditions on the generator: a stack machine requires equal stack depth at every control-flow merge and a balanced net effect per statement, while a register machine requires that no register be reused while its current value is live on any path. Neither precondition is checkable by the other's verifier.

Key points

The formats differ in exactly one thing — operand location — and every other difference is downstream of it.
Register VMs execute fewer instructions; the time win is smaller than the instruction win because each instruction is wider and costs more to decode.
The measured advantage is real, modest and workload-dependent; a specific percentage belongs to the experiment that produced it.
Stack machines are trivially generatable and cheaply verifiable, which is why public and sandboxed formats choose them.
Register machines preserve the dataflow graph, which is why formats expecting a JIT choose them.
The decision usually turns on who writes the code generators and whether the code is trusted, not on throughput.

The one real difference

Both machines fetch instructions from an array, both keep an instruction pointer, both push a frame on a call and pop it on return. The only structural difference is how an instruction finds its inputs. Every other contrast follows mechanically from that, and keeping this in mind stops the comparison from turning into a list of unrelated folk claims.

From "operands are implicit" you get: small instructions, a trivial generator, easy verification, and more instructions per unit of work. From "operands are encoded" you get: wide instructions, a generator that must allocate, harder verification, and fewer instructions per unit of work. That is the whole table, expanded below.

The same program, the two formats, honestly comparedtypical

Dimension	Stack VM	Register VM	Who pays
Instruction count	Higher — one instruction per operand move plus one per operation	Lower — one instruction can express a full three-address operation	The interpreter, once per execution. This is the register machine's main advantage.
Instruction size	Smallest possible — most opcodes have no operand fields at all	Larger — two or three operand fields per arithmetic instruction	The instruction fetcher and the instruction cache. Fewer, bigger instructions is not automatically less total code.
Decode cost	Minimal — often just the opcode	Higher — operand fields must be extracted and used to index the frame	Every executed instruction. This is why the time win is smaller than the instruction-count win.
Code generator complexity	Very low — a post-order walk with no decisions	Moderate — register assignment, liveness across branches, frame sizing	The compiler author, once, and every third party who targets the format.
Writing an optimizer for it	Hard — operands have no names, so dataflow must be reconstructed by abstract-interpreting stack effects	Easier — operands are named, so the format already looks like three-address IR	Anyone adding a JIT later. This is the strongest technical argument for registers.
Verifying untrusted codetypical	Easy — a linear pass tracking stack depth and types	Harder — definite assignment and liveness per register must be proved	The platform, on every load of untrusted code. This is why sandboxed formats are stack machines.
Frame memory	Usually smaller — a shallow operand area plus named locals	Usually larger — sized for maximum simultaneous liveness, allocated per call	The allocator, on every call. Rarely decisive, occasionally noticeable in deep recursion.

What the measurements actually support

typicalThese conclusions come from converting one interpreter and measuring the pair, which controls for everything but the format and generalizes poorly. Two VMs with different formats, different implementers and different tuning budgets cannot be compared this way at all — a benchmark showing Lua beating CPython is not evidence about registers versus stacks, because almost everything else differs too.

The defensible claim is directional: converting a stack interpreter to an equivalent register interpreter reduces the number of executed VM instructions substantially, and reduces running time by less than that, because the remaining instructions are wider and more expensive to decode. Studies that did this conversion on a single interpreter and measured both report exactly that pattern, with the time saving materially smaller than the instruction saving.

The claim that is not defensible is a number. The gap depends on the benchmark mix, on how well the original stack interpreter was tuned, on whether the host CPU predicts the interpreter's indirect branches well, and on how much of the program's time is spent in the interpreter loop at all rather than in library code. A workload that spends most of its time inside a regular-expression engine written in C will not notice either design.

Reliable: register bytecode executes fewer VM instructions for the same work.
Reliable: the time saving is smaller than the instruction saving, because of decode and fetch.
Not reliable: any specific percentage, carried from one VM to another.
Not reliable: "therefore register VMs are faster" as an unconditional statement — it depends on where the workload spends its time, and most real workloads are not pure interpreter loops.
Frequently decisive and rarely mentioned: who has to write code generators for the format.

Choose on the other axes

If the format is a public interface that other compilers will target, choose the stack machine: you are moving work off every producer and onto yourself, once. If the format will be verified before execution because the code is untrusted, choose the stack machine again, for the same reason WebAssembly did. If the format is private, executed far more often than it is generated, and likely to acquire a JIT, choose registers.

And note what does not decide it: elegance. Both designs are implemented by systems that run enormous amounts of production code, which is strong evidence that the dominant term is context and not the format. A team that argues about this for a week has almost certainly spent more than the difference is worth.

The mechanical rewrite between the two forms

Before

LOAD 0 ; a
LOAD 1 ; b
ADD
STORE 2 ; c

After

ADD 2 0 1   ; R[2] := R[0] + R[1]

Legal only when

Only if the stack sequence is balanced — it pushes exactly the operands the operator consumes and its net stack effect is the single stored result — and the destination slot is not read by any instruction between the loads and the store. Under those conditions the two sequences compute the same value into the same location with the same faults.

Illegal when

If anything between the loads and the store can observe or modify the operands: a call that could reassign a, an exception handler that reads c, or a debugger breakpoint whose contract says every intermediate is materialized. Fusing then removes states that something else was allowed to see, which is the same reasoning that limits [[peephole-optimization]] in a native backend.

How it works

The steps, in the order the compiler takes them.

Take the same three-address IR as the starting point, since both formats are reachable from it.
For a stack machine, emit a post-order walk: push each operand, then the operator, then store the result into a slot if the IR named a destination.
For a register machine, emit one instruction per IR instruction, mapping each virtual register to a frame register and reusing registers whose values are dead.
Count executed instructions on both for the same input to see the instruction-count difference directly; count bytes to see the encoding difference go the other way.
Verify the stack form with a linear depth-and-type pass; verify the register form with a definite-assignment and liveness analysis, and notice how much more machinery the second needs.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A team picks the register design for throughput, then finds that most of the program's time is in library calls and the interpreter loop was never the bottleneck — the extra generator complexity was bought for nothing.
A team picks the stack design for a format other compilers will target, then adds a JIT and discovers every optimization starts by reconstructing the dataflow the format threw away.
A benchmark comparing two unrelated VMs is cited as evidence about the format, and the resulting decision is uncorrelated with the reason it was made.
The register generator has a liveness bug that only appears when a value crosses a loop back edge, so the program is correct on straight-line tests and wrong in loops.
The stack generator leaves an unbalanced merge, so one branch of an if corrupts every subsequent expression and the failure is attributed to the expression rather than to the branch.

When it helps

Making the decision once, early, with the actual usage pattern in front of you: who generates it, who executes it, is the code trusted, and will there be a JIT.
Explaining an existing VM's disassembly — the format tells you immediately what its designers optimized for.
Interview conversations, where the useful answer is the conditional one and the weak answer is a ranking.

When it hurts

As a performance decision made in isolation. The format is rarely the largest term, and treating it as one produces confident, unmeasured choices.
When it delays the first working implementation. A stack VM you can build this week beats a register VM you are still designing next month, and the conversion is mechanical if it turns out to matter.

What it costs

Every one of these is paid by something.

The register format buys fewer dispatches and pays in decode work, generator complexity and harder verification — three costs against one benefit, which is why the choice is not obvious.
The stack format buys a trivially generatable, cheaply verifiable public interface and pays a permanent instruction-count tax on every execution.
Choosing either buys a decision and pays an opportunity cost: the conversion later is mechanical for straight-line code and genuinely hard for anything with a debugger, a profiler or serialized bytecode already in the field.
Optimizing the chosen format — superinstructions for the stack machine, wider operand forms for the register machine — buys throughput and pays in interpreter code size, which pushes against the instruction cache and can give the win back.

What else you could do

What a different compiler or language does instead, and when that is better.

Ship a stack format and build a register form at load time. The interface stays easy to produce and verify; the executed form is fast. This is effectively what a bytecode-to-IR front end in a JIT does — see [[jit-compilation]].
Skip the argument: use an existing VM. Targeting the JVM, .NET or WebAssembly gives you a mature implementation of one of these designs plus its tooling — [[webassembly]].
Neither format: a closure-compiling interpreter keeps the tree and removes the per-node type dispatch, which recovers a large part of the win with none of the format work — [[tree-walk-interpreter]].
Compile ahead of time and have no VM at all, which is the right answer whenever startup and portability are not constraints — [[aot-compilation]].

See it for yourself

The flag, dump or tool that shows you this directly.

Read the two disassemblies side by side: python -m dis for a stack machine and luac -l for a register machine, on the same three-line function.
Count instructions rather than reading them: CPython exposes sys.settrace at line granularity, and luac -l prints the whole instruction list, so a small script gives you real counts for a real function.
/compilers/vm reports stepsExecuted for our stack machine, which is the left-hand column of this comparison for any program you type.
For WebAssembly, wasm-objdump -x prints the section sizes, which shows the encoding side of the trade in bytes rather than in instructions.

Plausible wrong readings

Stated the way a confident engineer states them.

"Register VMs are 30% faster." Some measured conversion of some interpreter was, on some benchmark set. The direction transfers; the number does not.
"Stack VMs are simpler, therefore worse." They are simpler for the generator and the verifier, which is a feature when either of those is on someone else's critical path.
"Fewer instructions must mean less memory." Fewer, wider instructions can be more bytes in total, and instruction bytes compete for cache.
"The choice is permanent." The bytecode is internal unless you published it. If it is internal, you can change it — the cost is your tooling, not the world's.

Misconceptions

The claim, and what is actually true.

One of these designs is obsolete.

Both are used by systems that execute enormous amounts of production code, and the newest widely deployed bytecode format — WebAssembly — is a stack machine. The choice tracks purpose, not era.

The format determines how fast the language is.

For anything with a JIT, the interpreter format mostly determines startup behavior and how quickly the JIT can build IR from it. Steady-state speed is decided by the optimizing tier, not by the bytecode.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

A stack machine's instructions are tiny and there are more of them; a register machine's are bigger and there are fewer. Register machines usually run a bit faster, stack machines are much easier to generate code for and to check for safety. Both are used by major systems, which tells you the difference is smaller than the arguments about it.

practical

Ask four questions in order. Will other people's compilers target this format? Will you execute untrusted code and need to verify it? Is the bytecode generated once and executed many times, or the reverse? Is a JIT on the roadmap? Two yeses in the first pair point at a stack machine; two yeses in the second pair point at registers. If the answers are mixed, build the stack machine, because it is the one you can finish.

advanced

The comparison stops being interesting the moment a JIT exists, and starts being interesting again for a different reason. With a JIT, the steady-state code is native and the bytecode format only governs startup, the profiling instrumentation, and how much work the JIT does to build its IR. A stack format costs the JIT an abstract-interpretation pass to recover dataflow; a register format hands it over. That cost is paid per compilation rather than per execution, which is a much better place to pay it — and it is why the format debate in a tiered system is really a debate about compile latency, not about interpreter throughput.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalThe instruction-count advantage of register bytecode is consistent across the published conversions; the time advantage is smaller and varies with benchmark mix and host CPU. Neither statement is a specification, and both were established on interpreters without JITs — once a JIT dominates execution, the interpreter format matters mainly for how fast the JIT can consume it.

implementationCPython, the JVM, .NET IL and WebAssembly are stack machines at their current versions; Lua 5.x and Dalvik are register machines. Individual implementations diverge from their format inside the loop — CPython specializes hot instructions at runtime, and most JVMs stop interpreting hot code entirely — so the format tells you about the artifact, not about how the code eventually executes.

simplifiedOur AtlasLang VM implements only the stack side, so the register column of every comparison here is quoted from Lua and Dalvik rather than measured by us. Instruction counts for the stack side are real and reproducible at /compilers/vm.

If you were asked this in an interview

You are designing a bytecode that third-party compilers will target and that runs untrusted code. Stack or registers, and why?
Someone tells you register VMs are 30% faster. What do you ask them?
Your stack VM is getting a JIT. What does the format cost you now that it did not cost you before?

Connections

Computer Architectureinstruction-decode instruction-cache registers isa-vs-microarchitecture

Performancebenchmark-fallacies microbenchmark-vs-system

Domains that do not exist yet

Testing & Reliability Engineering — Designing a benchmark that isolates one variable, and knowing when a comparison has confounds
Almost every wrong belief about this comparison comes from a benchmark that varied the format and the implementer and the tuning budget at once. Which comparisons are valid is a methodology question owned there, and it decides whether any number in this lesson means anything.