Interpreters

Interpreters and bytecode VMs

An interpreter's speed is decided by its dispatch loop and its value representation. Pick those two first; everything else is negotiable.

Contract

Inputs

• The language or bytecode format: required, existing or being designed.
• The compiler toolchain: required. Computed goto needs GCC or Clang.
• A benchmark program: required for every performance decision.
• The target platforms: required when a JIT is in scope, because executable-memory rules differ.

Procedure

1. Choose stack or register bytecode. Stack bytecode is compact and trivial to generate; register bytecode runs fewer dispatch cycles per expression and pays for it with register allocation in the compiler front end. Done when: the choice is written down with the workload that decides it.

2. Write the dispatch loop. Start with a switch; it is correct and portable. Then compare computed goto, which gives each opcode its own indirect branch so the predictor trains per opcode. Done when: the benchmark runs and the dispatch strategy is chosen from its measurement, not from habit.

// switch form: one indirect branch serves every opcode
while (1) {
    uint8_t op = *ip++;
    switch (op) {
        case OP_ADD: { Value b = pop(); Value a = pop(); push(a + b); } break;
        case OP_HALT: return;
    }
}

// computed goto: one indirect branch per opcode, GCC and Clang only
static const void *dispatch_table[] = {
    [OP_ADD]  = &&op_add,
    [OP_HALT] = &&op_halt,
};
#define DISPATCH() goto *dispatch_table[*ip++]

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

Guard the goto form with #ifdef __GNUC__ and keep the switch as the fallback for other compilers.

3. Represent values without a memory round trip per operation. Tagged pointers keep the tag in the low bits of an aligned word. NaN boxing stores non-double values inside quiet-NaN bit patterns, which is how LuaJIT boxes everything in one double-sized slot. Done when: the hot arithmetic path never allocates.

typedef uintptr_t Value;
#define TAG_MASK 0x3u

#define MAKE_INT(x)  ((((uint64_t)(int64_t)(x)) << 2) | 0x0)
#define IS_INT(v)    (((v) & TAG_MASK) == 0x0)
#define INT_VAL(v)   ((int64_t)(v) >> 2)   // sign-extends through the tag bits

4. Bound the value stack. Fixed size with an explicit check beats unbounded growth, and the check belongs in the push path, not the opcode handlers. Done when: a deliberately deep program fails with the VM's own stack overflow error.

#define STACK_SIZE 4096
Value stack[STACK_SIZE];
Value *sp = stack;

#define PUSH(v) do { if (sp >= stack + STACK_SIZE) vm_error("stack overflow"); *sp++ = (v); } while (0)
#define POP()   (*--sp)

5. Add an inline cache to every polymorphic site. Cache the last receiver type at the call site; on a hit, call the cached method without lookup. Done when: a hot call site shows a hit rate in the profile.

struct call_site {
    uint32_t cached_type;      // last observed receiver type
    void (*cached_method)(VM *);
    uint32_t miss_count;
};

void invoke(VM *vm, struct call_site *cs, Value receiver) {
    uint32_t t = value_type(receiver);
    if (t == cs->cached_type) {
        cs->cached_method(vm);
        return;
    }
    cs->cached_method = lookup_method(t);
    cs->cached_type = t;
    cs->miss_count++;
    cs->cached_method(vm);
}

Extend to a polymorphic cache of a few type and method pairs when profiling shows a site serving several stable types.

6. Add a first JIT by writing machine code into an executable page. Write into PROT_READ|PROT_WRITE memory, then switch the page to PROT_READ|PROT_EXEC before calling it. On Apple silicon, MAP_JIT plus pthread_jit_write_protect_np replaces the switch. Done when: the compiled function runs and returns the expected value.

#include <sys/mman.h>
#include <string.h>

typedef int (*jit_fn)(int, int);

jit_fn compile_add(void) {
    // add edi, esi ; mov eax, edi ; ret   in System V argument order
    static const uint8_t code[] = {
        0x01, 0xF7,   // add %esi, %edi
        0x89, 0xF8,   // mov %edi, %eax
        0xC3,         // ret
    };
    void *mem = mmap(NULL, sizeof(code), PROT_READ | PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (mem == MAP_FAILED) return NULL;
    memcpy(mem, code, sizeof(code));
    mprotect(mem, sizeof(code), PROT_READ | PROT_EXEC);  // W^X: never write and exec at once
    return (jit_fn)mem;
}

7. Profile before optimizing further. High self time on the indirect jump means dispatch mispredicts; high time in lookup means the caches are missing. Done when: the next change on the list is justified by a profile line, not by folklore.

perf record -g ./my_interp bench.bytecode
perf report --no-children

8. Keep hot VM state in one or two cache lines. Put sp and ip first in the VM struct. Keeping sp in a fixed register through a global register variable is a GCC and Clang trick that costs an otherwise usable register; measure it before keeping it. Done when: the struct layout matches the access frequency.

Failure and recovery

Output

A working interpreter with the chosen dispatch, value representation, and caching, plus a measured before and after for each performance change. The relative dispatch strategy figures and tiering notes are in references/benchmarks.md.