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

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

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

* Recent Intel architectures have improved branch prediction, so the aforementioned tricks no longer have a very big impact (on Haswell x86 processors specifically)

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.

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.