Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Branch Prediction and the Performance of Interpreters – Don’t Trust Folklore

hal.inria.fr

Post reply on HN
Print view View original

41–50 of 56 posts

Re: Branch Prediction and the Performance of Interpreters – Don’t Trust Folklore

#41

Post by jcranmer »

chrisdevereux wrote: post #13

Is there a reason that machine languages don't allow the programmer/compiler/runtime to explicitly control the CPU's cache & instruction pipeline? Presumably they have access to much better information about the code's intent and future behaviour than the cpu does.

Ever hear of this process called MIPS? The design behind MIPS (Machine without Interlocking Processor Stages) was originally based on the notion that every time the hardware needed to introduce a bubble, the CPU would instead continue executing instructions--giving rise to load slots and branch delay slots.

The resulting finds from practice were that these new slots were hard to fill (i.e., mostly nops), and, instead of making hardware simpler, they made hardware much more complex if you ever decide to adjust microarchitectural details.

There is some limited support for poking the cache, though (prefetching, flushes, bypass, load streaming), but all of those techniques tend to be very coarse-grained.

Re: Branch Prediction and the Performance of Interpreters – Don’t Trust Folklore

#42

Post by rurban »

This research misses a few important points.

First, the fastest interpreter is never switch or "jump threading" (i.e. computed goto) based. It is either based on passing the next pointer from one opcode to the next (e.g. perl5) or using an opcode array (lua). Those two cache much better and don't need the dispatch overhead with a jump table at all. Not talking about asm tuned interpreter dispatch yet, which count as best of the best.

Second, the famous cited Ertl paper mostly suggested to use smaller opcodes to influence the icache. Lua and luajit do this with one-word ops and blow all other interpreters away.

Using the computed goto extension only helps in bypassing the out of bounds check at the start of the switch dispatch, and gains the famous 2-3%, and less on more modern CPU's. When talking about the differences, the differences should be explained.

Summary: This research result is not useful for state of the art interpreters, only for conventional slow interpreters. And for those the result should be ignored at all, as much better interpreter speedup techniques exist, not noted in this paper.

Re: Branch Prediction and the Performance of Interpreters – Don’t Trust Folklore

#43

Post by cfallin »

chrisdevereux wrote: post #13

Is there a reason that machine languages don't allow the programmer/compiler/runtime to explicitly control the CPU's cache & instruction pipeline? Presumably they have access to much better information about the code's intent and future behaviour than the cpu does.

In addition to what others have said (mainly, it would be specific to a particular version of the CPU, which is probably the biggest thing -- imagine if no x86 binary older than ~1 year could run on your chip), one more point:

The programmer doesn't necessarily have better knowledge than the CPU, because the programmer can't see or respond to runtime behavior. There are a lot of cases where behavior is input-data-dependent, or simply too complicated to reason about analytically a-priori. The big wins in computer architecture over the past two decades have all been in mechanisms that adapt dynamically in some way: dynamic instruction scheduling (out-of-order), branch prediction based on history/context, all sorts of fancy cache eviction/replacement heuristics, etc.

Itanium tried "VLIW + compiler smarts" and the takeaway, I think, was that it was just too hard to build good enough static analysis to beat a conventional out-of-order CPU.

Re: Branch Prediction and the Performance of Interpreters – Don’t Trust Folklore

#44

Post by loup-vaillant »

rurban wrote: post #42

This research misses a few important points. First, the fastest interpreter is never switch or "jump threading" (i.e. computed goto) based. It is either based on passing the next pointer from one opcode to the next (e.g. perl5) or using an opcode array (lua). Those two cache much better and don't need the dispatch overhead with a jump table at all. Not talking about asm tuned interpreter dispatch yet, which count as…

> passing the next pointer from one opcode to the next (e.g. perl5)

> using an opcode array (lua)

Would you perchance have a couple links explaining what those are? A quick search on my end didn't turn up anything useful.

Re: Branch Prediction and the Performance of Interpreters – Don’t Trust Folklore

#45

Post by loup-vaillant »

sklogic wrote: post #19

The article is missing one important difference between a primitive Python use of jump threading and the OCaml bytecode interpreter which pre-compiles the bytecode into a threaded code. A difference in performance between these two is huge.

> the OCaml bytecode interpreter […] pre-compiles the bytecode into a threaded code

Wait a minute, how is that even possible? Or rather, what do you mean?

Here's my layman's view of things: the bytecode is basically a string of opcodes. The interpreter has to look up the opcode before executing it somehow. And it can be threaded, or use an ordinary switch, or perform some other bizarre optimization I don't understand.

But what does it mean for the bytecode itself to be compiled into a threaded form?

Re: Branch Prediction and the Performance of Interpreters – Don’t Trust Folklore

#46

Post by sklogic »

loup-vaillant wrote: post #45
sklogic wrote: post #19

The article is missing one important difference between a primitive Python use of jump threading and the OCaml bytecode interpreter which pre-compiles the bytecode into a threaded code. A difference in performance between these two is huge.

> the OCaml bytecode interpreter […] pre-compiles the bytecode into a threaded code Wait a minute, how is that even possible? Or rather, what do you mean? Here's my layman's view of things: the bytecode is basically a string of opcodes. The interpreter has to look up the opcode before executing it somehow. And it can be threaded, or use an ordinary switch, or perform some other bizarre optimization I don't understand…

> Wait a minute, how is that even possible? Or rather, what do you mean?

It means that the stream of bytecodes (32-bit numbers in OCaml) is replaced with the corresponding label addresses (for 64-bit hosts - addresses minus a fixed offset) once. Then the execution is trivial. This is called "indirect threaded code" [1] and used a lot in Forth implementations, for example.

See the definition of the "Next" macro in interp.c [2] for details.

[1] https://en.wikipedia.org/wiki/Threaded_code#Indirect_threadi...

[2] https://github.com/ocaml/ocaml/blob/trunk/byterun/interp.c

EDIT: if you wonder where the actual threading is done, see https://github.com/ocaml/ocaml/blob/trunk/byterun/fix_code.c

Re: Branch Prediction and the Performance of Interpreters – Don’t Trust Folklore

#47

Post by sliverstorm »

chrisdevereux wrote: post #13

Is there a reason that machine languages don't allow the programmer/compiler/runtime to explicitly control the CPU's cache & instruction pipeline? Presumably they have access to much better information about the code's intent and future behaviour than the cpu does.

They have been produced, but x86's dominance has always been about fungibility and idiot-proofness while maintaining acceptable performance. It's never been the fastest possible or cheapest possible architecture; it's the architecture whose success has been built upon hiding all the complicated bits behind the curtains, so that software people can worry about software and not hardware.

There actually are some performance upsides to that too. It allows the chip architects to radically change the underpinnings of the chip with impunity, doing whatever works best on the current process node and using the latest advancements from computing research.

Re: Branch Prediction and the Performance of Interpreters – Don’t Trust Folklore

#49

Post by mamcx »

rurban wrote: post #42

This research misses a few important points. First, the fastest interpreter is never switch or "jump threading" (i.e. computed goto) based. It is either based on passing the next pointer from one opcode to the next (e.g. perl5) or using an opcode array (lua). Those two cache much better and don't need the dispatch overhead with a jump table at all. Not talking about asm tuned interpreter dispatch yet, which count as…

So, any example (easy to understand? well explained?, ie: apart to study a whole codebase as luajit) in what are the state of art interpreters?

Re: Branch Prediction and the Performance of Interpreters – Don’t Trust Folklore

#50

Post by loup-vaillant »

sklogic wrote: post #46
loup-vaillant wrote: post #45

Earlier quoted context omitted.

> the OCaml bytecode interpreter […] pre-compiles the bytecode into a threaded code Wait a minute, how is that even possible? Or rather, what do you mean? Here's my layman's view of things: the bytecode is basically a string of opcodes. The interpreter has to look up the opcode before executing it somehow. And it can be threaded, or use an ordinary switch, or perform some other bizarre optimization I don't understand…

> Wait a minute, how is that even possible? Or rather, what do you mean? It means that the stream of bytecodes (32-bit numbers in OCaml) is replaced with the corresponding label addresses (for 64-bit hosts - addresses minus a fixed offset) once. Then the execution is trivial. This is called "indirect threaded code" [1] and used a lot in Forth implementations, for example. See the definition of the "Next" macro in int…

OK, I'm rephrasing to make sure I understand.

In the ordinary, C compliant switch code, you would do this:

  int instructions[] = { /* bytecode */ };

  // main loop
  int* ip = instructions;
  while(1) {
    switch (*ip) {
    case 1: /* instruction 1 */ break;
    case 2: /* instruction 2 */ break;
    case 3: /* instruction 3 */ break;
    /* etc */
    }
    ip++; /* goto next instruction. beware jumps */
  }
With a jump threaded implementation, you would do this instead:

  int instructions[] = { /* bytecode */ };

  void jump_table[] = {
    &&lbl1,
    &&lbl2,
    &&lbl3,
    /* etc */
  };

  // main loop
  int* ip = instructions;
  goto *jump_table[*ip];
  lbl1: /* instruction1 */ ip++; goto *jump_table[*ip];
  lbl2: /* instruction2 */ ip++; goto *jump_table[*ip];
  lbl3: /* instruction3 */ ip++; goto *jump_table[*ip];
  /* etc */
Which means, instead of having the compiler constructing a jump table under the hood, I do this myself, and get the benefit of jumping from several locations instead of just one. But I still look up that table. Now the indirect threading you speak of:

  int instructions[] = { /* bytecode */ };

  void jump_table[] = {
    &&lbl1,
    &&lbl2,
    &&lbl3,
    /* etc */
  };

  // translating bytecode into adresses
  void* labels[] = malloc(sizeof(void*) * nb_instructions);
  for (uint i = 0; i
If I got that correctly, instead of accessing the jump table at some random place, I only access the label table in a much more linear fashion, saving one indirection and some memory access in the process —this should relieve some pressure off the L1 cache.

Did I get that right?

Post reply on HN