Re: Opcode handler dispatch in an interpreter: Implementing switch on OpCode.

On 05/10/2017 17:29, Robert Jacobson wrote:
> I am trying to wrap my mind around the issue of dynamic dispatch in the
> context of switching on opcode in a bytecode interpreter. I came across Julian
> Squires' recent well-cited blog post (via r/programming), "Are Jump Tables
> Always Fastest?" ...


> Switching on opcode number is a special case of a general switch.
> Specifically:
> 1. opcodes are dense and contiguous;
> 2. opcodes typically take values over a relatively small range.
> For example, CPython's opcodes range from 1 to 161 (excepting EXCEPT_HANDLER).
> The jump table is thus a perfect hash: We need only store the addresses of the
> opcode handler functions in a smallish table and use the opcode value as an
> index into the table. Given (1) and (2), it's not clear to me that, say, a
> binary search with Log_2(161) ~ 8 comparisons is better than the lookup table.


I don't understand what this binary search is looking for here. You've
got an index of 1 to 161, and a table of addresses index from 1 to 161;
what more is needed? You just do an index operation to find the address
you have to get to to deal with that byte-code.


> Is that really what the recent literature is saying? Are concerns about cache
> misses really valid for a table of 161 addresses? Is a load instruction that
> much more expensive than comparison instructions with branch prediction?
>
> I also have a question about optimization. Testing for opcode values in order
> of frequency of occurrence optimizes for the 1-gram entropy of opcodes. While
> we expect the conditional entropy of a given opcode to be high, I would still
> think that a bigram optimization would still be a benefit. One wouldn't have
> to compute all of the conditional probability distributions for every opcode
> to do this. Just do it for the statistically most common bigrams, including
> checks of the next opcode against the most probable successor in the current
> opcode's handler code. Is this ever done in practice? Why or why not?


Are you trying to implement something or doing academic research?


I can only give my own practical experience based on four kinds of
dispatchers I've used:


(1) Function-pointer dispatcher.


Within the byte-code program, byte-code indices (c. 1 to 200 in my
interpreter) are replaced before starting by the actual address of the
corresponding handler. Then there is a very simple loop that that passes
control direct to the handler for the current byte-code.


(2) Switch-based dispatcher.


Indices are retained within the byte-code, and used to jump to one of
the 200 different case-labels (in C jargon). Most of those will then
perform a function-call (but if using C, that is likely to inline those
functions)


(3) Label-pointer dispatcher.


Similar to the block of 200 case-labels, there are 200 ordinary labels,
each of which will again call the handler (which may again be inlined).


Within the byte-code, each index is replaced by the address of each
label (if using C, it needs support for this feature).


(4) Thread-code dispatcher.


Within the byte-code, each index is replaced by the address of each
handler, each of which is now a threaded-code function (jump into the
function, jump out again straight to the next handler).


In terms of performance, (1) was usually the slowest, (2) faster, and
(3) fastest.


A direct comparison with (4) is difficult, because this dispatcher was
written as an ASM-based overlay on top of (1). If no other optimisations
are done, then this overlay (4) ends up slightly slower than (1).


(In practice, (4) will directly handle many simple byte-codes in in-line
assembly, and it will keep global values resident in registers as much
as it can. So it generally ends up the fastest of all.)


The overheads of byte-code dispatch depend also on the kind of language
being interpreted. For my dynamic one which needs also to deal with
type-dispatch, and where some opcodes can do a lot of work, they might
not be as significant compared with lower-level languages.


(I've since dropped dispatchers (2) and (3), and use either (1) or (4).)


--
bartc

Return to the comp.compilers page.
Search the comp.compilers archives again.