4 ms·

> 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

> 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.

kragen 1y ago
Thank you! This is indeed very thought-provoking! It certainly does depend on which stack machine. I'm surprised that Wasm doesn't have a one-byte encoding for (local.get 0) or (local.set 0)! As you point out, even the JVM has one. My survey of bytecode instruction sets in https://dercuano.github.io/notes/tiny-interpreters-for-microcontrollers.html https://dercuano.github.io/notes/tiny-interpreters-for-micro... found such an 8-bit or 5-bit instruction in nearly every example except CPython, with a 3-to-5-bit operand field in the local.get and local.set instruction byte, but of course Wasm didn't exist in 02007. The JVM only offering 2 bits is atypically stingy. RVC and Thumb2 are pretty extreme cases of optimized register-machine encoding, and probably not something you'd want to decode in software on a 6502. The comparable stack-machine code would be something like Chuck Moore's x18/F18A with its four instructions per 18-bit word or James Bowman's J1A. It also depends, as you say, on the code. Most code is somewhere in between the extremes of x += y and your example of det = a*(e*i − f*h) − b*(d*i − f*g) + c*(d*h − e*g) with statements like these: dstRect.bottom := Max(dstRect.bottom,dstRect.top + txMinHeight); thePort^.grafProcs := Nil; { restore to normal } if (n != 0 && --n != 0) ... target_command = entry_i + CAM_CONTENT_COUNT * j; tfd = open(ptr, O_RDWR|O_TRUNC|O_EXCL|O_CREAT, 0600); for (size_t i = 1; i < n; i++) ... if (event == EV_enter_state) ... else if (event == EV_tick) ... else if (event == EV_reenter_state) ... Those are all taken from my examples in https://dernocua.github.io/notes/c-stack-bytecode.html https://dernocua.github.io/notes/c-stack-bytecode.html. There are a lot of subroutine calls, some reuse of the same value in multiple computations, many more variable reads than writes, and an occasional infix expression with more than one operator. These are all factors that favor stack instruction sets more than x += y does. Subroutine calls in particular are typically a single bytecode once all the operands are on the stack, referring to a subroutine name or address stashed elsewhere with a short literal index, which similarly is usually allocated a 3–5-bit field in the opcode byte. Very popular subroutines like car or #at:put: can get their own bytecode. There's a bit of a difference between the 8 registers in the PDP-11 or the 8086 and the 3-bit local variable field in an Emacs Lisp bytecode byte. The stack pointer soaks up one of those slots; on the PDP, the program counter soaks up another. (On ARM the link register sometimes is a third. Thumb and RVC do better here by excluding these registers from their 3-bit namespaces.) Analogously, one of the 8 local-variable indices in Elisp is "see next byte". Also, though, stack machines don't need to spend local variable indices on temporaries, and they often have instance-variable-access opcodes as well. So in effect register machines have less local variables than it at first appears. Incidentally, as that note mentions, Aztec C for the 6502 did support a bytecode interpreter to more than halve code size: > As an alternative, the pseudo-code C compiler, CCI, produces machine language for a theoretical machine with 8, 16 and 32 bit capabilities. This machine language is interpreted by an assembly language program that is about 3000 bytes in size. > The effects of using CCI are twofold. First, since one instruction can manipulate a 16 or 32 bit quantity, the size of the compiled program is generally more than fifty percent smaller than the same program compiled with C65 [the Aztec C native code compiler for the 6502]. However, interpreting the pseudo-code incurs an overhead which causes the execution speed to be anywhere from five to twenty times slower. But I don't know whether it was a stack bytecode, an accumulator bytecode, a register bytecode, or something weirder. My experience programming in FORTH is that often I can profitably keep about one variable on the operand stack, so accessing that variable takes no instructions and no bytes. In theory this is something that a compiler could do, but the only case I know of is when you store to a variable in Smalltalk inside a larger expression. Similarly it's common in FORTH to spend no instructions on accessing arguments or returning a value; you just don't drop it before returning.

kragen 1y ago

Thank you! This is indeed very thought-provoking! It certainly does depend on which stack machine. I'm surprised that Wasm doesn't have a one-byte encoding for (local.get 0) or (local.set 0)! As you point out, even the JVM has one. My survey of bytecode instruction sets in https://dercuano.github.io/notes/tiny-interpreters-for-microcontrollers.html https://dercuano.github.io/notes/tiny-interpreters-for-micro... found such an 8-bit or 5-bit instruction in nearly every example except CPython, with a 3-to-5-bit operand field in the local.get and local.set instruction byte, but of course Wasm didn't exist in 02007. The JVM only offering 2 bits is atypically stingy. RVC and Thumb2 are pretty extreme cases of optimized register-machine encoding, and probably not something you'd want to decode in software on a 6502. The comparable stack-machine code would be something like Chuck Moore's x18/F18A with its four instructions per 18-bit word or James Bowman's J1A. It also depends, as you say, on the code. Most code is somewhere in between the extremes of x += y and your example of det = a*(e*i − f*h) − b*(d*i − f*g) + c*(d*h − e*g) with statements like these: dstRect.bottom := Max(dstRect.bottom,dstRect.top + txMinHeight); thePort^.grafProcs := Nil; { restore to normal } if (n != 0 && --n != 0) ... target_command = entry_i + CAM_CONTENT_COUNT * j; tfd = open(ptr, O_RDWR|O_TRUNC|O_EXCL|O_CREAT, 0600); for (size_t i = 1; i < n; i++) ... if (event == EV_enter_state) ... else if (event == EV_tick) ... else if (event == EV_reenter_state) ... Those are all taken from my examples in https://dernocua.github.io/notes/c-stack-bytecode.html https://dernocua.github.io/notes/c-stack-bytecode.html. There are a lot of subroutine calls, some reuse of the same value in multiple computations, many more variable reads than writes, and an occasional infix expression with more than one operator. These are all factors that favor stack instruction sets more than x += y does. Subroutine calls in particular are typically a single bytecode once all the operands are on the stack, referring to a subroutine name or address stashed elsewhere with a short literal index, which similarly is usually allocated a 3–5-bit field in the opcode byte. Very popular subroutines like car or #at:put: can get their own bytecode. There's a bit of a difference between the 8 registers in the PDP-11 or the 8086 and the 3-bit local variable field in an Emacs Lisp bytecode byte. The stack pointer soaks up one of those slots; on the PDP, the program counter soaks up another. (On ARM the link register sometimes is a third. Thumb and RVC do better here by excluding these registers from their 3-bit namespaces.) Analogously, one of the 8 local-variable indices in Elisp is "see next byte". Also, though, stack machines don't need to spend local variable indices on temporaries, and they often have instance-variable-access opcodes as well. So in effect register machines have less local variables than it at first appears. Incidentally, as that note mentions, Aztec C for the 6502 did support a bytecode interpreter to more than halve code size: > As an alternative, the pseudo-code C compiler, CCI, produces machine language for a theoretical machine with 8, 16 and 32 bit capabilities. This machine language is interpreted by an assembly language program that is about 3000 bytes in size. > The effects of using CCI are twofold. First, since one instruction can manipulate a 16 or 32 bit quantity, the size of the compiled program is generally more than fifty percent smaller than the same program compiled with C65 [the Aztec C native code compiler for the 6502]. However, interpreting the pseudo-code incurs an overhead which causes the execution speed to be anywhere from five to twenty times slower. But I don't know whether it was a stack bytecode, an accumulator bytecode, a register bytecode, or something weirder. My experience programming in FORTH is that often I can profitably keep about one variable on the operand stack, so accessing that variable takes no instructions and no bytes. In theory this is something that a compiler could do, but the only case I know of is when you store to a variable in Smalltalk inside a larger expression. Similarly it's common in FORTH to spend no instructions on accessing arguments or returning a value; you just don't drop it before returning.