6 ms·

A stack-based WASM CPU for stack-based WASM bytecode will be slower than a traditional register based CPU for reasons that have been known at least since the 19

A stack-based WASM CPU for stack-based WASM bytecode will be slower than a traditional register based CPU for reasons that have been known at least since the 1970s-1980s, when stack-based CPUs for Smalltalk, Lisp, and C were tried. This didn't stop Sun from trying again in the 1990s to make stack based CPUs for the JVM (picoJava, UltraJava, ...). TL;DR: A WASM CPU will need a complicated stack cache to map stack positions to registers. This will involve more transistors, power, and latency than just letting compiler writers use the registers directly. One of the earliest important papers is from 1982: "Register Allocation for Free: The C Machine Stack Cache."[1] Lispers sometimes lament that current processors are 'C machines ill-suited to Lisp like the Symbolics Lisp processors of yore', but in reality, C is very much a stack language, too. A C compiler is soooooo much easier to write if you don't have to worry about register allocation, a hard problem. I like that WASM is stack-based because it makes compilers for WASM much easier to write. But it makes the WASM JIT compiler much more complicated to write. But it's better that top talent at Google, Mozilla, etc. does the WASM JIT compiler so that the rest of us can focus on solving other problems. The Lisp Machines of yore had instructions for tagged arithmetic, which can speed up, say, adding two dynamically typed variables. No need for a compiler to infer and enforce the datatypes of simple variables in advance, the processor checks the datatypes while it is executing the code and signals a type error if you try to add a float to a character. But modern JIT strategies, which can infer the datatypes of loop variables and emit native instructions lightning fast, might ultimately be better. [1] https://www.eecg.utoronto.ca/~jzhu/csc467/readings/ra-for-free.pdf https://www.eecg.utoronto.ca/~jzhu/csc467/readings/ra-for-fr...

jvanderbot 5y ago
Ah yes, I remember the embedded SoCs that started appearing in our coursework and labs that ran Java native. It just never seemed to be worth all the trouble to me. There are whole ecosystems that have to be supplanted, and for what? To help 'get into' a new domain?
aseipp 5y ago
I mean, you don't even have to go as far as register allocation to see the problems that make it all a big dead end. WebAssembly requires e.g. the call opcode parameter to actually be an index into the global function table, causing an indirection, which is about a trillion times worse than current CPUs which can just directly write the new PC to the register file at once. The spec is littered with stuff like this, for good reason. Considering WebAssembly is designed to be relatively easy to compile ahead of time, there's no reason to make the hardware worse when you could just ship "firmware" that compiles to an underlying ISA transparently, and reuse decades of existing knowledge. This would make the system behave more like the AS/400 and IBM iSeries, which abstracted away the underlying microarchitecture through its firmware.
- AstralStorm 5y ago
  Technically there are a few extra tricks you could pull off in microcode if you natively support the instruction set, that even a sufficiently smart JIT compiler cannot. It would be similar to what ARM tried with Jazelle way back when, with some very modest performance gain at best. Not worth the time.
- nneonneo 5y ago
  And, if you want to literally run the bytecode, there’s that little issue of nested blocks and block start/end tags…a proper WASM CPU would have to perform parsing in order to handle any form of control flow. (Alternatively, you could load not-quite-WASM that’s been gently preprocessed to use normal jumps, but at that point why not just go all the way and generate native code for a real CPU?)
dehrmann 5y ago
Is the compiler in a better position to allocate registers than the CPU? Considering it's a hard problem, but really only needs to be solved once, I can see how pushing that from the CPU to the compiler would help.
- AstralStorm 5y ago
  Very modestly. It's better to provide simple 4 bit "hotness" probability similar to what CPUs do on their own in branch prediction and cache allocation. Considering all the "blobby" multicore and SMT architecture, you could argue CPU has better information about registers. Just keep register format even and you'd be fine. Not too much to allocate when you have a lot of them and fast. The general hotness would especially help with reducing execution costs in JIT compilation, where new code is generated and CPU does not have accurate prediction data.
- ithkuil 5y ago
  A register based ISA implicitly conveys dependencies between instructions. This allows the CPU to infer which instructions can be executed in parallel (superscalar execution). Extracting instructions level parallelism (ILP) from a stack oriented is harder, but if a compiler can do it, technically a CPU could do the same. The question is: what would be the advantage? ILP extraction can be done statically. Doing it on a CPU at runtime would cost time and power. OTOH, stack based instruction sets tend to be more compact, so there is less pressure to the memory hierarchy to pull in the code, leaving more bandwidth for operands, and thus reducing stalls. CPU design is a tradeoff in a tradeoff in a tradeoff.
- astrange 5y ago
  It's better to think of the compiler allocating register names rather than registers. CPUs usually have far more physical registers which they allocate the ISA registers to, with some weird constraints, like some Intel CPUs have a penalty if you try to read a register that hasn't been written in a few hundred cycles. But that problem is simpler than allocating a stack to physical registers.
kazinator 5y ago
C is not a stack machine at all because (1) it has randomly accessed local variables with (2) the programmer expectation that these be mapped to registers as well as possible. C even used to have a register keyword; yet it never had any stack manipulation primitives (push, pop, ...).
- pjmlp 5y ago
  His point is not about what C abstract machine is, rather that there existed C implementations that used a stack machine as target. You can start with "A Book on C" for such implementation description, https://link.springer.com/book/10.1007/978-1-349-10233-4 https://link.springer.com/book/10.1007/978-1-349-10233-4
- ofubd8kc 5y ago
  From the programmer's perspective C is not a stack based language the way that, say, Forth is, because (as you note) there are no explicit push and pop instructions. But from an implementor's perspective, evaluating C function calls and arithmetic expressions is very stack oriented, which is why in the cited paper some Bell Labs researchers in the early 1980s were trying to build stack machine CPUs to execute C code. Given your Lisp experience, just think about how you'd translate various C expressions to Lisp ones, and how Lisp expressions map to stack operations, and you'll see C's stack based nature come out. (I.e. the abstract syntax trees (ASTs) a C compiler builds can naturally be represented as Lisp-like expressions.) C: y = a*x + foo(b); Lisp: (setq y (+ (* a x) (foo b))) Example stack instructions for the above (many variations possible): PUSH a PUSH x MUL PUSH b PUSH foo CALL ADD PUSH y SETQ ; or MOV or whatever your arch wants to call it Dennis Ritchie added the register storage qualifier keyword to primeval C (and also auto, inherited from B) to make the earliest C compilers easier to write, because bug-free register allocation is a very hard problem and Ritchie's earliest PDP had only a few kilobytes of core to hold both the C compiler's code and the chunk of program text being currently translated, so a complicated register allocator was out of the question.
  - gary_0 5y ago
    C is just implicit about how it pushes each function-local variable onto the stack. No amount of compiler optimization can hide it completely -- recurse too much or use up all the space, and you'll get a stack overflow. And just below C, all mainstream ABIs are designed around a stack too (with a designated stack pointer register, etc).
rbanffy 5y ago
> Lispers sometimes lament that current processors are 'C machines ill-suited to Lisp like the Symbolics Lisp processors of yore' Interestingly, SPARC was designed to run C code well. The register window idea allows cheaper function calls than other architectures where you need to push state to a stack prior to the jump.
- pjmlp 5y ago
  SPARC is also one of the very first C Machines, to the sense that SPARC ADI is the first widely deployed CPU architecture to protect against traditional C memory corruption bugs with help of tagged memory.
  - rbanffy 5y ago
    I think it’s a real shame SPARC is fading fast thanks to Oracle. The acquisition of Sun by them was a major tragedy of our industry.
    - pjmlp 5y ago
      SPARC ADI was designed by Oracle. I liked Sun, but lets not worship them more than they deserve. Just like had it not been for Oracle, anyone doing Java would be porting Java 6 code to whatever would be the hot replacements. And yes they care more about Oracle Linux than Solaris, just like all remaining UNIX vendors have switched to GNU/Linux as cost reduction on development costs.
      - rbanffy 5y ago
        I give you Sun’s management pre-acquisition was utterly stupid, but their hardware design teams, which continued under Oracle until being disbanded in 2017 or 2018, was nothing short of stellar.

jvanderbot 5y ago

Ah yes, I remember the embedded SoCs that started appearing in our coursework and labs that ran Java native. It just never seemed to be worth all the trouble to me. There are whole ecosystems that have to be supplanted, and for what? To help 'get into' a new domain?

aseipp 5y ago

I mean, you don't even have to go as far as register allocation to see the problems that make it all a big dead end. WebAssembly requires e.g. the call opcode parameter to actually be an index into the global function table, causing an indirection, which is about a trillion times worse than current CPUs which can just directly write the new PC to the register file at once. The spec is littered with stuff like this, for good reason. Considering WebAssembly is designed to be relatively easy to compile ahead of time, there's no reason to make the hardware worse when you could just ship "firmware" that compiles to an underlying ISA transparently, and reuse decades of existing knowledge. This would make the system behave more like the AS/400 and IBM iSeries, which abstracted away the underlying microarchitecture through its firmware.

AstralStorm 5y ago
Technically there are a few extra tricks you could pull off in microcode if you natively support the instruction set, that even a sufficiently smart JIT compiler cannot. It would be similar to what ARM tried with Jazelle way back when, with some very modest performance gain at best. Not worth the time.
nneonneo 5y ago
And, if you want to literally run the bytecode, there’s that little issue of nested blocks and block start/end tags…a proper WASM CPU would have to perform parsing in order to handle any form of control flow. (Alternatively, you could load not-quite-WASM that’s been gently preprocessed to use normal jumps, but at that point why not just go all the way and generate native code for a real CPU?)

dehrmann 5y ago

Is the compiler in a better position to allocate registers than the CPU? Considering it's a hard problem, but really only needs to be solved once, I can see how pushing that from the CPU to the compiler would help.

AstralStorm 5y ago
Very modestly. It's better to provide simple 4 bit "hotness" probability similar to what CPUs do on their own in branch prediction and cache allocation. Considering all the "blobby" multicore and SMT architecture, you could argue CPU has better information about registers. Just keep register format even and you'd be fine. Not too much to allocate when you have a lot of them and fast. The general hotness would especially help with reducing execution costs in JIT compilation, where new code is generated and CPU does not have accurate prediction data.
ithkuil 5y ago
A register based ISA implicitly conveys dependencies between instructions. This allows the CPU to infer which instructions can be executed in parallel (superscalar execution). Extracting instructions level parallelism (ILP) from a stack oriented is harder, but if a compiler can do it, technically a CPU could do the same. The question is: what would be the advantage? ILP extraction can be done statically. Doing it on a CPU at runtime would cost time and power. OTOH, stack based instruction sets tend to be more compact, so there is less pressure to the memory hierarchy to pull in the code, leaving more bandwidth for operands, and thus reducing stalls. CPU design is a tradeoff in a tradeoff in a tradeoff.
astrange 5y ago
It's better to think of the compiler allocating register names rather than registers. CPUs usually have far more physical registers which they allocate the ISA registers to, with some weird constraints, like some Intel CPUs have a penalty if you try to read a register that hasn't been written in a few hundred cycles. But that problem is simpler than allocating a stack to physical registers.

kazinator 5y ago

C is not a stack machine at all because (1) it has randomly accessed local variables with (2) the programmer expectation that these be mapped to registers as well as possible. C even used to have a register keyword; yet it never had any stack manipulation primitives (push, pop, ...).

pjmlp 5y ago
His point is not about what C abstract machine is, rather that there existed C implementations that used a stack machine as target. You can start with "A Book on C" for such implementation description, https://link.springer.com/book/10.1007/978-1-349-10233-4 https://link.springer.com/book/10.1007/978-1-349-10233-4
ofubd8kc 5y ago
From the programmer's perspective C is not a stack based language the way that, say, Forth is, because (as you note) there are no explicit push and pop instructions. But from an implementor's perspective, evaluating C function calls and arithmetic expressions is very stack oriented, which is why in the cited paper some Bell Labs researchers in the early 1980s were trying to build stack machine CPUs to execute C code. Given your Lisp experience, just think about how you'd translate various C expressions to Lisp ones, and how Lisp expressions map to stack operations, and you'll see C's stack based nature come out. (I.e. the abstract syntax trees (ASTs) a C compiler builds can naturally be represented as Lisp-like expressions.) C: y = a*x + foo(b); Lisp: (setq y (+ (* a x) (foo b))) Example stack instructions for the above (many variations possible): PUSH a PUSH x MUL PUSH b PUSH foo CALL ADD PUSH y SETQ ; or MOV or whatever your arch wants to call it Dennis Ritchie added the register storage qualifier keyword to primeval C (and also auto, inherited from B) to make the earliest C compilers easier to write, because bug-free register allocation is a very hard problem and Ritchie's earliest PDP had only a few kilobytes of core to hold both the C compiler's code and the chunk of program text being currently translated, so a complicated register allocator was out of the question.
- gary_0 5y ago
  C is just implicit about how it pushes each function-local variable onto the stack. No amount of compiler optimization can hide it completely -- recurse too much or use up all the space, and you'll get a stack overflow. And just below C, all mainstream ABIs are designed around a stack too (with a designated stack pointer register, etc).

rbanffy 5y ago

> Lispers sometimes lament that current processors are 'C machines ill-suited to Lisp like the Symbolics Lisp processors of yore' Interestingly, SPARC was designed to run C code well. The register window idea allows cheaper function calls than other architectures where you need to push state to a stack prior to the jump.

pjmlp 5y ago
SPARC is also one of the very first C Machines, to the sense that SPARC ADI is the first widely deployed CPU architecture to protect against traditional C memory corruption bugs with help of tagged memory.
- rbanffy 5y ago
  I think it’s a real shame SPARC is fading fast thanks to Oracle. The acquisition of Sun by them was a major tragedy of our industry.
  - pjmlp 5y ago
    SPARC ADI was designed by Oracle. I liked Sun, but lets not worship them more than they deserve. Just like had it not been for Oracle, anyone doing Java would be porting Java 6 code to whatever would be the hot replacements. And yes they care more about Oracle Linux than Solaris, just like all remaining UNIX vendors have switched to GNU/Linux as cost reduction on development costs.
    - rbanffy 5y ago
      I give you Sun’s management pre-acquisition was utterly stupid, but their hardware design teams, which continued under Oracle until being disbanded in 2017 or 2018, was nothing short of stellar.