Problem

If you have ever written a stack-based virtual machine or used them (I'm looking at you Python), you may have noticed that they are relatively inefficient compared with a register-based VM or code compiled directly to native machine code. A significant part of that overhead often comes from instruction dispatch. It goes a little something like this: In a bytecode interpreter, the VM repeatedly fetches the next opcode, decodes it, determines which handler should execute, and then jumps to that handler. For simple instructions (which are the more common type of instructions), the cost of this dispatch loop can become surprisingly large relative to the amount of useful work the instruction actually performs.

Stack machines typically make instruction dispatch overhead worse because a single high-level operation often expands into several small bytecode instructions. More instructions means more trips through the dispatch loop, which means greater overhead.

A Small Bytecode Language

For demonstration purposes, I will define a small stack VM with no guest-language heap allocations. This isn't super useful in practice, but I think garbage collection and strategies along those lines are better left to a future post. If you haven't ever worked with a stack-based VM or seen under the hood, this could also be a useful starting point.

Values

Now, let's define what a primitive value is in our stack machine. For simplicity, we only support integers, floats, and booleans.

rust
#[derive(Debug, Clone, Copy, PartialEq)]
enum Value {
    Integer(i64),
    Float(f64),
    Bool(bool)
}

ISA

Now we define our ISA, with primitive stack operations a user may perform.

rust
// The binary instructions pop `b` from the head of the stack, then `a`
// from beneath it, so `a` is the operand that was pushed first.
#[derive(Debug, Clone, PartialEq)]
enum Instruction {
    /// Push a value onto the stack.
    Push(Value),
    /// Pop a value from the stack, discarding it.
    Pop,
    /// Duplicate the value at the head of the stack.
    Dup,
    /// Push a copy of the local in the provided slot.
    Load(u8),
    /// Pop the value at the head of the stack and store
    /// it in the provided local slot.
    Store(u8),
    /// Pop `b` and `a`, pushing `a + b`.
    Add,
    /// Pop `b` and `a`, pushing `a - b`.
    Sub,
    /// Pop `b` and `a`, pushing `a * b`.
    Mul,
    /// Pop `b` and `a`, pushing `a / b`.
    Div,
    /// Pop `b` and `a`, pushing `a % b`.
    Mod,
    /// Arithmetically negate the number at the head of
    /// the stack.
    Neg,
    /// Pop `b` and `a`, pushing whether `a == b`.
    Eq,
    /// Pop `b` and `a`, pushing whether `a < b`.
    LT,
    /// Pop `b` and `a`, pushing whether `a <= b`.
    LE,
    /// Logically negate the boolean at the head of the
    /// stack.
    Not,
    /// Jump unconditionally to the provided instruction
    /// index.
    Jump(u32),
    /// Pop the head of the stack, jumping to the provided
    /// instruction index if it was false.
    JumpIfFalse(u32),
    /// Call the named function, passing it the top n
    /// values on the stack as its arguments.
    Call(String, u8),
    /// Pop the return value, discard the current frame,
    /// and push the return value for the caller.
    Return,
    /// Discontinue the computation.
    Halt
}

Functions

Now that we have a somewhat useful ISA, we can start to think about how we will model our data in our VM. For a function, we need enough information to provide a way to construct its stack frame. We may define this as follows:

rust
#[derive(Debug)]
struct Function {
    name: String,
    arity: u8,
    locals: u8,
    code: Vec<Instruction>
}

Note that locals counts every local slot the function uses, including its arguments, which occupy the first arity slots.

For example, the following function in a hypothetical language would look a little something like this:

rust
/// fn add(a, b) {
///   let c = a + b;
///   return c
/// }
fn add() -> Function {
    Function {
        name: "add".into(),
        arity: 2,
        // a, b and c
        locals: 3,
        code: vec![
            Instruction::Load(0),
            Instruction::Load(1),
            Instruction::Add,
            Instruction::Store(2),
            Instruction::Load(2),
            Instruction::Return
        ]
    }
}

Program

A program is really just a collection of functions plus an entry point:

rust
use std::collections::HashMap;

#[derive(Debug)]
struct Program {
    functions: HashMap<String, Function>,
    entry: String
}

Call Frames

When we call a function, we need to remember where we came from. This allows us to determine where execution should resume afterwards:

rust
/// A suspended caller, saved while its callee runs.
#[derive(Debug)]
struct Frame {
    /// The function that made the call.
    function: String,
    /// The instruction in the caller at which execution
    /// resumes once the callee returns.
    return_ip: u32,
    /// Where the caller's locals begin on the stack.
    base: u32
}

Finally, with all of this together, we can construct a VM for this tiny interpreter:

rust
#[derive(Debug)]
struct VM {
    program: Program,

    /// The function currently executing.
    function: String,
    /// The index of the next instruction to execute.
    ip: u32,
    /// Where the current function's locals begin on the stack.
    base: u32,

    /// The locals and operands of every active call.
    stack: Vec<Value>,

    /// Suspended callers.
    frames: Vec<Frame>,

    /// Whether the VM has been halted.
    halted: bool
}

Runtime Errors

We can enumerate the runtime errors rather than allowing mysterious explosions of malformed bytecode.

rust
#[derive(Debug, PartialEq)]
enum RuntimeError {
    StackUnderflow,
    InvalidLocal(u8),
    UnknownFunction(String),
    InvalidInstructionPointer(u32),
    /// The arity the callee expects, then the number of
    /// args it was called with.
    ArityMismatch(u8, u8),
    TypeError(String),
    DivisionByZero
}

Interpreter

With all of this together, we can write the interpreter.

rust
use RuntimeError::*;

/// obtain the current function from a function name
fn current_function(vm: &VM) -> Result<&Function, RuntimeError> {
    match vm.program.functions.get(&vm.function) {
        Some(func) => Ok(func),
        None => Err(UnknownFunction(vm.function.clone()))
    }
}

/// fetch the current instruction from the VM
fn fetch(vm: &VM) -> Result<&Instruction, RuntimeError> {
    let current_fn = current_function(vm)?;
    match current_fn.code.get(vm.ip as usize) {
        Some(instruction) => Ok(instruction),
        None => Err(InvalidInstructionPointer(vm.ip))
    }
}

/// index into the stack where the current function's operands begin,
/// i.e. just past its locals
fn operand_base(vm: &VM) -> Result<usize, RuntimeError> {
    let current_fn = current_function(vm)?;
    Ok((vm.base + current_fn.locals as u32) as usize)
}

/// pop an operand, refusing to pop into the current function's locals
fn pop_operand(vm: &mut VM) -> Result<Value, RuntimeError> {
    let operand_base = operand_base(vm)?;
    if vm.stack.len() <= operand_base {
        return Err(StackUnderflow);
    }

    match vm.stack.pop() {
        Some(value) => Ok(value),
        None => Err(StackUnderflow)
    }
}

fn execute_dup(vm: &mut VM) -> Result<(), RuntimeError> {
    let value = pop_operand(vm)?;
    vm.stack.push(value);
    vm.stack.push(value);
    Ok(())
}

/// Add, Sub, Mul, Div and Mod. With `a` pushed before `b`, computes `a op b`.
fn execute_arithmetic(vm: &mut VM, op: &Instruction) -> Result<(), RuntimeError> {
    let b = pop_operand(vm)?;
    let a = pop_operand(vm)?;
    let result = match (a, b) {
        (Value::Integer(a), Value::Integer(b)) => Value::Integer(match op {
            Instruction::Add => a.wrapping_add(b),
            Instruction::Sub => a.wrapping_sub(b),
            Instruction::Mul => a.wrapping_mul(b),
            Instruction::Div | Instruction::Mod if b == 0 => return Err(DivisionByZero),
            Instruction::Div => a.wrapping_div(b),
            Instruction::Mod => a.wrapping_rem(b),
            _ => return Err(TypeError(format!("{:?} is not an arithmetic instruction", op)))
        }),
        (Value::Float(a), Value::Float(b)) => Value::Float(match op {
            Instruction::Add => a + b,
            Instruction::Sub => a - b,
            Instruction::Mul => a * b,
            Instruction::Div => a / b,
            Instruction::Mod => a % b,
            _ => return Err(TypeError(format!("{:?} is not an arithmetic instruction", op)))
        }),
        (a, b) => return Err(TypeError(format!("cannot apply {:?} to {:?} and {:?}", op, a, b)))
    };
    vm.stack.push(result);
    Ok(())
}

// execute_load, execute_store, execute_neg, execute_eq, execute_compare,
// execute_not and execute_jump_if_false follow the same pattern.

/// The args on top of the stack become the callee's first locals; the
/// rest of its locals are pushed after them, zero-initialised.
fn execute_call(vm: &mut VM, name: String, args: u8) -> Result<(), RuntimeError> {
    let (arity, locals) = match vm.program.functions.get(&name) {
        Some(func) => (func.arity, func.locals),
        None => return Err(UnknownFunction(name))
    };
    if args != arity {
        return Err(ArityMismatch(arity, args));
    }
    if vm.stack.len() < operand_base(vm)? + args as usize {
        return Err(StackUnderflow);
    }

    let base = vm.stack.len() - args as usize;
    for _ in arity..locals {
        vm.stack.push(Value::Integer(0));
    }

    vm.frames.push(Frame {
        function: std::mem::replace(&mut vm.function, name),
        return_ip: vm.ip + 1,
        base: vm.base
    });
    vm.base = base as u32;
    vm.ip = 0;
    Ok(())
}

/// Replaces the callee's locals and operands with its return value.
/// Returning from the entry function halts the VM.
fn execute_return(vm: &mut VM) -> Result<(), RuntimeError> {
    let result = pop_operand(vm)?;
    vm.stack.truncate(vm.base as usize);
    match vm.frames.pop() {
        Some(frame) => {
            vm.function = frame.function;
            vm.ip = frame.return_ip;
            vm.base = frame.base;
        },
        None => vm.halted = true
    }
    vm.stack.push(result);
    Ok(())
}

/// execute a single instruction
fn step(vm: &mut VM) -> Result<(), RuntimeError> {
    let instruction = fetch(vm)?.clone();
    match instruction {
        Instruction::Push(value) => vm.stack.push(value),
        Instruction::Pop => {
            pop_operand(vm)?;
        },
        Instruction::Dup => execute_dup(vm)?,
        Instruction::Load(slot) => execute_load(vm, slot)?,
        Instruction::Store(slot) => execute_store(vm, slot)?,
        Instruction::Add
        | Instruction::Sub
        | Instruction::Mul
        | Instruction::Div
        | Instruction::Mod => execute_arithmetic(vm, &instruction)?,
        Instruction::Neg => execute_neg(vm)?,
        Instruction::Eq => execute_eq(vm)?,
        Instruction::LT | Instruction::LE => execute_compare(vm, &instruction)?,
        Instruction::Not => execute_not(vm)?,
        // the remaining instructions set the instruction pointer themselves
        Instruction::Jump(target) => {
            vm.ip = target;
            return Ok(());
        },
        Instruction::JumpIfFalse(target) => return execute_jump_if_false(vm, target),
        Instruction::Call(name, args) => return execute_call(vm, name, args),
        Instruction::Return => return execute_return(vm),
        Instruction::Halt => {
            vm.halted = true;
            return Ok(());
        }
    }
    vm.ip += 1;
    Ok(())
}

/// run the VM until it halts
fn run(vm: &mut VM) -> Result<(), RuntimeError> {
    while !vm.halted {
        step(vm)?;
    }
    Ok(())
}

We now have a working interpreter, but its hot path contains several costs unrelated to the actual computation being performed. Before introducing instruction fusion, let's first remove those incidental costs so that we have a reasonable baseline to optimize.

Function Table

Every trip through step currently pays for the fact that functions are identified by name. fetch calls current_function, which hashes vm.function and probes the map just to find the code we are already in the middle of executing. pop_operand does the same thing again through operand_base, so a single Add costs three string-keyed map lookups: one to fetch the instruction and one for each operand it pops. A Call adds yet another to find the callee.

The names cost us in a less obvious way too. Because Call owns a String, Instruction cannot be Copy, so the clone in step heap-allocates a fresh copy of the callee's name every time a call executes.

None of this is work the guest program asked for. Names matter to whoever writes the bytecode, but the interpreter only needs to know which function is meant, and that question can be answered before execution starts.

So instead, we can assign every function an integer identifier and store the functions in an array, with each function's identifier being its index. Looking up a function then becomes a bounds check and an indexed access, rather than hashing a string and comparing keys.

The translation from names to identifiers happens when the bytecode is produced. The compiler or assembler builds a name-to-identifier map as it collects the functions, and uses it to rewrite every call, in the same way it resolves jump labels to instruction indexes. That map can be thrown away once the program is loaded. We keep name on Function purely for error messages and debugging.

First, we introduce a function identifier:

rust
type FunctionId = u32;

Our program can then store functions in an array rather than a map:

rust
#[derive(Debug)]
struct Program {
    functions: Vec<Function>,
    entry: FunctionId
}

We also update Call so that the bytecode refers directly to a function ID:

rust
#[derive(Debug, Clone, Copy, PartialEq)]
enum Instruction {
    Push(Value),
    Pop,
    // ...
    /// Call the function with the provided id, passing it
    /// the top n values on the stack as its arguments.
    Call(FunctionId, u8),
    Return,
    Halt
}

With the String gone, every variant is plain data and Instruction can derive Copy. The clone in step is now a copy of a few bytes and never touches the allocator.

The current function stored by the VM and by suspended call frames should also use FunctionId:

rust
/// A suspended caller, saved while its callee runs.
#[derive(Debug)]
struct Frame {
    /// The function that made the call.
    function: FunctionId,
    /// The instruction in the caller at which execution
    /// resumes once the callee returns.
    return_ip: u32,
    /// Where the caller's locals begin on the stack.
    base: u32
}

#[derive(Debug)]
struct VM {
    program: Program,

    /// The function currently executing.
    function: FunctionId,
    /// The index of the next instruction to execute.
    ip: u32,
    /// Where the current function's locals begin on the stack.
    base: u32,

    /// The locals and operands of every active call.
    stack: Vec<Value>,

    /// Suspended callers.
    frames: Vec<Frame>,

    /// Whether the VM has been halted.
    halted: bool
}

Now fetching the current function no longer requires a string-keyed map lookup:

rust
/// obtain the current function from its function id
fn current_function(vm: &VM) -> Result<&Function, RuntimeError> {
    match vm.program.functions.get(vm.function as usize) {
        Some(func) => Ok(func),
        None => Err(UnknownFunctionId(vm.function))
    }
}

execute_call changes in the same way. Only the lookup and the error differ, the rest of the function is untouched:

rust
fn execute_call(vm: &mut VM, id: FunctionId, args: u8) -> Result<(), RuntimeError> {
    let (arity, locals) = match vm.program.functions.get(id as usize) {
        Some(func) => (func.arity, func.locals),
        None => return Err(UnknownFunctionId(id))
    };
    // ...

    vm.frames.push(Frame {
        function: std::mem::replace(&mut vm.function, id),
        return_ip: vm.ip + 1,
        base: vm.base
    });
    vm.base = base as u32;
    vm.ip = 0;
    Ok(())
}

And let's not forget to change the corresponding runtime error as well:

rust
#[derive(Debug, PartialEq)]
enum RuntimeError {
    StackUnderflow,
    InvalidLocal(u8),
    UnknownFunctionId(FunctionId),
    InvalidInstructionPointer(u32),
    /// The arity the callee expects, then the number of
    /// args it was called with.
    ArityMismatch(u8, u8),
    TypeError(String),
    DivisionByZero
}

Now consider the function factorial, and assume that it was assigned the function id 4.

text
fn factorial(n) {
  if n <= 1 {
    return 1
  }

  return n * factorial(n - 1)
}

Its bytecode would look a bit like this:

assembly
;; factorial: arity 1, locals 1
LOAD 0                  ;; n
PUSH 1
LE                      ;; n <= 1
JUMP_IF_FALSE recurse

PUSH 1
RETURN

;; Labels only exist in the assembly. The assembler replaces each
;; one with the index of the instruction it points at, so the jump
;; above is emitted as JUMP_IF_FALSE 6.
recurse:
LOAD 0                  ;; n, the left operand of the MUL below

LOAD 0
PUSH 1
SUB                     ;; n - 1
CALL 4 1                ;; factorial(n - 1): function id 4, 1 argument

MUL                     ;; n * factorial(n - 1)
RETURN

The recursive call is where the function table pays off. CALL 4 1 indexes straight into functions, where previously every level of the recursion hashed the string "factorial" to find the callee and allocated a copy of it just to execute the instruction. It's a small enhancement, but when you are designing a runtime for a virtual machine meant to run any program, you take all the wins that you can get.

Benchmarks

For the purposes of this article, we will benchmark two programs: a loop built out of jumps, which never calls a function, and a recursive Fibonacci function, which does little else.

Loops with jumps

text
let i = 0;
while i < 5000000 {
  i = i + 1;
}
return i;
assembly
;; main: arity 0, locals 1
LOAD 0                  ;; i
PUSH 5000000
LT                      ;; i < 5000000
JUMP_IF_FALSE 9
LOAD 0
PUSH 1
ADD
STORE 0                 ;; i = i + 1
JUMP 0
LOAD 0
RETURN

This executes 45,000,006 instructions.

Fibonacci

text
fn fib(n) {
  if n < 2 {
    return n
  }

  return fib(n - 1) + fib(n - 2)
}
assembly
;; fib: arity 1, locals 1
LOAD 0                  ;; n
PUSH 2
LT                      ;; n < 2
JUMP_IF_FALSE 6
LOAD 0
RETURN
LOAD 0
PUSH 1
SUB                     ;; n - 1
CALL 1 1                ;; fib(n - 1): function id 1, 1 argument
LOAD 0
PUSH 2
SUB                     ;; n - 2
CALL 1 1                ;; fib(n - 2)
ADD
RETURN

The version of the interpreter without a function table runs the same bytecode, except that both calls refer to fib by name. We call fib(30) from a three instruction main, which executes 26,925,369 instructions in total.

Results

The following constitute benchmarks run on a 2026 M5 MacBook Air laptop with 24 GB of RAM. Each program was run 31 times against each version of the interpreter, after one warm-up run that was thrown away, and the times reported are the medians of those 31 runs. Everything was compiled in release mode.

Program Interpreter Time Per instruction Speedup
Loop to 5,000,000 Functions by name 804.6 ms 17.88 ns 1.00x
Function table 99.5 ms 2.21 ns 8.09x
fib(30) Functions by name 664.7 ms 24.69 ns 1.00x
Function table 92.3 ms 3.43 ns 7.20x

The function table makes the interpreter seven to eight times faster. Notice that the loop benefits just as much as fib does, even though it never executes a Call. Most of the cost was never in calling functions. It was in looking up the current function by name on every fetch and every pop.

One caveat: Rust's HashMap uses SipHash by default, which is designed to resist collision attacks rather than to be fast. A cheaper hasher could potentially narrow the gap.

Caching the Operand Base

The function table made current_function cheap, but we are still calling it far more often than we need to. Every pop_operand goes through operand_base, which looks up the current function just to read its locals and add it to vm.base. An Add therefore recomputes the same number twice, and it is a number that cannot change while the function is running. The operand base only moves when we enter or leave a function.

So we compute it at exactly those two points and keep the result on the VM. The suspended caller's operand base is saved in its frame alongside its base, so that returning doesn't need to look anything up either:

rust
/// A suspended caller, saved while its callee runs.
#[derive(Debug)]
struct Frame {
    /// The function that made the call.
    function: FunctionId,
    /// The instruction in the caller at which execution
    /// resumes once the callee returns.
    return_ip: u32,
    /// Where the caller's locals begin on the stack.
    base: u32,
    /// Where the caller's operands begin on the stack.
    operand_base: u32
}

#[derive(Debug)]
struct VM {
    program: Program,

    /// The function currently executing.
    function: FunctionId,
    /// The index of the next instruction to execute.
    ip: u32,
    /// Where the current function's locals begin on the stack.
    base: u32,
    /// Where the current function's operands begin on the stack,
    /// i.e. just past its locals. Always `base` plus the current
    /// function's `locals`.
    operand_base: u32,

    /// The locals and operands of every active call.
    stack: Vec<Value>,

    /// Suspended callers.
    frames: Vec<Frame>,

    /// Whether the VM has been halted.
    halted: bool
}

The operand_base function disappears entirely, and pop_operand is left with a comparison against a field:

rust
/// pop an operand, refusing to pop into the current function's locals
fn pop_operand(vm: &mut VM) -> Result<Value, RuntimeError> {
    if vm.stack.len() <= vm.operand_base as usize {
        return Err(StackUnderflow);
    }

    match vm.stack.pop() {
        Some(value) => Ok(value),
        None => Err(StackUnderflow)
    }
}

execute_call already looks up the callee's locals in order to reserve space for them, so it can set the new operand base without any extra work:

rust
fn execute_call(vm: &mut VM, id: FunctionId, args: u8) -> Result<(), RuntimeError> {
    let (arity, locals) = match vm.program.functions.get(id as usize) {
        Some(func) => (func.arity, func.locals),
        None => return Err(UnknownFunctionId(id))
    };
    if args != arity {
        return Err(ArityMismatch(arity, args));
    }
    if vm.stack.len() < vm.operand_base as usize + args as usize {
        return Err(StackUnderflow);
    }

    let base = vm.stack.len() - args as usize;
    for _ in arity..locals {
        vm.stack.push(Value::Integer(0));
    }

    vm.frames.push(Frame {
        function: std::mem::replace(&mut vm.function, id),
        return_ip: vm.ip + 1,
        base: vm.base,
        operand_base: vm.operand_base
    });
    vm.base = base as u32;
    vm.operand_base = base as u32 + locals as u32;
    vm.ip = 0;
    Ok(())
}

And execute_return restores it along with everything else:

rust
fn execute_return(vm: &mut VM) -> Result<(), RuntimeError> {
    let result = pop_operand(vm)?;
    vm.stack.truncate(vm.base as usize);
    match vm.frames.pop() {
        Some(frame) => {
            vm.function = frame.function;
            vm.ip = frame.return_ip;
            vm.base = frame.base;
            vm.operand_base = frame.operand_base;
        },
        None => vm.halted = true
    }
    vm.stack.push(result);
    Ok(())
}

The one other place that needs to know about it is wherever the VM is first constructed, which must set operand_base to the entry function's locals, since the entry function's base is 0.

Benchmarks

Like in the previous section, the benchmarks here were run on a 2026 M5 MacBook Air with 24 GB of RAM. The programs and the method are the same too: the loop to 5,000,000 and fib(30), each run 31 times against each version of the interpreter after one discarded warm-up run, compiled in release mode, with the median reported.

Program Interpreter Time Per instruction Speedup over function table Speedup over functions by name
Loop to 5,000,000 Function table 99.5 ms 2.21 ns 1.00x 8.09x
Function table + cached operand base 93.3 ms 2.07 ns 1.07x 8.63x
fib(30) Function table 92.3 ms 3.43 ns 1.00x 7.20x
Function table + cached operand base 84.1 ms 3.13 ns 1.10x 7.90x

Caching the operand base takes about 6% off the loop and about 9% off fib(30). That is a far smaller win than the function table was, but we take what we can get!

Instruction Fusion

Finally, we get to the actual purpose of this article with a somewhat optimized (there is probably still other stuff to be optimized) stack virtual machine with no guest-language heap allocations. In this pass, we will create intermediate instructions that multiple single stack operations will be converted into. This will allow us to tackle some of the instruction dispatch overhead. For our purposes, we will be optimizing compare and branch and local with constant arithmetic by introducing the following instructions:

rust
enum Instruction {
    // ... the existing instructions ...

    /// `Load s, Push k, LT, JumpIfFalse t`
    LoadPushLTJumpIfFalse(u8, i32, u32),
    /// `Load s, Push k, LE, JumpIfFalse t`
    LoadPushLEJumpIfFalse(u8, i32, u32),
    /// `Load s, Push k, Add`
    LoadPushAdd(u8, i32),
    /// `Load s, Push k, Sub`
    LoadPushSub(u8, i32),
    /// `Load s, Push k, Add, Store s`
    LoadPushAddStore(u8, i32)
}

This will allow the following reductions in the number of instructions:

Before After
LOAD 0
PUSH 5000000
LT
JUMP_IF_FALSE 9		 LOAD_PUSH_LT_JUMP_IF_FALSE 0 5000000 9
LOAD 0
PUSH 5000000
LE
JUMP_IF_FALSE 9		 LOAD_PUSH_LE_JUMP_IF_FALSE 0 5000000 9
LOAD 0
PUSH 1
ADD		 LOAD_PUSH_ADD 0 1
LOAD 0
PUSH 1
SUB		 LOAD_PUSH_SUB 0 1
LOAD 0
PUSH 1
ADD
STORE 0		 LOAD_PUSH_ADD_STORE 0 1

Each fused instruction is named after the sequence it replaces, and carries the operands of the instructions it swallowed: the local slot, the constant, and for the first two the jump target.

Keeping Instructions Small

You may have noticed that the constant is an i32, where Push carries a whole Value. That is deliberate. Instruction is currently 16 bytes, and with an i32 constant the fused instructions fit in those same 16 bytes. If the three-operand forms carried a Value or an i64 instead, Instruction would grow to 24 bytes, and every instruction in every function would get bigger to make room for a few fused ones.

The price is that we can only fuse a Push of an integer that fits in 32 bits. Anything else, a float or a very large integer, is simply left as the original sequence. With this approach, we can catch a lot of optimizations while not allowing our instructions to grow in size :)

The Fusion Pass

These instructions are not intended to be written by hand, and are produced by a preprocessing pass that runs once over the program before it executes. First, we define a function that recognizes a fusable sequence at the start of a slice of code.

rust
/// The fused form of the sequence at the start of `code`, if it has one,
/// along with the number of instructions in that sequence.
fn fused(code: &[Instruction]) -> Option<(Instruction, usize)> {
    let (slot, k) = match code {
        [Instruction::Load(slot), Instruction::Push(Value::Integer(k)), ..] => (*slot, i32::try_from(*k).ok()?),
        _ => return None
    };
    match &code[2..] {
        [Instruction::LT, Instruction::JumpIfFalse(target), ..] => {
            Some((Instruction::LoadPushLTJumpIfFalse(slot, k, *target), 4))
        },
        [Instruction::LE, Instruction::JumpIfFalse(target), ..] => {
            Some((Instruction::LoadPushLEJumpIfFalse(slot, k, *target), 4))
        },
        [Instruction::Add, Instruction::Store(store), ..] if *store == slot => {
            Some((Instruction::LoadPushAddStore(slot, k), 4))
        },
        [Instruction::Add, ..] => Some((Instruction::LoadPushAdd(slot, k), 3)),
        [Instruction::Sub, ..] => Some((Instruction::LoadPushSub(slot, k), 3)),
        _ => None
    }
}

The pass itself walks each function and applies it:

rust
/// Rewrite the fusable sequences of every function into their fused
/// instructions. Only the first instruction of a sequence is overwritten.
/// The rest stay where they are, so no jump target moves and a jump into
/// the middle of a sequence still finds the original instructions.
fn fuse(program: &mut Program) {
    for function in &mut program.functions {
        let code = &mut function.code;
        let mut index = 0;
        while index < code.len() {
            match fused(&code[index..]) {
                Some((instruction, length)) => {
                    code[index] = instruction;
                    index += length;
                },
                None => index += 1
            }
        }
    }
}

This executes in-place before running our VM, and allows old instructions to be rewritten into a more compressed format. This doesn't turn our VM into a register machine, but it does recover some of what makes one fast: fewer dispatches, and fewer values shuffled on and off the operand stack along the way. Of course, there are also updates to the instruction dispatch function.

Executing Fused Instructions

A fused instruction has one rule to follow: it must behave exactly like the sequence it replaced. That means the same result, and also the same error if the sequence would have failed. All five of ours read an integer out of a local, so they share a helper that does so and reports the error the unfused instruction would have reported for any other type:

rust
/// The integer in the provided local slot and its index into the stack,
/// on behalf of a fused instruction that applies `op` to it and `k`. A
/// local of any other type is the error the unfused `op` would report.
fn integer_local(vm: &VM, slot: u8, op: Instruction, k: i32) -> Result<(usize, i64), RuntimeError> {
    let index = local_index(vm, slot)?;
    match vm.stack.get(index) {
        Some(Value::Integer(a)) => Ok((index, *a)),
        Some(a) => Err(TypeError(format!("cannot apply {:?} to {:?} and {:?}", op, a, Value::Integer(k as i64)))),
        None => Err(InvalidLocal(slot))
    }
}

/// `Load s, Push k, LT, JumpIfFalse t` and its LE counterpart, where `op`
/// is the comparison. Nothing is pushed: the local is compared in place.
fn execute_load_push_compare_jump_if_false(
    vm: &mut VM, op: Instruction, slot: u8, k: i32, target: u32
) -> Result<(), RuntimeError> {
    let (_, a) = integer_local(vm, slot, op, k)?;
    let result = match op {
        Instruction::LT => a < k as i64,
        Instruction::LE => a <= k as i64,
        _ => return Err(TypeError(format!("{:?} is not a comparison instruction", op)))
    };
    vm.ip = if result { vm.ip + 4 } else { target };
    Ok(())
}

/// `Load s, Push k, Add` and its Sub counterpart, where `op` is the
/// arithmetic instruction. Only the result is pushed.
fn execute_load_push_arithmetic(vm: &mut VM, op: Instruction, slot: u8, k: i32) -> Result<(), RuntimeError> {
    let (_, a) = integer_local(vm, slot, op, k)?;
    let result = match op {
        Instruction::Add => a.wrapping_add(k as i64),
        Instruction::Sub => a.wrapping_sub(k as i64),
        _ => return Err(TypeError(format!("{:?} is not an arithmetic instruction", op)))
    };
    vm.stack.push(Value::Integer(result));
    vm.ip += 3;
    Ok(())
}

/// `Load s, Push k, Add, Store s`. The local is updated in place.
fn execute_load_push_add_store(vm: &mut VM, slot: u8, k: i32) -> Result<(), RuntimeError> {
    let (index, a) = integer_local(vm, slot, Instruction::Add, k)?;
    vm.stack[index] = Value::Integer(a.wrapping_add(k as i64));
    vm.ip += 4;
    Ok(())
}

None of these push the local or the constant onto the stack. The compare-and-branch never builds a Bool only to pop it again and check that it is one. LoadPushAddStore does not touch the operand stack at all. And since each of them stands for three or four instructions, each advances the instruction pointer by three or four rather than by one.

All that is left is to dispatch to them from step:

rust
        Instruction::LoadPushLTJumpIfFalse(slot, k, target) => {
            return execute_load_push_compare_jump_if_false(vm, Instruction::LT, slot, k, target)
        },
        Instruction::LoadPushLEJumpIfFalse(slot, k, target) => {
            return execute_load_push_compare_jump_if_false(vm, Instruction::LE, slot, k, target)
        },
        Instruction::LoadPushAdd(slot, k) => return execute_load_push_arithmetic(vm, Instruction::Add, slot, k),
        Instruction::LoadPushSub(slot, k) => return execute_load_push_arithmetic(vm, Instruction::Sub, slot, k),
        Instruction::LoadPushAddStore(slot, k) => return execute_load_push_add_store(vm, slot, k)

Benchmarks

Same machine, same two programs and same method as before. These numbers come from a fresh run of all the interpreters, which is why the unfused times differ slightly from the table in the previous section.

Program Interpreter Time Instructions executed Per instruction Speedup
Loop to 5,000,000 Unfused 98.8 ms 45,000,006 2.20 ns 1.00x
Fused 36.6 ms 15,000,003 2.44 ns 2.70x
fib(30) Unfused 83.5 ms 26,925,369 3.10 ns 1.00x
Fused 57.5 ms 13,462,686 4.27 ns 1.45x

Fusion makes the loop 2.7 times faster and fib(30) about 1.45 times faster. Measured against the interpreter we started with, the one that looked functions up by name, that is 22 times faster on the loop and 11.6 times faster on fib(30).

Look at the per instruction column, though. The fused interpreter is slower per instruction, because each fused instruction does the work of three or four. The win comes entirely from executing fewer of them: a third as many for the loop, and half as many for fib. This is the whole idea of instruction fusion in one table. We did not make dispatch any cheaper, we just stopped paying for it so often.

It also explains why fib gains less than the loop. Every instruction in the loop body ended up inside a fused sequence except the Jump. In fib, a call that recurses goes from executing 14 instructions to 7 (and a base case from 6 to 3), but the two calls, the return and the final Add are all still dispatched one at a time, and calls and returns spend their time setting up and tearing down frames rather than in dispatch. If we really cared about squeezing more out of it, we could do something like LT_JUMP_IF_FALSE t and LOAD_RETURN s. A more heavily optimized stack VM would have more and more of these instructions for different cases that frequently appear in a program to squeeze out performance.

Conclusion

Instruction fusion is a very important technique for squeezing performance out of stack-based VMs, along with other techniques shown in this article. Things that you don't really think of suddenly become important for squeezing out performance of programs. I know that when I program, I usually look to the easiest or what I consider to be the most elegant solution without regard for performance. That seems to be a good place to start, so long as you benchmark and then find opportunities for enhancements later as they become necessary for your workloads. Thank you for taking the time to read this article, and have a wonderful day!