by brucehoult | 2025-09-07 23:19:15+00:00
> stack-based bytecode uses about twice as many instructions as register-based bytecode but significantly less space

That's not my experience, and I don't see how it can be true, even theoretically, for typical programs.

I don't at all mind more instructions, if that works out smaller or at least not bigger. E.g. RISC-V using `c.slli; c.srli` or `c.slli; c.srai` (all 2-byte opcodes) to extract unsigned or signed bitfields instead of having a 4-byte "extract field" instruction.

It is true that a stack-based ISA can have a size advantage in evaluating very complex expressions, such as those typical in scientific / engineering computing, when you get a lot of arithmetic operators in a row with no arguments needed.

But in general purpose programs the vast majority of lines of C code have only very simple expressions. `x=x+y`. `x=x+10`. `if x<y`.

Register ISAs provide short addressing for the most frequently-used 8 or 16 or 32 variables in a function (the registers). Experience shows 8 isn't really enough, 32 is usually a little more than you need -- I think some study showed 24 was enough but you don't get a code size advantage from that, so ...

Stack based ISAs do similarly. JVM can load or store any of four local variables within a 1-byte instruction. For more than than you can refer to 256 variables with a 2-byte instruction. Four really isn't enough, but 256 is a waste of code size. WASM doesn't have any option to include a variable number in the main opcode byte -- `local.get 1` is two bytes.

A very typical statement in programs is `x += y`.

JVM 4 bytes:

iload 0 // 1A iload 1 // 1B iadd // 60 istore 0 // 3B

If x and y aren't in the first 4 locals then it's 7 bytes

WASM 7 bytes:

(local.get 0) // 20 00 (local.get 1) // 20 01 (i32.add) // 6A (local.set 0) // 21 00

ARMv7 / ARMv6-M / ARMv4T 2 bytes:

add r0, r0, r1 // 08 44

RISC-V with C extension 2 bytes:

add a0, a0, a1 // 2E 95

The Arm example works with 16 local variables (only the most common operations MOV, ADD, and CMP can use all 16 registers, other operations can only use 8), the RISC-V example works with all 32 registers (again only C.MV, C.ADD, C.ADDI, C.SLLI work with all 32 registers, other 2-byte opcodes use only 8).

8086, M68k, PDP-11, Super-H, MSP430 can all also do this very common operation with a 2-byte instruction, with anything from 8 to 16 local variables.

Exactly the same analysis applies to `x += 10`.

Most programs consist almost entirely of statements like these, not things like `det = a(ei − fh) − b(di − fg) + c(dh − e*g)`

There are two main problems with stack code:

- you need four opcodes: `load`, `load`, `add`, `store`. Each opcode needs at minimum 3 or 4 bits, so no matter what you do you're going to have 12-16 bits to specify four actions. In contrast, the register machine can just use a single `add` opcode, again using 3 or 4 bits.

- all the common stack ISAs use a minimum of 8 bits for an instruction (even the extremely common `iadd` or `i32.add` and use a multiple of 8 bits for every instruction. Four instructions is going to be minimum 4 bytes.

- the register machine needs only one 3 or 4 bit opcode for `add` AND can pack the other operands arbitrarily into a 16-bit instruction, using whatever field size and position makes sense.

- the register machine needs to mention the dst/rs1 variable only once.

Stack machine code could be improved in size a little if you bit-packed the instructions, but you'll still have the problems of needing more opcode fields and needing to repeat variable names.

Perhaps ironically, some accumulator machines do better. For example the much-hated PIC microcontroller actually does this well:

MOVF 0x21, W ; Load y (from address 0x21) into W register ADDWF 0x20, F ; Add W (containing y) to x (at address 0x20), store result in x

Instructions such as ADDWF have a bit to specify whether to put the result of the add into W (the accumulator) or the source register.

On the smaller chips each of those instructions is 12 bits (with 32 registers, many with special purposes), though those are very limited and most applications use mid-range chips with 14 bit instructions (allowing 128 directly accessible registers).

So this is 24 or 28 bits of code, still not as compact as the 16 bits for that extensive list of register machines: RISC-V, Arm Thumb, 8086, M68k, PDP-11, Super-H, MSP430.