4 ms·

This is my area of interest and I know a little about interpretation/compiling. I'm a little dubious about this (which I shouldn't be because the benchmarks spe

This is my area of interest and I know a little about interpretation/compiling. I'm a little dubious about this (which I shouldn't be because the benchmarks speak for themselves). But a couple of doubts. 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; So I don't see how the branch predictor has that much to work on. I suppose it cuts down on the possible number of targets so it's more likely to predict correctly, and reading again, that's exactly what they say "we may only see a subset of bytecodes, which increases the chance that the processor can predict the jump correctly". Hmm, I'm a bit surprised that makes that much of a difference but a quick look at the benchmarks suggest they are really pretty small. I'd expect the technique to lose its speedup as the amount of code grows. 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.

deleted 3y ago
[deleted]
superdimwit 3y ago
On 1: this small amount of overhead matters because the amount of work you do on each opcode can be tiny. The extra jump could be 20% of your runtime! On 2: yes, this helps the indirect branch target predictor. In a real program you’ll often get repeated sequences of opcodes (increment, then compare) that can be predicted. These branch predictors can be pattern based.
kaba0 3y ago
So you are questioning the effect of direct threading code? Because I assure you, that has a significant impact compared to the naive switch-eval loop, on the order of 2-4x from my experience. (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.
- hinkley 3y ago
  The last new information I had on this was that direct threading stopped being a distinct perf advantage when branch predictors got more sophisticated (able to predict indirect branches). Do you have benchmarks on current gen hardware that suggest that the code complexity results in a measurable difference in outcomes?
  - kaba0 3y ago
    I wrote that interpreter roughly a year ago — my computer is definitely not the most up-to-date (the CPU is an intel i5-4690), but I would be surprised if the difference would have disappeared. 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 https://github.com/vshymanskyy/interp
  - ghusbands 3y ago
    Even if it were only the same speed on current gen hardware, most users are on older hardware, anyway, so it would still be a win unless it actually reduced performance.
ghusbands 3y ago
It's odd that this is your area of interest and yet you don't know of the commonly-used direct/indirect threading techniques. Many interpreters, including a famously fast one [1], use them, and benchmarks have repeatedly shown it to be a significant gain [2]. [1] http://lua-users.org/lists/lua-l/2011-02/msg00742.html http://lua-users.org/lists/lua-l/2011-02/msg00742.html [2] https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e...
- _a_a_a_ 3y ago
  My interest is in compilers much more than interpreters, I haven't come across this threaded style before, my interest in languages and compilers is something I've barely used at work, and everything after university that I've learnt has been self-taught. There are inevitably going to be holes. Anyway, great pair of links, much appreciated!

deleted 3y ago

[deleted]

superdimwit 3y ago

On 1: this small amount of overhead matters because the amount of work you do on each opcode can be tiny. The extra jump could be 20% of your runtime! On 2: yes, this helps the indirect branch target predictor. In a real program you’ll often get repeated sequences of opcodes (increment, then compare) that can be predicted. These branch predictors can be pattern based.

kaba0 3y ago

So you are questioning the effect of direct threading code? Because I assure you, that has a significant impact compared to the naive switch-eval loop, on the order of 2-4x from my experience. (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.

hinkley 3y ago
The last new information I had on this was that direct threading stopped being a distinct perf advantage when branch predictors got more sophisticated (able to predict indirect branches). Do you have benchmarks on current gen hardware that suggest that the code complexity results in a measurable difference in outcomes?
- kaba0 3y ago
  I wrote that interpreter roughly a year ago — my computer is definitely not the most up-to-date (the CPU is an intel i5-4690), but I would be surprised if the difference would have disappeared. 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 https://github.com/vshymanskyy/interp
- ghusbands 3y ago
  Even if it were only the same speed on current gen hardware, most users are on older hardware, anyway, so it would still be a win unless it actually reduced performance.

ghusbands 3y ago

It's odd that this is your area of interest and yet you don't know of the commonly-used direct/indirect threading techniques. Many interpreters, including a famously fast one [1], use them, and benchmarks have repeatedly shown it to be a significant gain [2]. [1] http://lua-users.org/lists/lua-l/2011-02/msg00742.html http://lua-users.org/lists/lua-l/2011-02/msg00742.html [2] https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e...

_a_a_a_ 3y ago
My interest is in compilers much more than interpreters, I haven't come across this threaded style before, my interest in languages and compilers is something I've barely used at work, and everything after university that I've learnt has been self-taught. There are inevitably going to be holes. Anyway, great pair of links, much appreciated!