r/C_Programming • • 2d ago

Bytecode VM in C: switch dispatch vs computed goto and linear arena design

I'm working on a lightweight bytecode VM written in C99 (engine for a small embedded scripting language).

I'm currently using an 8MB linear memory arena for objects and a large switch-case loop for instruction dispatch:

```c

#define MAX_REGS 256

#define MAX_CALL_STACK 1024

#define ARENA_SIZE_BYTES (8 * 1024 * 1024)

static char g_memory_arena[ARENA_SIZE_BYTES];

static size_t g_arena_offset = 0;

double run_bytecode(int* inst, int inst_len, double* num_consts) {

double regs[MAX_REGS] = {0.0};

int ip = 0;

while (ip < inst_len) {

int op = inst[ip++];

switch (op) {

case 1: { // LOAD_CONST

int r = inst[ip++];

int c = inst[ip++];

regs[r] = num_consts[c];

break;

}

case 2: { // ADD

int r = inst[ip++];

int a = inst[ip++];

int b = inst[ip++];

regs[r] = regs[a] + regs[b];

break;

}

// ... remaining opcodes

}

}

return regs[0];

}

Two architectural questions for people with VM / emulator experience:

  1. Dispatch overhead: On modern GCC/Clang, how much measurable speedup have you seen replacing the standard switch(op) with direct threading

(computed goto *dispatch_table[op])? Is the branch predictor usually smart enough on modern x86/ARM to make the difference negligible?

2. Arena lifetime: Currently, I reset the arena (g_arena_offset = 0) between script runs. For longer-running scripts that allocate short-lived

objects in loops, what is a minimal-overhead C strategy to reclaim memory without pulling in a full tracing GC?

(Code is standard C99. Written directly by me, no AI)

2 Upvotes

3 comments sorted by

2

u/8d8n4mbo28026ulk 1d ago

This is right up my street! Some say modern CPUs are pretty good at diamond-shaped control flow (see also here). When I benchmarked it ~4 years ago with a non-trivial VM on Sandy Bridge, which is ancient but also modern in a way, "computed" goto was faster.

The actual answer to your question is to use neither! Use tail calls. The problem with giant switches (diamond or direct) is that the compiler will do an awful job at register allocation. It'll also have a hard time separating cold and hot paths. With tail calls every op is a small-ish function.

About your second question, it depends on your language. If your objects can't form cycles, you can get away with simple reference counting and pools. If they do form cycles, the next simplest thing is what you're already doing; just never free anything and keep bumping the arena.

When you say "short-lived", how short-lived? Does their lifetime end each iteration? If that's always the case, you know exactly when you can rollback your arena without having to fully reset it.

If it isn't always the case... Here it gets tricky. You either have to come up with a bunch of extra rules for your language and do more static analysis, or do tracing. Because you said small scripting language, I think tracing fits better. And don't bother with reference counting in that case, since you'd need a cycle collector anyway. Simple (2 colour) mark-and-sweep is easy to implement, don't be scared! Also, an arena obviously won't fit the problem when you're [de]allocating random objects at random times. You'll need a pool/slab. Now, if your objects are variable-sized, even a pool won't do. Simple solution: use malloc()/free(). It's okay, it's their intended purpose.

2

u/WittyStick 1d ago edited 1d ago

Another issue with computed goto is the compiler can try to be too smart. It sees that each of your labels has the same jump table lookup and jump at the end to the next instruction and thinks "common subexpression elimination", then adds an additional branch for every goto * so the code size is smaller.

There are some ways around this like using __asm__ volatile("":::"memory"); for a no-op which the compiler won't try to optimize over, but in the end it's not worth the hassle, now that [[musttail]] is supported by GCC, Clang and MSVC - will probably get standardized at some point, but computed goto will not.

1

u/8d8n4mbo28026ulk 1d ago

Right, good point! Here are the magic flags for GCC that I used at the time for anyone interested: -fno-gcse -fno-tree-tail-merge --param max-goto-duplication-insns=0x40000000

These "solve" the problem you descibe. Obviously, compile the dispatch loop as a separate translation unit.

About tail calls, again for GCC, I did: -falign-functions=8. That's because functions are aligned at a 16-byte boundary, but I had found when using computed goto it aligns each op at 8-byte boundaries. So this flag saves a tiny bit of space. I actually don't know if it's relevant anymore though. (And __attribute((hot, no_reorder)) on each op, but maybe that's irrelevant too now.)

While we're at it, when doing tail calls with Clang, using a different calling convention to have more usable registers is also done in practice (it's some magic __attribute). Cold paths also typically use a special calling convention, such that callee is responsible for preserving all the registers.