4 ms·
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
by 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 agoIIUC 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 agoRight 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 agoI 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 agoYou 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 agoOp 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.