Hacker News Reader

Hacker News

Comment by zwerdlds | Hacker News Reader

Parent Full thread

zwerdlds

Article from 2013

View on HN

Also discussed here previously:

https://news.ycombinator.com/item?id=6842338

It seems that the solution is not the top voted comment, but due to mgraczyk.

And oddly no followup article where he talks about how the branch prediction works in Sandy Bridge CPUs.

Although the title is a little confusing, he mentions in the article that he was testing on Sandy Bridge and Haswell: "it manifests on Sandy Bridge and Haswell desktop-class CPUs as well as Sandy Bridge-EP Xeon CPUs".

I just confirmed that the results are the same on Skylake, but I don't have an explanation yet, although I don't think it's branch prediction related.

Excellent, my thinking of why it would be branch prediction is that the call in the loop body would force the pipeline fill (the prediction assumption would be set to 'no' rather than 'yes') whereas in the increment loop the prediction pattern would be set to 'yes' which would give a faster exit and a limited stall penalty if it were wrong.

You can prove/disprove that by taking the branch out of the question and just generating N calls to increment. Or N increments interspersed with a call to NOP.

That said, micro-architecture abuse at this level is rarely applicable to non-synthetic workloads in my experience.

The person who could look at this and just whip out an amazingly brilliant and nuanced explanation of what was going on is Ian Taylor over at Google. I am always in awe of some of the amazing ways that he and the gcc team there could increase performance in something already highly optimized.

See from the old discussion, I understand it's not about the branch prediction:

https://news.ycombinator.com/item?id=6842872

mgraczyk:

"I think It's because the branch target is a memory access, so the dcache causes the execution pipe to stall on the load. In the tight loop with a call, the branch target is a call and there is time enough to pull from dcache before the load data is needed. I suspect that the i7 can't pull data from dcache immediately the jne instruction, so you get a hiccup. Try adding a second noop in to tightloop as the target for jne."

and

https://news.ycombinator.com/item?id=6844264

pbsd:

"The CPU is using store forwarding to cache the 'memory' accesses in the store buffer, which means most accesses are not even accessing L1 cache (if this were the case, we would not have such a low count of cycles per iteration)"

Interesting stuff and I see that Nathan commented there as well [1] where he observed "what matters is that the store-to-load forwarding does not try to execute in the same cycle.". The Agner Fog paper on Intel Micro-architecture [2] is probably the most relevant in terms of puzzling it out.

Again the reason I suspect the branch predictor in this sort of case is that when the loops are essentially 100% inside the cache, practically the only thing that varies the actual execution rate is whether or not a branch is not predicted. That said, the flow through these sorts of pipelined execution units is anything but clear.

[1] https://news.ycombinator.com/item?id=6846257

[2] http://www.agner.org/optimize/microarchitecture.pdf

IMHO branch prediction here is really irrelevant, it is practically trivial for Intel processors and this kind of loops (jumping back conditionally happens many times, there's nothing to confuse the predictor). The only thing that matters is what the CPU does with the "volatile variable" memory accesses in the loop, in which there is the load and the store which could also be conveniently optimized (or not become penalized) in the CPU between one and another event if there is "just enough" separation in some form. I haven't tested these examples myself and I don't have some exact model that would allow me to be sure, but that is my "approximate" conclusion from that former discussion. Interestingly, regarding the experiments with the loops in the previous discussion, I always believed that the NOPSs don't have to be translated to the uops, but if these tests are true, NOPs are somehow relevant even past the decoder, as I'd expect that the whole loop is in the uops cache (and I also admit I don't know the size or behavior of such cache on the recent Intel CPUs).

Thanks! Added.

Reply on news.ycombinator.com