Hacker News Reader

> 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 have to care about branch prediction.

Interpreter developers shouldn't ignore pre-Haswell chips just yet, but if you were to, say, develop a new language your design decisions should be guided by where the puck will be rather than where it used to be.

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

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

While I somewhat agree with you, the real answer is assume nothing and profile. Always. But there's a catch. Things are getting a bit out of hand, there are just too many architectures and configurations.

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

Focus on 64-bit, but some attention should still be paid to 32-bit performance.

Number of actual targets is even worse, because cache and memory architecture vary so much. At least all those have 64-byte cache lines.

In high performance code, there's often the choice between memory and compute load balancing. What memory access patterns and layouts you're going to use - where do you want your bottlenecks? You can often reduce bandwidth requirements by computing more and vice versa.

Take Sandy Bridge for example:

While L1 and L2 cache sizes are fixed on Sandy Bridge, L3 cache varies between 1 - 20 MB.

Clock speeds vary between 1.0 to 3.6 GHz.

There are 1-4 memory channels, I believe they're usually arranged 64 byte granularity round robin. Say your access pattern is access every second 64-byte cache line vs. access every line. On 1 and 3 channel systems, both perform about same. When skipping 64 byte cache line on 2 channel system, effective memory bandwidth is equal to just 1 channel system. 4 channel system will behave like 2 channel one. The code might be bandwidth bottlenecked on 1-2 channel system and compute bound on 3-4 channel system.

Then you're going to hit DRAM page miss every... 1-8 kB? System dependant, of course.

To make the best choice for Sandy Bridge based systems, among other things, you need to know number of memory channels + their arrangement, amount of L3 cache and clock speed. On some Sandy Bridge CPUs you have a lot of time to do complicated data packing and unpacking, trying to just keep memory bandwidth usage down.

That was just one architecture. Now add all the other platforms in the mix. There are pretty many different instruction set extensions. If you don't use them properly, you can lose an order of magnitude of performance.

I think we'll need runtime code generation in the future. On system JIT/AOT also for traditionally compiled languages, such as C and C++.

> 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 themselves measure 30% speedup even only one generation before on Intel and they didn't measure any ARM or AMD.

It looks to me that "don't trust folklore" claim was possible only by ignoring all the processors you name.

And you are right, they also didn't show that they are aware of the differences inside of one generation (does the cheapest processor of the same generation behave the same?)

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

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.

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.

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.

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

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.

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

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

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

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.

The fact that the performance of an implementation varies significantly depending on the actual CPU could already be deduced from some of the Ertl papers.

Moreover, given that one uses specifically a bytecode interpreter and not a JIT is generally the sign that the interpreter is to be used on multiple platforms. "Optimizing" in this context simply means (almost) nothing.

The obvious conclusion is to not care too much about raw performance and focus instead on ease of interfacing with libraries, and to make it easy to add primitives/instructions to your VM. With the idea that if your interpreter is too slow, you just rewrite the critical parts in native code.

> 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 need a lightweight, thin profile guided JIT/AOT engine. No standard library, memory management agnostic. Something that can target different architectures, memory & cache configurations and instruction set extensions that may have been unknown at design phase. A compilation target for some C/C++/Rust/etc. and a runtime that takes care of the architecture details.

> 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 consider VMs as custom components because I'm working mainly with embedded systems. In the embedded world, JIT is often simply not an option either because they are not available for your particular target, or because the resource constrains don't allow it. But still you sometimes want to trade resources for ease of development and/or flexibility.

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.

    given that one uses specifically a bytecode interpreter and not a JIT is generally the sign that the interpreter is to be used on multiple platforms.

Well, you could JIT the bytecode. Or you could use a meta-tracer (see e.g. [1]). Both (kind-of / sort-of) circumvent the platform dependency problem.

[1] http://tratt.net/laurie/research/pubs/html/bolz_tratt__the_i...

> Is ground-breaking, high-risk research discovering that the algorithm in the latest Intel processor matches the one other researchers (which I respect much more) discovered in 2006, and variant of which won more "branch prediction championships"? I'd say no.

That appears to be a pretty reasonable criticism of the process by which the grant was awarded.

My somewhat unfair characterisation of this research from skim reading the abstract and conclusion is: "we point out that the understanding in the academic literature is lagging behind the understanding already built into systems that are sold commercially and are in operational use".

edit:

There's something slightly humorous in considering the grant-allocation process itself as some kind of optimisation problem:

Problem (GA) : How do we best allocate resources to promote high-risk, ground-breaking research?

...and then observing that grant resources have been allocated to perform research on another piece of optimisation that already seems to have happened.

I wonder if one could obtain an ERC Advanced Grant to study the effectiveness of the current process by which ERC Advanced Grants are awarded, and suggest improvements? It is plausible that such a study could be very valuable and yet not have much political support.

> understanding in the academic literature is lagging

Even that were too much to claim as the "branch prediction championships" happened on an "academic" place:

IEEE/ACM International Symposium on Microarchitecture

http://www.jilp.org/cbp/

http://www.microarch.org/micro37/

also note the sponsors.