| 01 Aug 2026 | Jimmy Ostler | Word Count: 1636 | Reading Time: 9 Min |
Recently, I came across this post
about different styles of VM dispatch as I was searching for ways to improve my ternary
project. 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 feature explicit_tail_calls lets 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:
enum ByteCode {
Lit(f64),
Add,
Sub,
Mul,
Div
}Essentially identical to Noel's Scala. Since this is a stack machine, the Lit (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 a match statement,
and execute it.
NOTE: I decided to use some strange decisions to match up with the Scala.
These include the usage of `static mut` and `unsafe` as opposed to manually
creating closures, though I did that in a sense anyways. I do NOT endorse
writing Rust this way.const STACK_SIZE: usize = 32;
// Our stack
static mut STACK: &mut [f32] = &mut [0.0; STACK_SIZE];
// The list of instructions to execute
static mut INSTRS: &[Instr] = /* { [Lit(4.0), Lit(3.0)... etc] } */;
// We pass the stack pointer and instruction pointer to `dispatch`
pub fn dispatch(sp: usize, ip: usize) -> f32 {
unsafe {
if ip == INSTRS.len() {
STACK[sp - 1]
} else {
match INSTRS[ip] {
Instr::Lit(value) => {
STACK[sp] = value;
become dispatch(sp + 1, ip + 1)
},
Instr::Add => {
let a = STACK[sp - 2];
let b = STACK[sp - 1];
STACK[sp - 2] = a + b;
become dispatch(sp - 1, ip + 1)
},
Instr::Sub => {
let a = STACK[sp - 2];
let b = STACK[sp - 1];
STACK[sp - 2] = a - b;
become dispatch(sp - 1, ip + 1)
},
Instr::Mul => {
let a = STACK[sp - 2];
let b = STACK[sp - 1];
STACK[sp - 2] = a * b;
become dispatch(sp - 1, ip + 1)
},
Instr::Div => {
let a = STACK[sp - 2];
let b = STACK[sp - 1];
STACK[sp - 2] = a / b;
become dispatch(sp - 1, ip + 1)
},
}
}
}
}Here we can see our entire logic - a large recursive function that calls itself for every instruction. Since we used the
become keyword, 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 the
Fn() 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):
// Now, our instructions are `&dyn Fn()`, so we can use dynamic dispatch
// to call different instructions without knowing what they are.
static mut INSTRS: &[&dyn Fn() -> ()] = /*[&Lit, &Add... etc]*/;
static mut SP: usize = 0;
const STACK_SIZE: usize = 32;
static mut STACK: &mut [f32] = &mut [0.0; STACK_SIZE];
struct Lit(f32);
struct Add;
struct Sub;
struct Mul;
struct Div;
impl Fn<()> for Lit {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
STACK[SP] = self.0;
SP += 1;
}
}
}
impl Fn<()> for Add {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a + b;
SP -= 1;
}
}
}
impl Fn<()> for Sub {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a - b;
SP -= 1;
}
}
}
impl Fn<()> for Mul {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a * b;
SP -= 1;
}
}
}
impl Fn<()> for Div {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a * b;
SP -= 1;
}
}
}
pub fn dispatch(ip: usize) -> f32 {
unsafe {
if ip == INSTRS.len() {
STACK[SP - 1]
} else {
INSTRS[ip]();
become dispatch(ip + 1)
}
}
}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 for this 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 use indirect 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.
pub enum ByteCode {
Lit(f32),
Add,
Sub,
Mul,
Div
}
static INSTRS: &[ByteCode] = ...;
static mut SP: usize = 0;
static mut IP: usize = 0;
const STACK_SIZE: usize = 32;
static mut STACK: &mut [f32] = &mut [0.0; STACK_SIZE];
pub fn dispatch(instr: ByteCode) -> f32 {
match instr {
ByteCode::Lit(val) => lit(val),
ByteCode::Add => add(),
ByteCode::Sub => sub(),
ByteCode::Mul => mul(),
ByteCode::Div => div(),
}
}
fn lit(val: f32) -> f32 {
unsafe {
STACK[SP] = val;
SP += 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
dispatch(INSTRS[IP])
}
}
}
fn add() -> f32 {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a + b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
dispatch(INSTRS[IP])
}
}
}
fn sub() -> f32 {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a - b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
dispatch(INSTRS[IP])
}
}
}
fn mul() -> f32 {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP * 2] = a - b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
dispatch(INSTRS[IP])
}
}
}
fn div() -> f32 {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP * 2] = a / b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
dispatch(INSTRS[IP])
}
}
}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's Fn() traits in ways they aren't really intended for, since
the feature that allows using them this way is still unstable.
This leads to a final question. What if we combined the techniques? We dispatch from within operations,
but use an array of dyn Fn(). This means a few nice things: one function call per instruction and
no match statement. While it varies, this can be somewhat kinder to certain
aspects of some microarchitectures, as well as having the minimal number of function calls,
1 (this can vary depending on your VM architecture, but the important part is that each operation directly
calls the next).
This leads to direct dispatch. We return to objects as bytecode (for now) and let each operation dispatch the next. This results in what turns out to be the best performing variation on my machine. It looks somewhat like this
static mut INSTRS: &[&dyn Op] = ...;
static mut SP: usize = 0;
static mut IP: usize = 0;
const STACK_SIZE: usize = 32;
static mut STACK: &mut [f32] = &mut [0.0; STACK_SIZE];
pub trait Op: Fn() -> f32 {}
impl Op for Lit {}
impl Op for Sub {}
impl Op for Add {}
impl Op for Mul {}
impl Op for Div {}
struct Lit(f32);
struct Add;
struct Sub;
struct Mul;
struct Div;
impl Fn<()> for Lit {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
STACK[SP] = self.0;
SP += 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
INSTRS[IP]()
}
}
}
}
impl Fn<()> for Add {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a + b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
INSTRS[IP]()
}
}
}
}
impl Fn<()> for Sub {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a - b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
INSTRS[IP]()
}
}
}
}
impl Fn<()> for Mul {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a * b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
INSTRS[IP]()
}
}
}
}
impl Fn<()> for Div {
extern "rust-call" fn call(&self, _args: ()) -> Self::Output {
unsafe {
let a = STACK[SP - 1];
let b = STACK[SP - 2];
STACK[SP - 2] = a * b;
SP -= 1;
IP += 1;
if IP == INSTRS.len() {
STACK[SP - 1]
} else {
INSTRS[IP]()
}
}
}
}This technique lacks a distinct dispatch function at all, meaning to begin computation,
you simply call the instruction at the location of the instruction pointer. All of this
experimentation led to these results on my machine
test bench::direct ... bench: 24.59 ns/iter (+/- 0.50)
test bench::indirect ... bench: 55.32 ns/iter (+/- 1.21)
test bench::subroutine ... bench: 79.93 ns/iter (+/- 1.18)
test bench::switch ... bench: 59.39 ns/iter (+/- 2.16)Direct dispatch is the clear winner here, and that's not too shocking, since it fully utilizes the power of tail calling without doing as much as the other recursive techniques. Indirect seems to have about 2 times the overhead, meaning that the overhead of one extra function call is not necessarily minimal. We do need to be careful here though - these are very small numbers, and we should be wary about optimizations the compiler is making, especially since (in this case) it has full information about the instructions we intend to execute. Despite this, the numbers for these techniques seem to line up with what we would expect, and the relationship they have to each other seems to mirror this on modern hardware.
While these techniques, translated directly from Scala into somewhat unorthodox Rust, are pretty cool, they're not really the style that my ternary VM is supposed to be. For one, my VMs tend to act a lot more like actual hardware, since my goal is to simulate some supposed theoretical ternary hardware, which means a more complicated decoding step and registers. So, I created an extremely limited and small 16-bit register machine to be able to test it in conditions more similar to my eventual use case.
The machine is simple:
pub struct Machine {
regs: [u16; 16],
instrs: [Instr; 256],
ip: usize,
}
pub enum Op {
Halt = 0b0000,
Add = 0b0001,
Sub = 0b0010,
Mul = 0b0011,
Div = 0b0100,
Bgt = 0b0101,
Bleq = 0b0110,
}
Instruction Encoding:
12 8 4 0
┌─────┬────┬────┬────┐
│ IMM │ R1 │ RD │ OP │
└─────┴────┴────┴────┘
Not the most revolutionary thing in the world, but enough to test a simple register machine.
Switch dispatch is about what you would expect, except including a larger decode stage. Additionally,
we internalized the instruction pointer into the machine, avoiding the unfortunate static muts from the
last stage. We could have interred the instruction pointer into the run function as a recursive argument,
but in this case it's unlikely to matter (this is the approach I'm currently using in my ternary VM, though
more testing should probably be done before I finally settle).
pub fn run(machine: &mut Machine) {
loop {
let instr = machine.instrs[machine.ip];
let rd = instr.rd() as usize;
let r1 = instr.r1() as usize;
let rdv = machine.regs[rd];
let r1v = machine.regs[r1];
let imm = instr.imm();
machine.ip = match instr.op() {
Op::Halt => return,
Op::Add => {
machine.regs[rd] = rdv + (r1v + imm);
machine.ip + 1
},
Op::Sub => {
machine.regs[rd] = rdv - (r1v + imm);
machine.ip + 1
},
Op::Mul => {
machine.regs[rd] = rdv * (r1v + imm);
machine.ip + 1
},
Op::Div => {
machine.regs[rd] = rdv / (r1v + imm);
machine.ip + 1
},
Op::Bgt => {
if rdv > r1v {
imm as usize
} else {
machine.ip + 1
}
},
Op::Bleq => {
if rdv <= r1v {
imm as usize
} else {
machine.ip + 1
}
},
};
}
}This keeps things quite simple, and is quite reasonable as a small prototype. We'll see, however, that it doesn't measure up performance wise.
We now can avoid using any manual closures, since we're directly embracing the decoding step. We now use a static array of handlers instead:
type Handler = fn(&mut Machine, instr: Instr) -> usize;
static HANDLERS: [Handler; 7] = [
halt, // Halt = 0b0000,
add, // Add = 0b0001,
sub, // Sub = 0b0010,
mul, // Mul = 0b0011,
div, // Div = 0b0100,
bgt, // Bgt = 0b0101,
blq, // Bleq = 0b0110,
];
#[inline(always)]
fn decode(instr: Instr) -> (usize, u16, u16, u16) {
let rd = instr.rd() as usize;
let r1 = instr.r1() as usize;
let imm = instr.imm();
let r1v = machine.regs[r1];
let rdv = machine.regs[rd];
(rd, imm, r1v, rdv)
}
fn add(machine: &mut Machine, instr: Instr) -> usize {
let (rd, imm, r1v, rdv) = decode(instr);
machine.regs[rd] = rdv.wrapping_add(r1v.wrapping_add(imm));
machine.ip + 1
}
fn sub(machine: &mut Machine, instr: Instr) -> usize {
let (rd, imm, r1v, rdv) = decode(instr);
machine.regs[rd] = rdv.wrapping_sub(r1v.wrapping_add(imm));
machine.ip + 1
}
fn mul(machine: &mut Machine, instr: Instr) -> usize {
let (rd, imm, r1v, rdv) = decode(instr);
machine.regs[rd] = rdv.wrapping_mul(r1v.wrapping_add(imm));
machine.ip + 1
}
fn div(machine: &mut Machine, instr: Instr) -> usize {
let (rd, imm, r1v, rdv) = decode(instr);
machine.regs[rd] = rdv.wrapping_div(r1v.wrapping_add(imm));
machine.ip + 1
}
fn bgt(machine: &mut Machine, instr: Instr) -> usize {
let (rd, imm, r1v, rdv) = decode(instr);
if rdv > r1v {
imm as usize
} else {
machine.ip + 1
}
}
fn blq(machine: &mut Machine, instr: Instr) -> usize {
let (rd, imm, r1v, rdv) = decode(instr);
if rdv <= r1v {
imm as usize
} else {
machine.ip + 1
}
}
fn halt(_machine: &mut Machine, _instr: Instr) -> usize {
return 0;
}
pub fn dispatch(machine: &mut Machine) {
let instr = machine.instrs[machine.ip];
if let Op::Halt = instr.op() {
return;
}
machine.ip = HANDLERS[instr.op() as usize](machine, instr);
become dispatch(machine);
}This is just one way of doing it. The halting is somewhat redundant since we never actually call a halt
handler, but this is simply a minor implementation detail. More complicated control flow can actually
be extremely easy later tail-call technique, including traditionally difficult forms, as we'll see in
indirect and direct, as well as later.
fn add(machine: &mut Machine, instr: Instr) {
let (rd, imm, r1v, rdv) = decode(instr);
machine.regs[rd] = rdv.wrapping_add(r1v.wrapping_add(imm));
machine.ip += 1;
let instr = machine.instrs[machine.ip];
become dispatch(machine, instr);
}
fn sub(machine: &mut Machine, instr: Instr) {
let (rd, imm, r1v, rdv) = decode(instr);
machine.regs[rd] = rdv.wrapping_sub(r1v.wrapping_add(imm));
machine.ip += 1;
let instr = machine.instrs[machine.ip];
become dispatch(machine, instr);
}
fn mul(machine: &mut Machine, instr: Instr) {
let (rd, imm, r1v, rdv) = decode(instr);
machine.regs[rd] = rdv.wrapping_mul(r1v.wrapping_add(imm));
machine.ip += 1;
let instr = machine.instrs[machine.ip];
become dispatch(machine, instr);
}
fn div(machine: &mut Machine, instr: Instr) {
let (rd, imm, r1v, rdv) = decode(instr);
machine.regs[rd] = rdv.wrapping_div(r1v.wrapping_add(imm));
machine.ip += 1;
let instr = machine.instrs[machine.ip];
become dispatch(machine, instr);
}
fn bgt(machine: &mut Machine, instr: Instr) {
let (rd, imm, r1v, rdv) = decode(instr);
if rdv > r1v { machine.ip = imm as usize } else { machine.ip += 1 }
let instr = machine.instrs[machine.ip];
become dispatch(machine, instr);
}
fn blq(machine: &mut Machine, instr: Instr) {
let (rd, imm, r1v, rdv) = decode(instr);
if rdv <= r1v { machine.ip = imm as usize } else { machine.ip += 1 }
let instr = machine.instrs[machine.ip];
become dispatch(machine, instr);
}
fn hlt(_machine: &mut Machine, _instr: Instr) {
return;
}
fn dispatch(machine: &mut Machine, instr: Instr) {
match instr.op() {
Op::Halt => become hlt(machine, instr),
Op::Add => become add(machine, instr),
Op::Sub => become sub(machine, instr),
Op::Mul => become mul(machine, instr),
Op::Div => become div(machine, instr),
Op::Bgt => become bgt(machine, instr),
Op::Bleq => become blq(machine, instr),
}
}We remove the HANDLERS static, and instead use a dispatch function to tail-call our instructions. Additionally,
our instructions tail-call dispatch, giving us our event loop. And if we halt, we can simply return, ending our
loop and leaving our machine in its final state, to either continue computing by dispatching again, or stop.
Lastly, we can get direct by combining the two strategies.
type Handler = fn(&mut Machine, instr: Instr);
static HANDLERS: [Handler; 8] = [
halt, // Halt = 0b0000,
add, // Add = 0b0001,
sub, // Sub = 0b0010,
mul, // Mul = 0b0011,
div, // Div = 0b0100,
bgt, // Bgt = 0b0101,
blq, // Bleq = 0b0110,
];
fn add(machine: &mut Machine, instr: Instr) {
let (rd, imm, r1v, rdv) = decode(instr);
machine.regs[rd] = rdv.wrapping_add(r1v.wrapping_add(imm));
machine.ip += 1;
let instr = machine.instrs[machine.ip];
become HANDLERS[instr.op() as usize](machine, instr)
}
fn sub(machine: &mut Machine, instr: Instr) {
let (rd, imm, r1v, rdv) = decode(instr);
machine.regs[rd] = rdv.wrapping_sub(r1v.wrapping_add(imm));
machine.ip += 1;
let instr = machine.instrs[machine.ip];
become HANDLERS[instr.op() as usize](machine, instr)
}
fn mul(machine: &mut Machine, instr: Instr) {
let (rd, imm, r1v, rdv) = decode(instr);
machine.regs[rd] = rdv.wrapping_mul(r1v.wrapping_add(imm));
machine.ip += 1;
let instr = machine.instrs[machine.ip];
become HANDLERS[instr.op() as usize](machine, instr)
}
fn div(machine: &mut Machine, instr: Instr) {
let (rd, imm, r1v, rdv) = decode(instr);
let val = rdv
.div_euclid(r1v.wrapping_add(imm));
let instr = machine.instrs[machine.ip];
become HANDLERS[instr.op() as usize](machine, instr)
}
fn bgt(machine: &mut Machine, instr: Instr) {
let (rd, imm, r1v, rdv) = decode(instr);
let instr = machine.instrs[machine.ip];
become HANDLERS[instr.op() as usize](machine, instr)
}
fn blq(machine: &mut Machine, instr: Instr) {
let (rd, imm, r1v, rdv) = decode(instr);
let instr = machine.instrs[machine.ip];
become HANDLERS[instr.op() as usize](machine, instr)
}
fn halt(_machine: &mut Machine, _instr: Instr) {
return;
}This gives us quite the nice result. Benchmarks tend to agree.
test bench::direct_machine ... bench: 62.87 ns/iter (+/- 1.32)
test bench::indirect_machine ... bench: 115.00 ns/iter (+/- 0.96)
test bench::subroutine_machine ... bench: 183.29 ns/iter (+/- 12.05)
test bench::switch_machine ... bench: 96.35 ns/iter (+/- 2.20)I used a different program to test the branching ability in this version, so while we can't compare this to the stack machine (future post?), we can compare them to each other, and direct wins quite handily. Interestingly, switch is now beating indirect. While I'm not sure why this is now the case, I suspect it could be because of our new branch instructions, or perhaps the different program. Questions to explore in a different post! There's just one more thing about this technique that I wanted to mention.
I found Noel's article while I was searching for another thing I had stumbled upon. Eventually, I found it.
This architecture used for the wasm3 virtual machine
talked about some of the benefits of this. Each code block can call its own dispatch function,
and when using a stack machine, this means the lexical scope aligns exactly with the actual scope! This
is very nice, and we can use this to trivially implement certain kinds of control flow, including exceptions.
There's a very nice synergy with Rust here as well, the ? operator and drop allowing for some very
interesting control flow structures to form, ones I haven't fully explored (the aforementioned mentioned future post).
These methods, once you're used to them, feel very natural, and are quite nice. With explicit
tail-calling and the control flow benefits, there's not really a reason to use switch dispatch.
For my use case, the ability for instructions to recursively call the dispatch function
(and not tail-call recursive - state is now stored on the stack) allows for certain types of trap
handling and privileged execution to become very simple, and there's virtually no risk to overflowing
the stack in this case. If you want to know more, check out the ternary section of
my website, or check out the code here!