Hacker News Reader

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-e... (see "Doing less per iteration")

I've tried using "default: __builtin_unreachable()" but this doesn't seem to help.

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.

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

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

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

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.

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

How about the chip in any recent model iPad or iPhone?

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.

Wouldn't the VM violate the rules even if it's just an interpreter?

You're allowed to bundle a custom VM for any language if it only executes code included with the app itself.

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

It seems likely that Python is targeting a wider field than just the latest few generations of desktop/server CPUs.

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

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.

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.