5 ms·

Computed goto for efficient dispatch tables (2012)

47 points by henning 6y ago

rurban 6y ago
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.
- felixr 6y ago
  IIUC your first option is what is known as threaded code or threaded interpreter https://en.m.wikipedia.org/wiki/Threaded_code https://en.m.wikipedia.org/wiki/Threaded_code
  - deleted 6y ago
    [deleted]
  - jashmatthews 6y ago
    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.
- jashmatthews 6y ago
  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.
- KMag 6y ago
  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.
  - rurban 6y ago
    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.
- junon 6y ago
  > 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.
codeulike 6y ago
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.
- Doctor_Fegg 6y ago
  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.
- treeman79 6y ago
  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.
nn3 6y ago
IMHO one of the major failures of the ISO-C process that they still didn't manage to standardize computed goto.
- junon 6y ago
  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.
ufo 6y ago
On the topic of other VMs, Lua 5.4 (released last year) now uses the computed goto by default.
zxcvbn4038 6y ago
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.
- hansvm 6y ago
  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.
- KMag 6y 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.
- chj 6y ago
  As of today, Computed goto is still much faster than switch, both on x64 or arm64.
souprock 6y ago
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.
klodolph 6y ago
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.
codr7 6y ago
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/liblg https://github.com/codr7/liblgpp https://github.com/codr7/liblgpp
nemetroid 6y ago
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.
- junon 6y ago
  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.
henning 6y ago
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 https://github.com/fearofcode/labeled_goto_test
- gopalv 6y ago
  > 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 https://news.ycombinator.com/item?id=15397109
  - monocasa 6y ago
    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).
  - jonstewart 6y ago
    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.

47 points by henning 6y ago

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.

felixr 6y ago
IIUC your first option is what is known as threaded code or threaded interpreter https://en.m.wikipedia.org/wiki/Threaded_code https://en.m.wikipedia.org/wiki/Threaded_code
- deleted 6y ago
  [deleted]
- jashmatthews 6y ago
  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.
jashmatthews 6y ago
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.
KMag 6y ago
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.
- rurban 6y ago
  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.
junon 6y ago
> 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.

codeulike 6y ago

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.

Doctor_Fegg 6y ago
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.
treeman79 6y ago
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.

nn3 6y ago

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

junon 6y ago
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.

ufo 6y ago

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

zxcvbn4038 6y ago

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.

hansvm 6y ago
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.
KMag 6y 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.
chj 6y ago
As of today, Computed goto is still much faster than switch, both on x64 or arm64.

souprock 6y ago

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.

klodolph 6y ago

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.

codr7 6y ago

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/liblg https://github.com/codr7/liblgpp https://github.com/codr7/liblgpp

nemetroid 6y ago

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.

junon 6y ago
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.

henning 6y ago

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 https://github.com/fearofcode/labeled_goto_test

gopalv 6y ago
> 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 https://news.ycombinator.com/item?id=15397109
- monocasa 6y ago
  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).
- jonstewart 6y ago
  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.