Recently, I came acrossthispost
about different styles of VM dispatch as I was searching for ways to improve myternaryproject. I had heard of tail-call interpretation, though my original source of inspiration took some
time for me to re-find. This post, however, gave an excellent breakdown about several different styles of
VM dispatch in Scala. I decided to implement these in Rust (including several variations more relevant to my project)
as a fun experiment, and benchmark them to measure how they differ. I’ll go over 2 versions – one, meant to
emulate Noel’s Scala, the other, meant to utilize Rust’s strengths with a more complicated and traditional
register machine.
Tail-call interpretation refers to the technique where some recursion can be turned into a jump during compilation,
removing the need to allocate a new stack frame.
It’s extremely useful for functional languages to keep stack sizes down, such as Scala, but most compilers tend to use it.
If you want to learn more, I highly recommend checking out Noel’s excellent article above. When compiling with high optimization,
Rust also performs this, and the unstable featureexplicit_tail_callslets us directly tell the compiler to
perform the optimization or error.
The simplest machine we can easily work with here is a stack machine with 5 instructions, represented in Rust as so:
Essentially identical to Noel’s Scala. Since this is a stack machine, theLit(literal) instruction pushes a value
on the stack; arithmetic instructions pop their operands, and push the resulting value back onto the stack.
As a control, switch dispatch makes the most sense. We simply create an array of bytecode, loop over it in amatchstatement,
and execute it.
Here we can see our entire logic – a large recursive function that calls itself for every instruction. Since we used thebecomekeyword, we know our recursion won’t lead to a stack overflow.
This is a nice and simple strategy! Nothing too complicated here.
We next do subroutine threading, where we replace the match statement. Instead of an enum,
we have to implement our instructions as a struct that can be called by implementing theFn()trait. This means we can call
a dynamic&dyn Fn(), regardless of the underlying struct.
Our bytecode now looks like this (some parts omitted for brevity):
I could, of course, remove the global variables and either include them as part of the bytecode data or pass them as variables.
One fairly easy technique would be to pass and return all necessary values from each function. This technique also benefits from
tail-call optimization, so we don’t need to worry about function passing overhead. Additionally, we could use plain functions
instead and add a slightly more complicated decode stage, but forthis part, I wanted to be as similar to the Scala as possible.
Next, Neal talked about indirect threading. This technique keeps the match statement, but we do not directly
return and loop through recursion. Rather, we useindirect recursion. This means operations
call the dispatch function, instead of returning and the function calling itself.
Theoretically, this results in one less function return and allows function calling overhead to be tail-call optimized
out. In Rust, this looks like this.
Here we utilize a return to return our final value as well. So far, I like this one the best,
partially because it avoids the more complex virtual dispatch I used for subroutine threading. This
is mostly a consequence of using Rust’sFn()traits in ways they aren’t really intended for, since
the feature that allows using them this way is still unstable.