6 ms·

Article from 2013

by zwerdlds 9y ago

Article from 2013

ChuckMcM 9y ago
And oddly no followup article where he talks about how the branch prediction works in Sandy Bridge CPUs.
- nkurz 9y ago
  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.
  - ChuckMcM 9y ago
    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.
    - acqq 9y ago
      See from the old discussion, I understand it's not about the branch prediction: https://news.ycombinator.com/item?id=6842872 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 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)"
      - ChuckMcM 9y ago
        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 https://news.ycombinator.com/item?id=6846257 [2] http://www.agner.org/optimize/microarchitecture.pdf http://www.agner.org/optimize/microarchitecture.pdf
        acqq 9y ago
        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).
dang 9y ago
Thanks! Added.
acqq 9y ago
Also discussed here previously: https://news.ycombinator.com/item?id=6842338 https://news.ycombinator.com/item?id=6842338 It seems that the solution is not the top voted comment, but due to mgraczyk.

Article from 2013

ChuckMcM 9y ago

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

nkurz 9y ago
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.
- ChuckMcM 9y ago
  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.
  - acqq 9y ago
    See from the old discussion, I understand it's not about the branch prediction: https://news.ycombinator.com/item?id=6842872 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 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)"
    - ChuckMcM 9y ago
      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 https://news.ycombinator.com/item?id=6846257 [2] http://www.agner.org/optimize/microarchitecture.pdf http://www.agner.org/optimize/microarchitecture.pdf
      - acqq 9y ago
        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).

dang 9y ago

Thanks! Added.

acqq 9y ago

Also discussed here previously: https://news.ycombinator.com/item?id=6842338 https://news.ycombinator.com/item?id=6842338 It seems that the solution is not the top voted comment, but due to mgraczyk.