Tailcall VM

[petrihakkinen]

Hi! Has there been any research on implementing the VM using tailcalls? Clang has had [clang::musttail] attribute for some time. A friend of mine who is into high speed (Forth) interpreters says he's getting a major speed up over computed gotos by using tailcalls. The theory is that a tailcall VM can keep important state (pc, data and return stacks in Forth's case) more likely in CPU registers because the calling convention enforces this. Of course a Forth interpreter is a much more primal beast, so I'm not sure if the same applies to Luau.

[zeux]

We've looked into this a little bit and it doesn't seem to work for complex code, because [IIRC] clang compiles functions that aren't leaf to have an actual stack frame. For Luau most opcodes have a metatable-based slow path or a type-based error paths, and so most functions would likely end up wasting time on this. Additionally, this is clang-specific and would require forking the VM code, whereas computed gotos are simple to support in parallel with portable switch-based code. OTOH all three modern compilers mostly succeed in keeping the 4-5 elements of our state in registers, so I'm surprised it's a problem for Forth VM.

[petrihakkinen]

Yeah, I can ask him some more details. If I recall correctly the speed difference was in the order of magnitude ~400 MIPS with computed goto, ~450 MIPS with tailcall, but I could be remembering it wrong. I was also thinking the more complex opcodes in Luau, and possibly having to support two very different VMs could be difficult.

[zeux]

Something I should note is that in a stack VM there's some opportunity to use the CPU registers to pass state around, eg pass the top of the stack to the function that is tailcalled which would make it land in a CPU register; this is where I could see having an advantage for a tailcall-based VM assuming the "persistent" state is small enough so that you can spend one extra register on this accumulator, but a register-based VM wouldn't enjoy this advantage because it's rare that an opcode can pass data into the next one directly like that.

[petrihakkinen]

btw. if you haven't seen this, here's a nice blog post about tailcalls which mention the problem with slow/fast paths etc.
https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html

[petrihakkinen]

I don't know if it makes a big different for tailcall vs. computed goto, but usually in high speed Forth interpreters the top of the data stack is always kept in a CPU register (I've written a couple myself too for 8-bit systems).