Branch Prediction and the Performance of Interpreters – Don’t Trust Folklore • Hacker News Board

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

#31

Post by acqq » Mon, Aug 10, 2015, 12:48 PM UTC

School-Cotton wrote: post #6

tl;dr for those who don't want to read the paper in detail: * Interpreters are conceptually a big switch(bytecode) statement in an infinite loop. They use various tricks to make it easier for the processor to predict the target of the next indirect branch * This previously had a dramatic impact on performance, because branch mispredictions are very expensive and it was difficult for the processor to predict them accu…

> various tricks

They actually present (approximately) a very simple construct that is used to speed the interpreters up:

   void labels[] = { &&ADD, &&SUB . . . };
   ...
   goto labels[ vpc++ ];
   ADD:
      ...
      goto labels[ vpc++ ];

instead of

    ...
    switch ( *vpc++ )
    {
    case ADD:
         ....
         break;
    case SUB:

It's not really hard. The only problem is that the former is not a standard C and not present in MSVC. See

http://stackoverflow.com/questions/6421433/address-of-labels...

"Erlang does (that) for building on Windows. They use MSVC for most of the build, and then GCC for one file to make use of the labels-as-values extension. The resulting object code is then hacked to be made compatible with the MSVC linker."

It obviously mattered enough for Erlang developers to use GCC even for just that critical piece of C code. It doesn't mean that it has to be regularly used in every code (not every switch is executed the way the main interpreter loop is).

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

#32

Post by loup-vaillant » Mon, Aug 10, 2015, 12:51 PM UTC

nly wrote: post #20

I wonder if indirect calls have also improved in latest generations? Anything vtable based would benefit.

Considering that Vtables are basically the same thing as a jump table in a switch… They have most probably improved in the same way.

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

#33

Post by acqq » Mon, Aug 10, 2015, 12:54 PM UTC

seanmcdirmid wrote: post #30

acqq wrote: post #27

Earlier quoted context omitted.

See the original article for the context. The question is actually if I'd use this: void labels[] = { &&ADD, &&SUB . . . }; ... goto labels[ vpc++ ]; ADD: ... goto labels[ vpc++ ]; instead of the plain switch if I'd write an interpreter in C (that's the topic of the article!) for a language that I know will be executed on ARM, AMD, Atom, you name it. The answer is: you bet I'd use the goto labels. That one particular…

My point was that eventually the technique will fall out if use of newer generations don't benefit from it. So say today X does no good on brand new hardware, then we still do X because not all hardware is new, but the value of doing X will definitely diminish over time. What is really annoying is when X is done to support an out-of-date CPU like a 386, to the detriment of CPUs that are actually currently in use. It…

> say today X does no good on brand new hardware

Is for you the "brand new hardware" your desktop which spends hundred of watts per hour or your mobile phone which has to survive the whole day without recharging his 5 Wh battery but still let you surf the web with all the stuff you take as given? Making optimizations that work good with lower wattage CPUs is a good thing, unless you limit yourself only to the non-battery devices.

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

#34

Post by loup-vaillant » Mon, Aug 10, 2015, 1:01 PM UTC

seanmcdirmid wrote: post #30

acqq wrote: post #27

Earlier quoted context omitted.

See the original article for the context. The question is actually if I'd use this: void labels[] = { &&ADD, &&SUB . . . }; ... goto labels[ vpc++ ]; ADD: ... goto labels[ vpc++ ]; instead of the plain switch if I'd write an interpreter in C (that's the topic of the article!) for a language that I know will be executed on ARM, AMD, Atom, you name it. The answer is: you bet I'd use the goto labels. That one particular…

My point was that eventually the technique will fall out if use of newer generations don't benefit from it. So say today X does no good on brand new hardware, then we still do X because not all hardware is new, but the value of doing X will definitely diminish over time. What is really annoying is when X is done to support an out-of-date CPU like a 386, to the detriment of CPUs that are actually currently in use. It…

There's one caveat: advanced branch prediction is probably not free. It probably costs a bit of silicon, even some energy. It may or may not actually matter (I'm no hardware designer), but if it does, we may have to make some hard choices, like a few more cores vs badass branch prediction.

It may not matter on X86 specifically, where out of order stuff dominates anyway. But it might matter for stuff like the Mill CPU architecture, for which energy efficiency and not wasting silicon is very important.

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

#35

Post by acqq » Mon, Aug 10, 2015, 1:09 PM UTC

loup-vaillant wrote: post #34

seanmcdirmid wrote: post #30

Earlier quoted context omitted.

My point was that eventually the technique will fall out if use of newer generations don't benefit from it. So say today X does no good on brand new hardware, then we still do X because not all hardware is new, but the value of doing X will definitely diminish over time. What is really annoying is when X is done to support an out-of-date CPU like a 386, to the detriment of CPUs that are actually currently in use. It…

There's one caveat: advanced branch prediction is probably not free. It probably costs a bit of silicon, even some energy. It may or may not actually matter (I'm no hardware designer), but if it does, we may have to make some hard choices, like a few more cores vs badass branch prediction. It may not matter on X86 specifically, where out of order stuff dominates anyway. But it might matter for stuff like the Mill CPU…

> advanced branch prediction is probably not free

I wouldn't be surprised that in this particular case it's even more about the patents and the possibility to have an advantage to the competition than the silicon. Anybody knows if there is a patent? If there is, who holds it? How much would the CPU which would implement that method cost more?

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

#36

Post by PythonicAlpha » Mon, Aug 10, 2015, 1:41 PM UTC

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.

Another reason might be security: There are already attacks known, that are using the CPU cache and/or instruction pipeline to break the boundaries of virtualization. With today's virtualizable processors, it becomes more and more important, that the users can not access to much of the processors implementation details.

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

#37

Post by seanmcdirmid » Mon, Aug 10, 2015, 1:41 PM UTC

acqq wrote: post #33

seanmcdirmid wrote: post #30

Earlier quoted context omitted.

My point was that eventually the technique will fall out if use of newer generations don't benefit from it. So say today X does no good on brand new hardware, then we still do X because not all hardware is new, but the value of doing X will definitely diminish over time. What is really annoying is when X is done to support an out-of-date CPU like a 386, to the detriment of CPUs that are actually currently in use. It…

> say today X does no good on brand new hardware Is for you the "brand new hardware" your desktop which spends hundred of watts per hour or your mobile phone which has to survive the whole day without recharging his 5 Wh battery but still let you surf the web with all the stuff you take as given? Making optimizations that work good with lower wattage CPUs is a good thing, unless you limit yourself only to the non-bat…

Mobile architectures are typically only a tock away from desktop architectures, who aren't really guzzling energy with these optimizations (the deep pentium 4 pipelines are behind us!). So if technology marches forward, there isn't some mobile version that is frozen in time just because of energy efficiency (indeed, good branch prediction saves energy also). There are no 386 or 486 CPUs to care about now, while P5s are limited to that Phi HPC product.

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

#38

Post by seanmcdirmid » Mon, Aug 10, 2015, 1:47 PM UTC

loup-vaillant wrote: post #34

seanmcdirmid wrote: post #30

Earlier quoted context omitted.

My point was that eventually the technique will fall out if use of newer generations don't benefit from it. So say today X does no good on brand new hardware, then we still do X because not all hardware is new, but the value of doing X will definitely diminish over time. What is really annoying is when X is done to support an out-of-date CPU like a 386, to the detriment of CPUs that are actually currently in use. It…

There's one caveat: advanced branch prediction is probably not free. It probably costs a bit of silicon, even some energy. It may or may not actually matter (I'm no hardware designer), but if it does, we may have to make some hard choices, like a few more cores vs badass branch prediction. It may not matter on X86 specifically, where out of order stuff dominates anyway. But it might matter for stuff like the Mill CPU…

If someone identifies an optimum (for performance, efficiency), all competitors are forced to go there to stay competitive. We already have more cores then we know what to do with, and better single core performance is always appreciated, so badass branch prediction probably wins out IF they find that it is useful at all (these days, meaningful gains on single core are difficult to eke out).

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

#39

Post by paulfr » Mon, Aug 10, 2015, 2:24 PM UTC

acqq wrote: post #22

paulfr wrote: post #15

Earlier quoted context omitted.

> the one other researchers (which I respect much more) discovered in 2006 You seem to be blissfully unaware that they're in fact the same researchers: André Seznec is a co-author of the paper. This paper is valuable in pointing out that ITTAGE branch prediction performance is a very good predictor of Haswell performance. Because the Haswell algorithm is secret, that should be very helpful to developers who still hav…

> You seem to be blissfully unaware that they're in fact the same researchers: André Seznec is a co-author of the paper. He's the third signer of the current paper but the first of the 2006 one. It's the case of legitimizing the "research" which only confirms exactly what Intel recently implemented in a given CPU generation, even if the grant is for other goals ("ground-breaking, high-risk projects"). Or, to be clear…

The grant is for the DAL project [1], which presumably fits the "ground-breaking, high-risk" label. In such a project, some tasks will be high-risk, some tasks will be low-risk. Quantifying the branch predictor of current processors may be a comparatively easy task, but that doesn't mean it's trivial, useless or outside the scope of the project, which is to improve sequential performance of microarchitectures. Knowing that real-world processors are performing just as well as previous academic research is helpful, because it suggests that there is no difficulty or unrealistic assumption that prevented manufacturers from doing so. Conveying that knowledge to the compiler and interpreter community is important too.

[1] https://team.inria.fr/alf/members/andre-seznec/defying-amdah...

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

#40

Post by haberman » Mon, Aug 10, 2015, 2:34 PM UTC

School-Cotton wrote: post #6

tl;dr for those who don't want to read the paper in detail: * Interpreters are conceptually a big switch(bytecode) statement in an infinite loop. They use various tricks to make it easier for the processor to predict the target of the next indirect branch * This previously had a dramatic impact on performance, because branch mispredictions are very expensive and it was difficult for the processor to predict them accu…

I'd be interested to see benchmark numbers for LuaJIT, which makes it extremely easy to compile with either replicated dispatch (each bytecode instruction footer has a separate dispatch "jmp" instruction) or common dispatch (each bytecode instruction jumps to a common dispatch "jmp" instruction): http://repo.or.cz/w/luajit-2.0.git/blob/a5b1c4d98eeb97a95077...

    // Instruction footer.
    .if 1
      // Replicated dispatch. Less unpredictable branches, but higher I-Cache use.
      .define ins_next, ins_NEXT
      .define ins_next_, ins_NEXT
    .else
      // Common dispatch. Lower I-Cache use, only one (very) unpredictable branch.
      // Affects only certain kinds of benchmarks (and only with -j off).
      // Around 10%-30% slower on Core2, a lot more slower on P4.
      .macro ins_next
        jmp ->ins_next
      .endmacro
      .macro ins_next_
      ->ins_next:
        ins_NEXT
      .endmacro
    .endif