Stack Machines vs. Register Machines TODO
Concept
A stack machine doesn't name its operands explicitly — it implicitly pops them off the top of the stack — which gives short instruction encodings and a simple compiler backend, but it needs more instructions to do the same computation and adds stack-shuffling operations like DUP and SWAP. A register machine names operands explicitly, so it needs fewer instructions and value reuse is explicit, which favors optimizations like register allocation and JIT compilation, at the cost of longer encodings and a more complex instruction set. The EVM is a stack machine that operates on 256-bit words with a stack depth capped at 1024, a design that prioritizes specification simplicity and deterministic reproducibility across every node over raw performance. WebAssembly's specification is also a stack-based validation model, but it provides function-local variables and structured control flow (blocks, loops, and branch labels), which makes it easy to compile AOT/JIT into native register code. So the real difference between the two VMs isn't stack versus register per se, but whether they prioritize verifiable, deterministic metering or native execution speed.
When you read EVM bytecode or fight over gas, stack-manipulation overhead shows up directly in the cost, and following discussions about alternative VMs requires knowing this trade-off as background. It's also what explains why compiler output looks the way it does.
Code & Formula
# 스택 머신 vs 레지스터 머신 — 같은 식 (a+b)*c 를 두 모델로 실행하고 명령 수를 비교한다.
def run_stack_machine(program):
stack = []
for op in program:
if isinstance(op, (int, float)):
stack.append(op)
elif op == "ADD":
b, a = stack.pop(), stack.pop()
stack.append(a + b)
elif op == "MUL":
b, a = stack.pop(), stack.pop()
stack.append(a * b)
return stack[-1]
def run_register_machine(program, regs):
regs = dict(regs)
for dest, op, *args in program:
if op == "ADD":
regs[dest] = regs[args[0]] + regs[args[1]]
elif op == "MUL":
regs[dest] = regs[args[0]] * regs[args[1]]
return regs
env = {"A": 3, "B": 4, "C": 5}
# (a+b)*c 를 스택 머신 명령으로: PUSH a, PUSH b, ADD, PUSH c, MUL (피연산자는 암묵적으로 스택 상단)
stack_program = [env["A"], env["B"], "ADD", env["C"], "MUL"]
# (a+b)*c 를 3-주소 레지스터 명령으로: r1 = A + B; r2 = r1 * C (피연산자를 이름으로 명시)
register_program = [("r1", "ADD", "A", "B"), ("r2", "MUL", "r1", "C")]
stack_result = run_stack_machine(stack_program)
register_result = run_register_machine(register_program, env)["r2"]
assert stack_result == register_result == (3 + 4) * 5
print(f"스택 머신 결과={stack_result}, 명령 수={len(stack_program)} "
f"(피연산자 암묵적 — EVM처럼 DUP/SWAP 같은 스택 정리 연산이 늘 수 있음)")
print(f"레지스터 머신 결과={register_result}, 명령 수={len(register_program)} "
f"(피연산자 명시 — 값 재사용이 이름으로 드러나 레지스터 할당·JIT에 유리)")
docs/code/algorithms/algorithms-25.py
Exercise
Pick a simple arithmetic expression, hand-translate it into both a stack-machine instruction sequence and a three-address register instruction sequence, then check what opcode sequence the same expression actually produces in solc's output bytecode.
Practical Connection
When optimizing a Solidity contract for gas, judging where stack-too-deep errors or unnecessary DUP/SWAP and memory round-trips come from requires exactly this understanding of the model difference.
Where it lands in Jayverse
- Verex: audit the CLOB matching loop for stack-machine overhead. Check for stack-too-deep errors and excess DUP/SWAP specifically in the hot matching and settlement path, since that's where this tradeoff turns into real gas cost.
- CI: add a gas-regression check on matching/settlement functions. Track compiled bytecode gas for those specific functions across commits, not just overall contract size.
- DeFi: minimize intermediate values in jayverse-defi's own math. For the from-scratch liquid-staking algorithms, prefer fewer live locals to reduce stack pressure, informed by this stack-vs-register model.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| operand | 연산 대상, 피연산자 · "A register machine names operands explicitly" |
| stack-shuffling | 스택 안에서 값을 이리저리 옮기는 작업 · "adds stack-shuffling operations like DUP and SWAP" |
| encoding (instruction) | 명령어를 표현·부호화하는 방식 · "short instruction encodings" |
| prioritize X over Y | Y보다 X를 우선시하다 · "over raw performance" |
| fight over gas | 가스비를 두고 다투다·고민하다 · "read EVM bytecode or fight over gas" |
| compile AOT/JIT into | ~로 사전 컴파일하거나 즉시 컴파일하다 · "compile AOT/JIT into native register code" |
| stack-too-deep | 스택이 너무 깊어져 나는 오류 · "stack-too-deep errors" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.