interpreters

Interpreters and Bytecode VMs

Purpose

Guide agents through implementing efficient bytecode interpreters and simple JITs in C/C++: dispatch strategies, VM architecture choices, and performance patterns.

Triggers

• "How do I implement a fast bytecode dispatch loop?"
• "What is the difference between switch dispatch and computed goto?"
• "How do I implement a register-based vs stack-based VM?"
• "How do I add basic JIT compilation to my interpreter?"
• "Why is my interpreter slow?"

Workflow

1. VM architecture choice

Style	Description	Examples
Stack-based	Operands on a value stack; compact bytecode	JVM, CPython, WebAssembly
Register-based	Operands in virtual registers; fewer instructions	Lua 5+, Dalvik
Direct threading	Each "instruction" is a function call	Some Forth implementations
Continuation-passing	Interpreter functions return continuations	Academic

Stack-based: easier to implement, compile to; code generation is simpler. More instructions per expression. Register-based: fewer dispatch iterations; needs register allocation in the compiler; better cache behaviour for complex expressions.

2. Dispatch loop strategies

Switch dispatch (simplest, baseline)

while (1) {
    uint8_t op = *ip++;
    switch (op) {
        case OP_LOAD:  push(constants[*ip++]); break;
        case OP_ADD:   { Value b = pop(); Value a = pop(); push(a + b); } break;
        case OP_HALT:  return;
        // ...
    }
}

Problem: switch compiles to a single indirect branch from a jump table. Modern CPUs can mispredict it heavily because the same indirect branch is used for all opcodes.

Computed goto (GCC/Clang extension — fastest portable approach)

// Table of label addresses
static const void *dispatch_table[] = {
    [OP_LOAD]  = &&op_load,
    [OP_ADD]   = &&op_add,
    [OP_HALT]  = &&op_halt,
    // ...
};

#define DISPATCH() goto *dispatch_table[*ip++]

DISPATCH();  // start

op_load:
    push(constants[*ip++]);
    DISPATCH();

op_add: {
    Value b = pop(); Value a = pop(); push(a + b);
    DISPATCH();
}

op_halt:
    return;