6 ms·

I made Web49 because there are not many good tools for WebAssembly out there. WABT is close, but the interpreter is too slow and the tools megabytes in size eac

by 4984 4y ago

I made Web49 because there are not many good tools for WebAssembly out there. WABT is close, but the interpreter is too slow and the tools megabytes in size each. Wasm3 is a bit faster but only contains an interpreter, nothing else. Tooling for WebAssembly is held mostly by the browser vendors. It is such a nice format to work with when one removes all the fluff. WebAssembly tooling should not take seconds to do what should take milliseconds, and it should be able to be used as a library, not just a command line program. I developed a unique way to write interpreters based on threaded code jumps and basic block versioning when I made MiniVM (https://github.com/FastVM/minivm https://github.com/FastVM/minivm). It was both larger and more dynamic than WebAssembly. Web49 started as a way to compile WebAssembly to MiniVM, but soon pivoted into its own Interpreter and tooling. I could not be happier with it in its current form and am excited to see what else It can do, with more work.

haberman 4y ago
> I developed a unique way to write interpreters based on threaded code jumps and basic block versioning when I made MiniVM (https://github.com/FastVM/minivm https://github.com/FastVM/minivm). It was both larger and more dynamic than WebAssembly. I'd be very interested to read more about this. It looks like you are using "one big function" with computed goto (https://github.com/FastVM/Web49/blob/main/src/interp/interp.c#L573-L586 https://github.com/FastVM/Web49/blob/main/src/interp/interp....). My experience working on this problem led me to the same conclusion as Mike Pall, which is that compilers do not do well with this pattern (particularly when it comes to register allocation): http://lua-users.org/lists/lua-l/2011-02/msg00742.html http://lua-users.org/lists/lua-l/2011-02/msg00742.html I'm curious how you worked around the problem of poor register allocation in the compiler. I've come to the conclusion that tail calls are the best solution to this problem: https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
- naasking 4y ago
  > My experience working on this problem led me to the same conclusion as Mike Pall, which is that compilers do not do well with this pattern Note that that message is from twelve years ago. A lot's changed since then, not just in compilers but in CPUs. Branch prediction is a lot better now.
  - haberman 4y ago
    Mike's primary complaint is bad register allocation. It is very important to keep the most important state consistently in registers. In my experience, compilers still struggle to do good register allocation in big and branchy functions. Even perfect branch prediction cannot solve the problem of unnecessary spills.
    - 10000truths 4y ago
      Does providing a hint to the compiler using the register keyword address the issue sufficiently?
      - haberman 4y ago
        No, most compilers ignore the register keyword, see: https://stackoverflow.com/a/10675111 https://stackoverflow.com/a/10675111
      - JonChesterfield 4y ago
        Nearly. You need register and to also pass them into (potentially no-op) inline asm. `register int v("eax")` iirc, but it's been years since I did this. The 'register' is indeed largely ignored, but it has the additional somewhat documented meaning of 'when this variable goes into inline asm, it needs to be in that register'. In between asm blocks it can be elsewhere - stack or whatever - but it still gives the regalloc a really clear guide to work from.
        lifthrasiir 4y ago
        It's `register int v asm("eax")`. However they are very easily elided, especially after higher optimization levels; compilers are very open about this [1]. [1] https://gcc.gnu.org/onlinedocs/gcc/Local-Register-Variables.html#Local-Register-Variables https://gcc.gnu.org/onlinedocs/gcc/Local-Register-Variables....
        deleted 4y ago
        [deleted]
- wahern 4y ago
  > that compilers do not do well with this pattern As compared to hand-written assembly or the tailcall technique you describe. But (for the benefit of onlookers) a threaded switch, especially using (switch-like) computed gotos, is still more performant than a traditional function dispatch table. Has there been any movement in GCC wrt the tailcalls feature? One of the limitations with computed gotos is the inability to derive the address of a label from outside the function. You always end up with some amount of superfluous conditional code for selecting the address inside the function, or indexing through a table. Several years ago when exploring this space I discovered a hack, albeit it only works with GCC (IIRC), at least as of ~10 years ago. GCC supports inline function definitions, inline functions have visibility to goto labels (notwithstanding that you're not supposed to make use of them), and most surprisingly GCC also supports attaching __attribute__((constructor)) to inline function definitions. This means you can export a map of goto labels that can be used to initialize VM data structures, permitting (in theory) more efficient direct threading. The tailcall technique is a much more sane and profitable approach, of course.
  - JonChesterfield 4y ago
    The goto labels can exported much more directly using inline asm. Further, inline asm can now represent control flow, so you can define the labels in inline asm and the computed jump at the end of an opcode. That's pretty robust to compiler transforms. Just looked up an interpreter in that style: #define LABEL_START(TAG) ns_##TAG : __asm__(".p2align 3\n.Lstart_" #TAG ":" :::) #define LABEL_END(TAG) __asm__(".Lend_" #TAG ":\n") #define PROLOGUE(TAG) LABEL_START(TAG); ip++ #define EPILOGUE(TAG) __asm__ goto("\tjmpq %0\n" "\t.Lend_" #TAG ":\n"::"r"((void)decode(ip))::ALL_LABELS()) Followed by opcodes implemented in this fashion: { PROLOGUE(add); { apply_opcode_ADD(&s->data_stack); } EPILOGUE(add); } Because the labels are defined in assembly, not in C, accessing them from outside the function is straightforward. I wrote a whole load of these at some point, there's probably a version of those macros somewhere that compiles to jumps through a C computed goto as well.
deleted 4y ago
[deleted]

by 4984 4y ago

haberman 4y ago

> I developed a unique way to write interpreters based on threaded code jumps and basic block versioning when I made MiniVM (https://github.com/FastVM/minivm https://github.com/FastVM/minivm). It was both larger and more dynamic than WebAssembly. I'd be very interested to read more about this. It looks like you are using "one big function" with computed goto (https://github.com/FastVM/Web49/blob/main/src/interp/interp.c#L573-L586 https://github.com/FastVM/Web49/blob/main/src/interp/interp....). My experience working on this problem led me to the same conclusion as Mike Pall, which is that compilers do not do well with this pattern (particularly when it comes to register allocation): http://lua-users.org/lists/lua-l/2011-02/msg00742.html http://lua-users.org/lists/lua-l/2011-02/msg00742.html I'm curious how you worked around the problem of poor register allocation in the compiler. I've come to the conclusion that tail calls are the best solution to this problem: https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i...

naasking 4y ago
> My experience working on this problem led me to the same conclusion as Mike Pall, which is that compilers do not do well with this pattern Note that that message is from twelve years ago. A lot's changed since then, not just in compilers but in CPUs. Branch prediction is a lot better now.
- haberman 4y ago
  Mike's primary complaint is bad register allocation. It is very important to keep the most important state consistently in registers. In my experience, compilers still struggle to do good register allocation in big and branchy functions. Even perfect branch prediction cannot solve the problem of unnecessary spills.
  - 10000truths 4y ago
    Does providing a hint to the compiler using the register keyword address the issue sufficiently?
    - haberman 4y ago
      No, most compilers ignore the register keyword, see: https://stackoverflow.com/a/10675111 https://stackoverflow.com/a/10675111
    - JonChesterfield 4y ago
      Nearly. You need register and to also pass them into (potentially no-op) inline asm. `register int v("eax")` iirc, but it's been years since I did this. The 'register' is indeed largely ignored, but it has the additional somewhat documented meaning of 'when this variable goes into inline asm, it needs to be in that register'. In between asm blocks it can be elsewhere - stack or whatever - but it still gives the regalloc a really clear guide to work from.
      - lifthrasiir 4y ago
        It's `register int v asm("eax")`. However they are very easily elided, especially after higher optimization levels; compilers are very open about this [1]. [1] https://gcc.gnu.org/onlinedocs/gcc/Local-Register-Variables.html#Local-Register-Variables https://gcc.gnu.org/onlinedocs/gcc/Local-Register-Variables....
        deleted 4y ago
        [deleted]
wahern 4y ago
> that compilers do not do well with this pattern As compared to hand-written assembly or the tailcall technique you describe. But (for the benefit of onlookers) a threaded switch, especially using (switch-like) computed gotos, is still more performant than a traditional function dispatch table. Has there been any movement in GCC wrt the tailcalls feature? One of the limitations with computed gotos is the inability to derive the address of a label from outside the function. You always end up with some amount of superfluous conditional code for selecting the address inside the function, or indexing through a table. Several years ago when exploring this space I discovered a hack, albeit it only works with GCC (IIRC), at least as of ~10 years ago. GCC supports inline function definitions, inline functions have visibility to goto labels (notwithstanding that you're not supposed to make use of them), and most surprisingly GCC also supports attaching __attribute__((constructor)) to inline function definitions. This means you can export a map of goto labels that can be used to initialize VM data structures, permitting (in theory) more efficient direct threading. The tailcall technique is a much more sane and profitable approach, of course.
- JonChesterfield 4y ago
  The goto labels can exported much more directly using inline asm. Further, inline asm can now represent control flow, so you can define the labels in inline asm and the computed jump at the end of an opcode. That's pretty robust to compiler transforms. Just looked up an interpreter in that style: #define LABEL_START(TAG) ns_##TAG : __asm__(".p2align 3\n.Lstart_" #TAG ":" :::) #define LABEL_END(TAG) __asm__(".Lend_" #TAG ":\n") #define PROLOGUE(TAG) LABEL_START(TAG); ip++ #define EPILOGUE(TAG) __asm__ goto("\tjmpq %0\n" "\t.Lend_" #TAG ":\n"::"r"((void)decode(ip))::ALL_LABELS()) Followed by opcodes implemented in this fashion: { PROLOGUE(add); { apply_opcode_ADD(&s->data_stack); } EPILOGUE(add); } Because the labels are defined in assembly, not in C, accessing them from outside the function is straightforward. I wrote a whole load of these at some point, there's probably a version of those macros somewhere that compiles to jumps through a C computed goto as well.

deleted 4y ago

[deleted]