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

51–56 of 56 posts

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

#51

Post by sanderjd »

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…

Since you seem to know a lot about this, which popular interpreters would you say are "state of the art" and which are "conventional slow"? It seems that lua and luajit (and perhaps perl5?) are in the former category. Is everything else in the latter?

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

#52

Post by sklogic »

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

Earlier quoted context omitted.

> 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 w…

Exactly, you got it right. One indirection less, and no jump table in the cache. And CPUs are very well optimised for this kind of indirect jumps, because of vtables.

There is also one step further - emit the actual jump instructions, making a direct threaded code. It is a bit more complicated and not very portable, but if you want to squeeze all the cycles you can it's still an easy and fast option before resorting to a full-scale compiler.

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

#53

Post by ehaliewicz2 »

sklogic wrote: post #52
loup-vaillant wrote: post #50

Earlier quoted context omitted.

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 w…

Exactly, you got it right. One indirection less, and no jump table in the cache. And CPUs are very well optimised for this kind of indirect jumps, because of vtables. There is also one step further - emit the actual jump instructions, making a direct threaded code. It is a bit more complicated and not very portable, but if you want to squeeze all the cycles you can it's still an easy and fast option before resorting…

I think direct threading is usually implemented just by reducing the indirection another level,

e.g.

  goto *lp
rather than

  goto **lp
You could implement an interpreter with generated JMP instructions, which might be called direct-threading, but at least in the forth world, where most jumps are to nested user-defined subroutines, subroutine-threading using JSR instructions is typically used.

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

#54

Post by caf »

Is it really true that "Jump threading, though, can- not be implemented in standard C."? Surely, each computed goto:

  goto *labels[*vpc++];
can be replaced with a full copy of the switch:

  switch (*vpc++) { case OP_ADD: goto ADD; case OP_SUB: goto SUB; }
..and hopefully the compiler will replace the entries for the cases in the switch's jump table with the goto targets.

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

#55

Post by sklogic »

cfallin wrote: post #43
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-dep…

The problem with the OoO is that it's a way too expensive (in terms of power and area) in many cases. You won't ever see OoO in GPUs and DSPs, unlikely in the microcontrollers. So, VLIW and the other "stupid core, smart compiler" approaches are still legitimate and will always remain valuable.

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

#56

Post by cfallin »

sklogic wrote: post #55
cfallin wrote: post #43

Earlier quoted context omitted.

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-dep…

The problem with the OoO is that it's a way too expensive (in terms of power and area) in many cases. You won't ever see OoO in GPUs and DSPs, unlikely in the microcontrollers. So, VLIW and the other "stupid core, smart compiler" approaches are still legitimate and will always remain valuable.

Yup, in some domains it definitely still makes sense. GPUs work well for highly-data-parallel applications (they're essentially vector machines, modulo branch divergence) and VLIW-style DSPs work because the code is numerical and easy to schedule at compile time.

I've worked mostly in the "need performance as high as possible for general-purpose code" domain, so I may be biased!

Post reply on HN