Computed goto for efficient dispatch tables (2012) | Hacker News Reader

Computed goto for efficient dispatch tables (2012)

eli.thegreenplace.net

47 pointshenning26 comments

You could do this in BBC Basic to make an ultra-fast switch.

    20 GOTO (30 + (start%*10))

I used to use it in game loops to call different procedures for character control based on the type of character. Just needed a bit of careful tuning of the character type integer and the line numbers.

This was genuinely one of the BBC features I missed most in (the Amstrad CPC’s) Locomotive BASIC. I remember reimplementing EVAL, which Locomotive was also missing, but not computed GOTO.

Used to work with stepper motors and basic. Legacy code.

Required very precise timing. Something Basic didn’t have.

So we used for loops.

Need a 2ms loop. 5,000 iterations. Etc.

Worked fine for years, until we couldn’t order the same cpus. Then machine ran way to fast.

So we set it up so that at boot time, it would calibrate how many loops equaled various milliseconds. Problem solved.

Was a really weird early job.

I don't do much C programming, but I set up a benchmark of the code in this post and it does indeed seem to be about 25% faster for the toy instruction set in the post. https://github.com/fearofcode/labeled_goto_test

> seem to be about 25% faster

So if you tested sometime between Haswell and Skylake, there was a period when there was no noticeable difference in cgoto vs a switch dispatch[1].

Then Intel got caught up in Meltdown, which is how it was speculating through branches and we're back to 2010 speeds for the switch dispatch, because the branch prediction won't load up the cache (the instruction cache) or start decoding before the conditional is entirely processed.

[1] - https://news.ycombinator.com/item?id=15397109

We'll probably get the speed up parity back once there's a proper speculative execution barrier instruction added to the ISA (though not for currently released chips).

Link about Meltdown mitigations? I’ve been operating off idea that computed goto isn’t faster anymore due to better branch prediction, would love to see something in-depth to the contrary.

You don't know until you try. Computed goto is great by itself, but it can disable some optimizations. Large functions can also disable some optimizations, so splitting opcodes out into separate functions can sometimes be good. Sometimes an array of function pointers will beat a switch or computed goto. Something like switch(opcode & 0xff000000) is far worse than something like switch(opcode >> 24) because gcc will think that it is sparse (and generate a tree of branches instead of a jump table) even if all possible cases are present. Marking the default with __builtin_unreachable() can help.

What Eli (and most others) is missing, are two more common strategies to avoid this dispatcher:

1st: implement the ops basic block as linked list, not an array of opcodes. Thus the next op can be called directly. No lookup and no indirect call.

2nd: inline the op insn into the basic block array, like a jit or just llvm byte code or similar. No jumps, everything stays in the i-cache.

There are more, even faster options, like luajit. Dispatch tables are pretty desperate in 2020. With 20 ops and short op insns (as in lua) everything fits into the icache. With fixed registers you can be pretty fast.

IIUC your first option is what is known as threaded code or threaded interpreter https://en.m.wikipedia.org/wiki/Threaded_code

Right but that's how VM's like CRuby do it. Dispatch looks like:

  goto *(void const *) *virtual_pc_in_register;

That gets translated to an indirect jump. There's no lookup in a dispatch table but that's still an indirect branch.

This is actually marginally better than LuaJIT which does jump * (dispatch_table + *virtual_pc_in_register) but LuaJIT does this so it can swap the dispatch tables to switch to trace recording.

I don't understand what you mean by either of these techniques.

1) If you have a basic block of bytecodes, how does a linked list help? You still have an indirect jump to actually execute the instructions for the bytecode op. Or do you mean having a linked-list of direct jumps somehow?

2) Do you mean template JIT by replacing the jump to the bytecode op with implementation of the op?

Do you mean the tracing compiler? LuaJIT's interpreter still uses a dispatch table.

You seem to be describing threaded code, but using a linked list instead of an array. Why go through the extra pointer chasing to use a linked list of code entry points instead of iterating over an array of code entry points?

[jonesforth.s] is a great search term for a well-documented Forth implementation explaining how threaded code works.

I'm actually surprised I've never seen a system that uses tiny JIT stubs to implement the interpreter portion of a modern hybrid interpreter and JIT system. The class loader would initially "JIT" each method as a function call to the interpreter function followed immediately by a return, with a pointer to a memory-mapped buffer of the bytecode after the return instruction. The interpreter function would look at its return address (which points to the JIT stub's return instruction) and add a constant offset to find the pointer to the bytecode to interpret. This avoids the need for an extra pointer indirection or conditional branch in your hot path method dispatch. Granted, in your really hot paths, you hope your JIT inlines everything.

Op arrays have the advantage of being in the i-cache, but needing an dispatcher with indirect calls.

Op linked lists are bad for the icache, but use all direct calls, which are much better cachable. The best is when you sort the list to be adjacent. Then you have the best of both.

> Dispatch tables are pretty desperate in 2020

You assume the development bandwidth exists to implement JIT runtimes for all small interpreters/VMs. Transforming VM bytecode into host machine code isn't a new concept, quite the opposite. The development cost to do so generally outweighs the benefits, especially in the beginning of development.

Plus, fortunately, such a refactor is generally unobtrusive, so computed goto is by far a more attractive option than implementing a JIT runtime.

IIRC Dalvik, when it launched, used a pretty fancy computed goto which computed the destination address without a table. It worked something like this: each case was given four instructions, so you could compute the address of the case with a shift+add. If a case needed more than four instructions, it would just use one of those to jump.

On the topic of other VMs, Lua 5.4 (released last year) now uses the computed goto by default.

This article is almost ten years old, I believe that modern compilers all create efficient dispatch tables without all of this manual work - even ten years ago I don’t think large switch statements were a problem area. Most emulators use these heavily. But I think it does give an idea what is going on behind the scenes. There are a number of ways compilers could implement this based on the number of cases and how dense they are. I know that go will organize sparse case values into a sorted array and do a binary search to find where to jump. I think Perl uses hash tables for the same purpose.

It'd be interesting to analyze more languages. C# .NET Core for example still couldn't handle large switch statements well as of a year ago.

If you have a while-loop wrapping a switch statement, will most modern compilers put dispatch code at the end of every case, to help the branch predictor (actually, branch target buffer)? Even if modern branch target buffer entries were dependent upon the target of the previous indirect branch (in the switch statement), if any of your bytecodes go off and do some C++ virtual dispatches, it will quickly swamp any extra context the BTB logic may have.

As of today, Computed goto is still much faster than switch, both on x64 or arm64.

I wrote more or less the same interpreter in C using computed goto and in C++ without if anyone's interested. The C-version is several times faster, and I'm pretty sure the dispatch method plays a part.

The reason I went with functions instead in C++ is to allow plugging new opcodes into the instruction set without updating the dispatch loop.

https://github.com/codr7/liblg

https://github.com/codr7/liblgpp

Given the common advice to _always_ include a "default" label in your switches, I had formed the impression that entering a default-less switch with a value that doesn't have a matching case would result in undefined behaviour. This is not the case: it will simply do nothing.

In my experience, this dogmatic advice is often counterproductive.

If this is a switch that is reasonably defended (internal API, etc.) then leaving off a default in a fixed enumeration type switch (where you want to hit _every_ switch case value possible) is ideal.

Most modern processors will warn (or -Werror, as everyone should be using these days) if one of the enum constants is missing, reducing the surface area for logic bugs.

If you are really paranoid about out-of-bounds values in a switch statement, then insert an assert() after the statement itself with a negated string literal, e.g. assert(!"invalid switch value");

This is a pretty reasonable approach for code that, again, is reasonably defended against faulty inputs or working with some degree of guarantee. If I'm not mistaken, often times such switch statements are even optimized to jump tables at compile time, too - namely if there are small/few/no gaps in the case values.

IMHO one of the major failures of the ISO-C process that they still didn't manage to standardize computed goto.

Normally I don't agree with such statements, but in this case I do. Computed goto is very C-like in nature and has clear and concrete benefits. Further, it can be replicated on any architecture I'm personally aware of, and knowing how LLVM and other compiler infrastructure is designed, is a fairly trivial thing to implement.

I'd be curious to hear why it was never standardized. It seems like low hanging fruit to me.

Reply on news.ycombinator.com