Comment by gopalv | Hacker News Reader

Comment by gopalv | Hacker News Reader

Parent Full thread

> 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

> 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.

Reply on news.ycombinator.com