4 ms·

> Threaded code should have better branch prediction behavior than a jump table with a single dispatch point This is not the case anymore, at least for modern

by ufo 9y ago

> Threaded code should have better branch prediction behavior than a jump table with a single dispatch point This is not the case anymore, at least for modern Intel processors. Starting with the Haswell micro-architecture, the indirect branch predictor got much better and a plain switch statement is just as fast as the "computed goto" equivalent. Be wary of any references about this that are from before 2013. For more info, I would recommend "Branch Prediction and the Performance of Interpreters - Don’t Trust Folklore", by Rouhou, Swamy and Seznec. Pdf link: https://hal.inria.fr/hal-01100647/document https://hal.inria.fr/hal-01100647/document > although indirect branch prediction should help even the field. Indeed :) ----- Fun story: I experimented with adding indirect threading to the Lua interpreter and was excited to find an improvement of up to 30% on some selected microbenchmarks (running on my IvyBridge workstation). But the improvement dropped to 0% when I tested it on a machine with a Haswell processor. Measuring with perf indicated that the improved branch predictor was indeed responsible for this.

gopalv 9y ago
> Starting with the Haswell micro-architecture, the indirect branch predictor got much better Looking at the results I get, I feel like there's also an inlined switch lookup so that the CPU can get ahead of it. Basically if I had to the same, I would try to inline the top of the switch down into the break; jump directly instead of jumping to a common location. So now the operator case ends with looks like op1_offset: <invariant=pc> (operator code) pc2 = pc+1 jmp_off = ops_table+pc2 jmp jmp_off Because there's no jump between the operator and the pc2 = pc+1, the CPU can compute jmp_off during any time from entering the op1_offset (and this is why you have an HLT opcode, also 32 bit opcodes are much more compact than 64 bit direct threaded CGOTO). I'm not sure if the inlining of the jmp to_top_of_loop can be done by the compiler itself or if it is done by the lower levels of the CPU. Compilers used to ruin the immediate dispatch of computed goto, to extract the common jump code - I've had to force GCC to leave my CGOTO alone to make this work before[1]. [1] - http://notmysock.org/blog/php/optimising-ze2.html http://notmysock.org/blog/php/optimising-ze2.html
- cwzwarich 9y ago
  > Because there's no jump between the operator and the pc2 = pc+1, the CPU can compute jmp_off during any time from entering the op1_offset (and this is why you have an HLT opcode, also 32 bit opcodes are much more compact than 64 bit direct threaded CGOTO). If you're relying heavily on the indirect branch predictor of a Haswell-class CPU for performance, the exact details of computing the address probably don't matter that much. The CPU predicts the branch and continues executing, validating the prediction later. While it's definitely possible to exhaust some internal CPU resource waiting for old predictions to be validated, that is unlikely to be affected much by minor scheduling changes of the address generation sequence. > I'm not sure if the inlining of the jmp to_top_of_loop can be done by the compiler itself or if it is done by the lower levels of the CPU. A C compiler can definitely do it if it so desires, but it would also have to inline the required bounds check in addition to the indirect branch. If the compiler properly scheduled this branch, the fallthrough would always be success, and it would just be an always-false branch away that any branch predictor can handle. Of course, you could hit a CPU resource limit for outstanding branches and eventually stall, even if the branch is always predicted. I'm not aware of any currently available out-of-order CPU that does the sort of linear trace formation that might be considered "inlining" of the switch logic. Pentium 4 famously used such a mechanism.
haberman 9y ago
That's really good to know. It's still annoying though that C semantics apparently require there to be a bounds-check for every iteration of the switch(): https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... (see "Doing less per iteration") I've tried using "default: __builtin_unreachable()" but this doesn't seem to help.
- phkahler 9y ago
  IIRC GCC is capable of dropping the check if it knows the possible range of the switch variable. An example would be using a single byte and having all 256 possibilities exist in the switch. Another would be switch (x & 7) with 8 cases. I have not checked in a while, but I spent a lot of time on code with this issue. It's at the core of my ray tracer of all things.
- gpderetta 9y ago
  There is no requirement for range checking in the C standard. That was a missed optimization that was only very recently fixed on GCC: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51513 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51513
tokenrove 9y ago
Yeah, I should have finished this article when it was still fresh. Hardware always seems to catch up with codegen from the '70s. (Thanks for the excellent paper reference.)
civility 9y ago
How about on ARM? Is its branch prediction keeping pace? I'm curious because you can't JIT to native on iOS, so finding the best way to build a VM there is interesting.
- microcolonel 9y ago
  > Is its branch prediction keeping pace? Well, most ARM cores are not designed by ARM Holdings, and even among their own cores there are many models. The answer to this question depends entirely on the specific design.
  - civility 9y ago
    How about the chip in any recent model iPad or iPhone?
    - microcolonel 9y ago
      Who knows, it would be trivial to check if Apple allowed customers to run an operating system of their choice. I don't have the patience to operate one.
- ant6n 9y ago
  Wouldn't the VM violate the rules even if it's just an interpreter?
  - spicyj 9y ago
    You're allowed to bundle a custom VM for any language if it only executes code included with the app itself.
ngrilly 9y ago
Thank you so much for sharing this paper, which answered all my questions on the opportunity of using "computed goto" in interpreters like Python, considering recent CPU architectures.
vilda 9y ago
This myth is even in Python source code[1] However, since the indirect jump instruction is shared by all opcodes, the CPU will have a hard time making the right prediction for where to jump next (actually, it will be always wrong except in the uncommon case of a sequence of several identical opcodes). [1] https://github.com/python/cpython/blob/ff8ad0a576c6cf375e68276e614e551b3b759254/Python/ceval.c#L825 https://github.com/python/cpython/blob/ff8ad0a576c6cf375e682...
- caf 9y ago
  It seems likely that Python is targeting a wider field than just the latest few generations of desktop/server CPUs.
- ufo 9y ago
  I think that this might just be because that code is a bit older now. I actually have to thank the documentation there for explaining all the flags you need to turn on GCC to get the computed goto to work. By default gcc's optimizer will mess things up and I would have never figured out the flags by myself to be able to run my benchmarks
simias 9y ago
That's super interesting, thank you for that. Although every time I write an interpreter I'm frustrated that I can't simply pass this information directly to the CPU instead of having it guess haphazardly where the indirect branch will lead to. Modern CPUs let us control the prefetcher, why not the branch predictor? I'm currently working on an MIPS emulator where I can predict the next executed opcode with perfect accuracy, yet I have no way to give this information to the processor and have to rely on the branch predictor to guess right.

by ufo 9y ago

gopalv 9y ago

> Starting with the Haswell micro-architecture, the indirect branch predictor got much better Looking at the results I get, I feel like there's also an inlined switch lookup so that the CPU can get ahead of it. Basically if I had to the same, I would try to inline the top of the switch down into the break; jump directly instead of jumping to a common location. So now the operator case ends with looks like op1_offset: <invariant=pc> (operator code) pc2 = pc+1 jmp_off = ops_table+pc2 jmp jmp_off Because there's no jump between the operator and the pc2 = pc+1, the CPU can compute jmp_off during any time from entering the op1_offset (and this is why you have an HLT opcode, also 32 bit opcodes are much more compact than 64 bit direct threaded CGOTO). I'm not sure if the inlining of the jmp to_top_of_loop can be done by the compiler itself or if it is done by the lower levels of the CPU. Compilers used to ruin the immediate dispatch of computed goto, to extract the common jump code - I've had to force GCC to leave my CGOTO alone to make this work before[1]. [1] - http://notmysock.org/blog/php/optimising-ze2.html http://notmysock.org/blog/php/optimising-ze2.html

cwzwarich 9y ago
> Because there's no jump between the operator and the pc2 = pc+1, the CPU can compute jmp_off during any time from entering the op1_offset (and this is why you have an HLT opcode, also 32 bit opcodes are much more compact than 64 bit direct threaded CGOTO). If you're relying heavily on the indirect branch predictor of a Haswell-class CPU for performance, the exact details of computing the address probably don't matter that much. The CPU predicts the branch and continues executing, validating the prediction later. While it's definitely possible to exhaust some internal CPU resource waiting for old predictions to be validated, that is unlikely to be affected much by minor scheduling changes of the address generation sequence. > I'm not sure if the inlining of the jmp to_top_of_loop can be done by the compiler itself or if it is done by the lower levels of the CPU. A C compiler can definitely do it if it so desires, but it would also have to inline the required bounds check in addition to the indirect branch. If the compiler properly scheduled this branch, the fallthrough would always be success, and it would just be an always-false branch away that any branch predictor can handle. Of course, you could hit a CPU resource limit for outstanding branches and eventually stall, even if the branch is always predicted. I'm not aware of any currently available out-of-order CPU that does the sort of linear trace formation that might be considered "inlining" of the switch logic. Pentium 4 famously used such a mechanism.

haberman 9y ago

That's really good to know. It's still annoying though that C semantics apparently require there to be a bounds-check for every iteration of the switch(): https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... (see "Doing less per iteration") I've tried using "default: __builtin_unreachable()" but this doesn't seem to help.

phkahler 9y ago
IIRC GCC is capable of dropping the check if it knows the possible range of the switch variable. An example would be using a single byte and having all 256 possibilities exist in the switch. Another would be switch (x & 7) with 8 cases. I have not checked in a while, but I spent a lot of time on code with this issue. It's at the core of my ray tracer of all things.
gpderetta 9y ago
There is no requirement for range checking in the C standard. That was a missed optimization that was only very recently fixed on GCC: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51513 https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51513

tokenrove 9y ago

Yeah, I should have finished this article when it was still fresh. Hardware always seems to catch up with codegen from the '70s. (Thanks for the excellent paper reference.)

civility 9y ago

How about on ARM? Is its branch prediction keeping pace? I'm curious because you can't JIT to native on iOS, so finding the best way to build a VM there is interesting.

microcolonel 9y ago
> Is its branch prediction keeping pace? Well, most ARM cores are not designed by ARM Holdings, and even among their own cores there are many models. The answer to this question depends entirely on the specific design.
- civility 9y ago
  How about the chip in any recent model iPad or iPhone?
  - microcolonel 9y ago
    Who knows, it would be trivial to check if Apple allowed customers to run an operating system of their choice. I don't have the patience to operate one.
ant6n 9y ago
Wouldn't the VM violate the rules even if it's just an interpreter?
- spicyj 9y ago
  You're allowed to bundle a custom VM for any language if it only executes code included with the app itself.

ngrilly 9y ago

Thank you so much for sharing this paper, which answered all my questions on the opportunity of using "computed goto" in interpreters like Python, considering recent CPU architectures.

vilda 9y ago

This myth is even in Python source code[1] However, since the indirect jump instruction is shared by all opcodes, the CPU will have a hard time making the right prediction for where to jump next (actually, it will be always wrong except in the uncommon case of a sequence of several identical opcodes). [1] https://github.com/python/cpython/blob/ff8ad0a576c6cf375e68276e614e551b3b759254/Python/ceval.c#L825 https://github.com/python/cpython/blob/ff8ad0a576c6cf375e682...

caf 9y ago
It seems likely that Python is targeting a wider field than just the latest few generations of desktop/server CPUs.
ufo 9y ago
I think that this might just be because that code is a bit older now. I actually have to thank the documentation there for explaining all the flags you need to turn on GCC to get the computed goto to work. By default gcc's optimizer will mess things up and I would have never figured out the flags by myself to be able to run my benchmarks

simias 9y ago

That's super interesting, thank you for that. Although every time I write an interpreter I'm frustrated that I can't simply pass this information directly to the CPU instead of having it guess haphazardly where the indirect branch will lead to. Modern CPUs let us control the prefetcher, why not the branch predictor? I'm currently working on an MIPS emulator where I can predict the next executed opcode with perfect accuracy, yet I have no way to give this information to the processor and have to rely on the branch predictor to guess right.