5 ms·

This is pretty exciting if real: > Bytecode/opcodes are translated into more efficient "operations" during a compilation pass, generating pages of meta-machine

This is pretty exciting if real: > Bytecode/opcodes are translated into more efficient "operations" during a compilation pass, generating pages of meta-machine code WASM compiled to a novel bytecode format aimed at efficient interpretation. > Commonly occurring sequences of operations can can also be optimized into a "fused" operation. Peephole optimizations producing fused opcodes, makes sense. > In M3/Wasm, the stack machine model is translated into a more direct and efficient "register file" approach WASM translated to register-based bytecode. That's awesome! > Since operations all have a standardized signature and arguments are tail-call passed through to the next, the M3 "virtual" machine registers end up mapping directly to real CPU registers. This is some black magic, if it works!

kevingadd 7y ago
IR getting converted into an interpreter-oriented bytecode is pretty common. Mono does it for its interpreter and IIRC, Spidermonkey has historically done that as well. I'm not sure if V8 has ever interpreted from an IR (maybe now?) but you could view their original 'baseline JIT' model as converting into an interpreter-focused IR, where the IR just happened to be extremely unoptimized x86 assembly. Translating the stack machine into registers was always a core part of the model but it's interesting to me that even interpreters are doing it. The necessity of doing coloring to assign registers efficiently is kind of unfortunate, I feel like the WASM compiler would have been the right place to do this offline.
- jashmatthews 7y ago
  > The necessity of doing coloring to assign registers efficiently is kind of unfortunate Register based VMs like Lua don't do this. The register allocation is incredibly simple https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/lj_parse.c#L370 https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/lj_parse.c#L3...
  - tom_mellior 7y ago
    But that's an allocator to virtual registers that don't try to correspond to (a valid number of) physical CPU registers. Sure it's easy to allocate to a large number of registers. It's harder to do it to a small number, like the project discussed here seems to claim to do.
    - jashmatthews 7y ago
      I could be completely wrong but it looks like what this does is more like stack-caching. One operand, if it's the result of the last instruction, should already be in "virtual r0" which is already in a register. For the other operand of the opcode, it's an infinite set of "registers" at an offset from the stack pointer: https://github.com/wasm3/wasm3/tree/b1462d450ca367e39e4b2eb414f1520f73dfb7ab/source#the-end-result https://github.com/wasm3/wasm3/tree/b1462d450ca367e39e4b2eb4...
      - tom_mellior 7y ago
        You're right. This doesn't use a register machine in the usual sense of the word. It's kind of the software analog to accumulator machines.
- saagarjha 7y ago
  > The necessity of doing coloring to assign registers efficiently is kind of unfortunate You don't have to do register allocation with coloring; it's just that most implementations do.
vnorilo 7y ago
Sure this is neat stuff, but I don't think any of it is novel. Bochs is a good source for some bytecode vm performance wizardry [1], even if the bytecode in question is the x86 ISA. Regardless, kudos to the authors and nice to see a fast wasm interpreter done well. 1: http://www.emulators.com/docs/nx25_nostradamus.htm http://www.emulators.com/docs/nx25_nostradamus.htm
- vshymanskyy 7y ago
  It's not only the "threaded code" approach, that makes Wasm3 so fast. In fact, Intel's WAMR also utilizes this method, yet is 30 times slower..
- saagarjha 7y ago
  Yeah, threaded interpretation is nothing new. Notably, Forth compilers have often used it; the iSH x86 emulator (https://github.com/tbodt/ish https://github.com/tbodt/ish) is a more recent example of this technique.
uasm 7y ago
> "WASM translated to register-based bytecode. That's awesome!" If the hardware executing this code is "stack-based" (or, does not offer enough general purpose registers to accomodate the funtion call) - this will need to be converted back to a stack-based function call (either at runtime, or beforehand). Wouldn't this intermediate WASM-to-register-based-bytecode translation be redundant then?
- tyingq 7y ago
  I don't know of any current physical stack machine CPUs.
  - uasm 7y ago
    Stacks are used extensively across the x86 family [0] [0] - https://en.wikipedia.org/wiki/X86_calling_conventions https://en.wikipedia.org/wiki/X86_calling_conventions
    - tyingq 7y ago
      "Has a stack" isn't the same as "Has a stack based ISA".
      - colejohnson66 7y ago
        To expand: a Forth machine or similar would be a stack based ISA. Using a stack is a different matters; Pretty much every ISA uses stacks.
    - jeltz 7y ago
      No, stack machine CPUs are pretty obscure things, especially today. See the link below for some examples. All or virtually all modern commercial CPUs are register based. https://en.wikipedia.org/wiki/Stack_machine#Commercial_stack_machines https://en.wikipedia.org/wiki/Stack_machine#Commercial_stack...
- AlEinstein 7y ago
  What proportion of machines running web assembly are stack-based, would you say? I would guess negligible.

kevingadd 7y ago

IR getting converted into an interpreter-oriented bytecode is pretty common. Mono does it for its interpreter and IIRC, Spidermonkey has historically done that as well. I'm not sure if V8 has ever interpreted from an IR (maybe now?) but you could view their original 'baseline JIT' model as converting into an interpreter-focused IR, where the IR just happened to be extremely unoptimized x86 assembly. Translating the stack machine into registers was always a core part of the model but it's interesting to me that even interpreters are doing it. The necessity of doing coloring to assign registers efficiently is kind of unfortunate, I feel like the WASM compiler would have been the right place to do this offline.

jashmatthews 7y ago
> The necessity of doing coloring to assign registers efficiently is kind of unfortunate Register based VMs like Lua don't do this. The register allocation is incredibly simple https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/lj_parse.c#L370 https://github.com/LuaJIT/LuaJIT/blob/v2.1/src/lj_parse.c#L3...
- tom_mellior 7y ago
  But that's an allocator to virtual registers that don't try to correspond to (a valid number of) physical CPU registers. Sure it's easy to allocate to a large number of registers. It's harder to do it to a small number, like the project discussed here seems to claim to do.
  - jashmatthews 7y ago
    I could be completely wrong but it looks like what this does is more like stack-caching. One operand, if it's the result of the last instruction, should already be in "virtual r0" which is already in a register. For the other operand of the opcode, it's an infinite set of "registers" at an offset from the stack pointer: https://github.com/wasm3/wasm3/tree/b1462d450ca367e39e4b2eb414f1520f73dfb7ab/source#the-end-result https://github.com/wasm3/wasm3/tree/b1462d450ca367e39e4b2eb4...
    - tom_mellior 7y ago
      You're right. This doesn't use a register machine in the usual sense of the word. It's kind of the software analog to accumulator machines.
saagarjha 7y ago
> The necessity of doing coloring to assign registers efficiently is kind of unfortunate You don't have to do register allocation with coloring; it's just that most implementations do.

vnorilo 7y ago

Sure this is neat stuff, but I don't think any of it is novel. Bochs is a good source for some bytecode vm performance wizardry [1], even if the bytecode in question is the x86 ISA. Regardless, kudos to the authors and nice to see a fast wasm interpreter done well. 1: http://www.emulators.com/docs/nx25_nostradamus.htm http://www.emulators.com/docs/nx25_nostradamus.htm

vshymanskyy 7y ago
It's not only the "threaded code" approach, that makes Wasm3 so fast. In fact, Intel's WAMR also utilizes this method, yet is 30 times slower..
saagarjha 7y ago
Yeah, threaded interpretation is nothing new. Notably, Forth compilers have often used it; the iSH x86 emulator (https://github.com/tbodt/ish https://github.com/tbodt/ish) is a more recent example of this technique.

uasm 7y ago

> "WASM translated to register-based bytecode. That's awesome!" If the hardware executing this code is "stack-based" (or, does not offer enough general purpose registers to accomodate the funtion call) - this will need to be converted back to a stack-based function call (either at runtime, or beforehand). Wouldn't this intermediate WASM-to-register-based-bytecode translation be redundant then?

tyingq 7y ago
I don't know of any current physical stack machine CPUs.
- uasm 7y ago
  Stacks are used extensively across the x86 family [0] [0] - https://en.wikipedia.org/wiki/X86_calling_conventions https://en.wikipedia.org/wiki/X86_calling_conventions
  - tyingq 7y ago
    "Has a stack" isn't the same as "Has a stack based ISA".
    - colejohnson66 7y ago
      To expand: a Forth machine or similar would be a stack based ISA. Using a stack is a different matters; Pretty much every ISA uses stacks.
  - jeltz 7y ago
    No, stack machine CPUs are pretty obscure things, especially today. See the link below for some examples. All or virtually all modern commercial CPUs are register based. https://en.wikipedia.org/wiki/Stack_machine#Commercial_stack_machines https://en.wikipedia.org/wiki/Stack_machine#Commercial_stack...
AlEinstein 7y ago
What proportion of machines running web assembly are stack-based, would you say? I would guess negligible.