Squeezing a Little More Performance Out of Bytecode Interpreters
stefan-marr.de
stefan-marr.de
1. "it avoids an extra jump to the top of the loop at the end of each bytecode" – but the top of the loop is a known, hardcoded value, so the prefetcher should be able to take the unconditional jump at little or no cost.
2. "we have multiple dispatch points instead of a single one" which is supposed to assist branch prediction - I made a big "oooh!" at that, but thinking it over, the target of the GOTO is computed each time eg.
push_local:
void* target = targets[index];
index += /* ... */
goto *target;
Perhaps if you wanted speed then picking out common bits of code and inlining it would cut down on the branches and possibly make the code more compact, for better cache use. (that's a bit petty though, it's clearly not the target of their research).
I suppose if you had some spare byte codes left over and you have a commonly used instruction, perhaps 'add', you might have a few different versions of add (add1, add2, add3) which behaved identically but were scattered through the 'source' code, to help the branch predictor even more.
(Source: have written a JVM interpreter with the naive approach that is approximately that much slower than the OpenJDK with disabled JIT compiler. It was later also confirmed by people working on the actual JVM that that’s roughly the order of difference between the two approaches. Unfortunately I can’t find a great article on the topic right now (google is beyond useless recently)).
The article is about a further small improvement over this much larger and commonly implemented one.
Do you have benchmarks on current gen hardware that suggest that the code complexity results in a measurable difference in outcomes?
Also, I don’t think that it could even in principle be efficiently branch predicted — you are basically doing a memory read, jump conditionally based on that, jump back, do another memory read vs memory read, jump there, memory read, jump there. There is one less jump involved here, so any form of improved branch prediction would also enhance this second form as well.
I found this, you might be able to benchmark it yourself if you have better hardware: https://github.com/vshymanskyy/interp
No, cos I said "the benchmarks speak for themselves". But I am trying to understand why it's better and under what circumstances.
"...and the goto version is 25% faster than the switch version...
Comments inside the CPython implementation note that using computed goto made the Python VM 15-20% faster"
(Which isn't the 2-4x speed up that you found. Maybe you meant 20-40%?).
In that link they say that part of the reason is because of the bounds checking which is automatically done by the switch statement.
What I'm struggling with which is no doubt down to my lack of knowledge, is why it should be significantly faster (if you take out or disable the bounds checking added by the switch). I can see there would be some advantage in spreading out the jumps so the branch predictor could work a bit better, but I am surprised at the speed up. I guess mispredicted branches are so expensive that doing just a little bit better could account for the difference, but I am trying to understand it.
[1] http://lua-users.org/lists/lua-l/2011-02/msg00742.html
[2] https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e...
Anyway, great pair of links, much appreciated!
Basically, the code handler ordering does not generalise well across benchmark nor processor, so to get the speedup they see, you'd need a specialised interpreter for your specific benchmark and processor. That puts this into the "interesting, but not very practical" category.
The «key problems» are also discussed in the introduction of the paper at the top of page 2 - including why it’s practical in their context.
Also in the paper, they say speedups based on optimizing a subset of benchmarks generalize to other benchmarks as well, but not across environments.
Last I checked, starting with an «optimizing your environment» task, is far from being considered «not very practical»
is a good summary
> improved the execution speed of the program for which the order was optimized between 0.8% and 23.0% with 7.7% on average.
Single-digit speedup is not worth it IMO, and the wide range (<1% - 23%) probably means that you specialize for some tasks at the expense of other types of tasks, which is not for everyone's interpreter.
One use I can see for it is to compile multiple inner loops and have the interpreter switch between them (probably manually), if that can get us the yummy 20% speedup. Core primitives and dispatchers are usually not the biggest part of interpreters, after all. Maybe in this scenario the core primitives could also benefit from small semantic changes, like no bounds checking for instance.
would you reject a single-digit pay rise? :)
Owning and maintaining a trainer in your build system would be a form of technical debt.
interesting read.