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

#21

Post by vardump » Mon, Aug 10, 2015, 10:44 AM UTC

astrobe_ wrote: post #17

vardump wrote: post #12

Earlier quoted context omitted.

> you just rewrite the critical parts in native code. Rewrite critical parts of interpreter in native code? My point was there's no optimal native code anymore. Pure interpreters are falling out of fashion anyways. For JITted systems, there's a significant cost for calling native code. At least until JITs actually inline natively called code, possibly even through dynamic library (.so, .dylib, .dll, etc.) call. We ne…

> Rewrite critical parts of interpreter in native code? My point was there's no optimal native code anymore. No, I mean rewrite the critical parts of the "interpreted" program as interpreter primitives/instructions: the best way to eliminate interpreter overhead is to merge N primitives into one. But I realise we have a different perspective. You seem to consider interpreter VMs as off the shelf components, when I co…

Right, I also do work in embedded (without OS), so I'm familiar with the limitations. However, there are situations where it's tempting to write a very primitive JIT or at least glue pieces of code together in a buffer and execute it, to get good inner loop performance by making it as few instructions as possible.

So far C has been enough. Achieving low (=preferably none) defect rate using C is challenging enough.

Usually FPGAs can take care of performance critical part. They do increase total cost, though.

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

#22

Post by acqq » Mon, Aug 10, 2015, 10:52 AM UTC

paulfr wrote: post #15

acqq wrote: post #3

If my coworker would come to me and show me his results where he measured that the "Labels as Values" implementation is not need while "on his Haswell CPU the speedup is only 3%" I'd just ask "can it be guaranteed that the code you propose to revert to the plain switch will run only on that CPU?" If not and the switch is in the performance sensitive place I'd keep the "Labels as Values" implementation. There are many…

> 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 clearer, I respect the deeds not the persons.

I fully understand the need for Seznec to be able to claim that the algorithm is really used by Intel and that therefore he co-authored the last paper. But confirming that Intel used ITTAGE is "ground-breaking, high-risk"? No. And does that mean we should never use goto label in the tight loops? No.

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

#23

Post by Timmons » Mon, Aug 10, 2015, 11:03 AM 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.

There are a number of reasons this is not openly available. Just a few: - It may lock the programmer into a specific CPU - The CPU cache/pipeline is less generic than you might think. Making setting a standard way to change it from within a program problematic. - Multiple programs may be running at the same time. Having the a program dictate cache behaviour would effect all running applications. - Arbitrary changes to behaviour would have performance implications when the change is made. In a multiple application situation that could mean flipflopping behaviour.

Generally though the benefit of the manual control wouldn't be worth the cost/risk/loss of platform support for most applications as CPU behaviour is very good and it would probably be cheaper to just upgrade to a more expensive CPU than to spend the time on developing improvements to the algorithm.

In the rare case where you do need specific behaviour and it is worth while it would be worth speaking to the vendors rather than doing it yourself.

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

#24

Post by acqq » Mon, Aug 10, 2015, 11:12 AM UTC

loup-vaillant wrote: post #14

acqq wrote: post #5

Earlier quoted context omitted.

> the real answer is assume nothing and profile. They did profile, but what? Their "don't trust folklore" ("just 3% speedup") conclusion is valid only for one specific architecture and only for the most recent CPUs. As you say > modern consumer-oriented code should run at least well on Intel Nehalem - Skylake, AMD K10 - K12, ARM Cortex A7/A8/A9/A15/A53/A57/A72, Qualcomm Krait/Kryo. If I understand correctly, they the…

> Their "don't trust folklore" ("just 3% speedup") conclusion is valid only for one specific architecture and only for the most recent CPUs. For now. In 5 years from now, you can be sure most new architectures will have predictors that are as good. So, while it might be good to reach for the low hanging fruit (jump threading), heavier approaches such as super-instruction replication are probably no longer a good idea…

Writing the code in a way not to be dependent on the most advanced hardware solution in existence is better choice unless you target only the specific hardware or the solution is of the "use once then throw away" kind.

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

#25

Post by loup-vaillant » Mon, Aug 10, 2015, 11:20 AM UTC

acqq wrote: post #24

loup-vaillant wrote: post #14

Earlier quoted context omitted.

> Their "don't trust folklore" ("just 3% speedup") conclusion is valid only for one specific architecture and only for the most recent CPUs. For now. In 5 years from now, you can be sure most new architectures will have predictors that are as good. So, while it might be good to reach for the low hanging fruit (jump threading), heavier approaches such as super-instruction replication are probably no longer a good idea…

Writing the code in a way not to be dependent on the most advanced hardware solution in existence is better choice unless you target only the specific hardware or the solution is of the "use once then throw away" kind.

That would be true, if we were speaking of using this optimization instead of that optimisation.

We're not. Here, they're saying that in this particular architecture, a number of optimisations are effectively useless. They're saying that naive code is almost as fast. They're saying that some "optimizations" have even become counter-productive.

The lesson I get from this? Unless I know a fair bit about the target platforms, the naive approach is better, because any performance model I have in mind might be invalidated anyway.

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

#26

Post by seanmcdirmid » Mon, Aug 10, 2015, 11:22 AM UTC

acqq wrote: post #24

loup-vaillant wrote: post #14

Earlier quoted context omitted.

> Their "don't trust folklore" ("just 3% speedup") conclusion is valid only for one specific architecture and only for the most recent CPUs. For now. In 5 years from now, you can be sure most new architectures will have predictors that are as good. So, while it might be good to reach for the low hanging fruit (jump threading), heavier approaches such as super-instruction replication are probably no longer a good idea…

Writing the code in a way not to be dependent on the most advanced hardware solution in existence is better choice unless you target only the specific hardware or the solution is of the "use once then throw away" kind.

So do you still write code for 386 and 486 generations? There is a point where previous CPUs drop off as a concern. All bets are off if you do cutting edge CUDA work, then you only care about the GPU you are running on today because the one you were using yesterday is already outdated, anyways.

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

#27

Post by acqq » Mon, Aug 10, 2015, 11:40 AM UTC

seanmcdirmid wrote: post #26

acqq wrote: post #24

Earlier quoted context omitted.

Writing the code in a way not to be dependent on the most advanced hardware solution in existence is better choice unless you target only the specific hardware or the solution is of the "use once then throw away" kind.

So do you still write code for 386 and 486 generations? There is a point where previous CPUs drop off as a concern. All bets are off if you do cutting edge CUDA work, then you only care about the GPU you are running on today because the one you were using yesterday is already outdated, anyways.

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 CPU generation doesn't get much speedup from that construct doesn't mean that I want to make all other significantly slower. It's not an excuse and I'm not that lazy under these circumstances. If I would not care for performance that much, I would not even use C.

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

#28

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

loup-vaillant wrote: post #25

acqq wrote: post #24

Earlier quoted context omitted.

Writing the code in a way not to be dependent on the most advanced hardware solution in existence is better choice unless you target only the specific hardware or the solution is of the "use once then throw away" kind.

That would be true, if we were speaking of using this optimization instead of that optimisation. We're not. Here, they're saying that in this particular architecture, a number of optimisations are effectively useless. They're saying that naive code is almost as fast. They're saying that some "optimizations" have even become counter-productive. The lesson I get from this? Unless I know a fair bit about the target plat…

They actually benchmark the Python interpreter. They show that only on Haswell the gain from using the goto label is low. For me, that's not an argument to never use goto label, especially not to remove it from the Python implementation which certainly should run on many other CPUs than Haswell.

Edit: therefore I don't agree with your "unless I know a fair bit about the target platforms, the naive approach is better." I'd agree however with "it the speed (or the battery use) actually doesn't matter, the naive approach is better." Sure.

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

#29

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

acqq wrote: post #28

loup-vaillant wrote: post #25

Earlier quoted context omitted.

That would be true, if we were speaking of using this optimization instead of that optimisation. We're not. Here, they're saying that in this particular architecture, a number of optimisations are effectively useless. They're saying that naive code is almost as fast. They're saying that some "optimizations" have even become counter-productive. The lesson I get from this? Unless I know a fair bit about the target plat…

They actually benchmark the Python interpreter. They show that only on Haswell the gain from using the goto label is low. For me, that's not an argument to never use goto label, especially not to remove it from the Python implementation which certainly should run on many other CPUs than Haswell. Edit: therefore I don't agree with your "unless I know a fair bit about the target platforms, the naive approach is better.…

Good thing they don't advocate not using goto label, nor removing it from the Python implementation. Heck, they're not even saying we should stop using goto labels on new projects.

Besides, goto label is a really low hanging fruit that hardly complicates your interpreter, and has no negative impact. They discuss heavier optimisations, some of which are slower on Haswell. Those might not be worth their while any more.

Also, "only on Haswell" won't apply for long. I give AMD 2 years to keep up with Intel's mighty branch prediction, if they haven't done so already. Mobile platform may be different given the energy requirements, though. I don't know.

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

#30

Post by seanmcdirmid » Mon, Aug 10, 2015, 12:42 PM UTC

acqq wrote: post #27

seanmcdirmid wrote: post #26

Earlier quoted context omitted.

So do you still write code for 386 and 486 generations? There is a point where previous CPUs drop off as a concern. All bets are off if you do cutting edge CUDA work, then you only care about the GPU you are running on today because the one you were using yesterday is already outdated, anyways.

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