3 ms·

"Apparently the conditional move is good to avoid branch mispredictions, but cannot hide memory latency as much as the regular implementation." Anybody knows w

by acqq 11y ago

"Apparently the conditional move is good to avoid branch mispredictions, but cannot hide memory latency as much as the regular implementation." Anybody knows what actually happens there? For a real analysis I'd like to see the generated assembly in a classic and conditional move case, and also an example of the indexes accessed in one and another algorithm.

bertr4nd 11y ago
This is just an educated guess, but the cmov is probably going to stall the execution stage of the pipeline, which could end up backing up the front-to-back-end queue, the reorder buffer, and perhaps even fetch itself. You're getting no help from the branch predictor at this point since the dependency runs through an ALU instruction, whereas in the branchy code, you at least have a coinflip chance of predicting the right direction.
- acqq 11y ago
  See my answer to the other post. I still don't see what's going on. I'd expect that the access to the non-cached RAM dominates in big arrays, and we see that for short arrays CMOV is faster. There are tools to actually figure out what's going on, Intel can measure cache misses etc. But I'd like at least ASM codes and the example of indexes in one and another case, if they are very different that's the best explanation.
  - bertr4nd 11y ago
    I think the other poster had it backwards. I'd expect CMOV to perform worse with high memory access latencies (which it does), because it stalls the pipeline. With low access latencies the pipe doesn't stall (for long) anyways, and you avoid the branch miss overhead.
    - acqq 11y ago
      Thanks, you motivated me to find this Linus' take about the CMOV stalls: http://yarchive.net/comp/linux/cmov.html http://yarchive.net/comp/linux/cmov.html Basically, if the direction is predictable, jump can be faster because the mov is then "unconditional." The strange thing is that the binary search on average shouldn't be predictable. So it's still the question what was measured there. Maybe always an element on the position a[0], even when the array was big?
mdergosits 11y ago
With a conditional move the processor executes both sides of the branch, but only "commits" the side that actually should be taken. Mis-predicting a branch on a modern OOO superscalar processor can be much more expensive than executing both sides.
- acqq 11y ago
  But the writer claims that his CMOV version takes more time than the one with the branch for big arrays. I'd expect that the access to the non-cached RAM dominates, and we see that for short arrays CMOV is faster, which is what is to be expected.
nkurz 11y ago
I did some preliminary testing on this a few months ago, which we might pick up again someday and try to publish as a short paper. I haven't looked closely yet at what the author did, and I've forgotten some details of what I did, but I can speak generally to our implementation comparing branching and branchless. For repeated lookups, the first couple levels will all be hit in L1 cache regardless of which way the comparison goes. The branch prediction penalty is about 15 cycles, and the L1 access is about 5. The next level might be in L2 at 12 cycles, then the next few levels are in L3, with a ~40 cycle access time, then RAM with 100+ cycles of access. The last few accesses will be within the same 64B cacheline (128B with buddy prefetch), and thus will be in L1 after the first access. The branchless conditional move approach has a data dependency, while the branching "if" approach is a control dependency. Modern processors "run ahead" with speculative execution past control dependencies (executing the instructions for one branch but not retiring them), while the conditional moves are issued but cannot be executed until the corresponding comparison has been made. Because of speculative execution, the branching approach effectively has a 50% accurate automatic prefetcher that runs several iterations ahead. The math works out so that for some access patterns this can be a significant advantage. The speed gap can be closed (and if I remember correctly, reversed) by adding explicit prefetch instructions to branchless approach. The branching approach can also benefit from judicious use of prefetch, so that each branch fetches acts as a prefetch for the opposite branch, which makes for faster recover after a branch prediction error. As the author concluded, we also found that a batch approach could be beneficial. You can mitigate latency from RAM (and even from L3) if you can arrange to have about 10 outstanding requests at a time. For a single core, batch and prefetch approaches had similar top speeds. For multicore (untested) presumably the excessive memory bandwidth of the "wrong" prefetches would give the advantage to batch. Similar to the author's experience on Broadwell, we found that on Haswell the SIMD gather had minimal advantage over repeated scalar loads. We have a Skylake machine coming soon, and are hoping the hardware gather approach might finally take the lead.
- pcwalton 11y ago
  > Similar to the author's experience on Broadwell, we found that on Haswell the SIMD gather had minimal advantage over repeated scalar loads. I've read that VPGATHERDD is microcoded to N separate loads on Haswell, unfortunately.
gfody 11y ago
I experimented with cmov for a lot of cpu-bound graphics routines years ago and found that it was rarely faster than branching and never faster than a branchless version w/o cmov. The folks on c.l.a.x said this was due to cmov being microcoded on modern CPUs and so under the hood your still just branching and the only benefit really was instruction cache.
- nkurz 11y ago
  I don't know when the change was made, but conditional moves are fast and efficient on the last several generations of AMD and Intel processors. Usually, you are trading 1 or 2 extra cycles of latency against the chance of a ~15 cycle mispredicted branch penalty. If your branch cannot be predicted correctly ~85% of the time, this can be a significant win.
susi22 11y ago
It's because the computation complexity increased: http://cs.stackexchange.com/questions/29755/why-is-binary-search-faster-than-ternary-search http://cs.stackexchange.com/questions/29755/why-is-binary-se...

by acqq 11y ago

bertr4nd 11y ago

This is just an educated guess, but the cmov is probably going to stall the execution stage of the pipeline, which could end up backing up the front-to-back-end queue, the reorder buffer, and perhaps even fetch itself. You're getting no help from the branch predictor at this point since the dependency runs through an ALU instruction, whereas in the branchy code, you at least have a coinflip chance of predicting the right direction.

acqq 11y ago
See my answer to the other post. I still don't see what's going on. I'd expect that the access to the non-cached RAM dominates in big arrays, and we see that for short arrays CMOV is faster. There are tools to actually figure out what's going on, Intel can measure cache misses etc. But I'd like at least ASM codes and the example of indexes in one and another case, if they are very different that's the best explanation.
- bertr4nd 11y ago
  I think the other poster had it backwards. I'd expect CMOV to perform worse with high memory access latencies (which it does), because it stalls the pipeline. With low access latencies the pipe doesn't stall (for long) anyways, and you avoid the branch miss overhead.
  - acqq 11y ago
    Thanks, you motivated me to find this Linus' take about the CMOV stalls: http://yarchive.net/comp/linux/cmov.html http://yarchive.net/comp/linux/cmov.html Basically, if the direction is predictable, jump can be faster because the mov is then "unconditional." The strange thing is that the binary search on average shouldn't be predictable. So it's still the question what was measured there. Maybe always an element on the position a[0], even when the array was big?

mdergosits 11y ago

With a conditional move the processor executes both sides of the branch, but only "commits" the side that actually should be taken. Mis-predicting a branch on a modern OOO superscalar processor can be much more expensive than executing both sides.

acqq 11y ago
But the writer claims that his CMOV version takes more time than the one with the branch for big arrays. I'd expect that the access to the non-cached RAM dominates, and we see that for short arrays CMOV is faster, which is what is to be expected.

nkurz 11y ago

I did some preliminary testing on this a few months ago, which we might pick up again someday and try to publish as a short paper. I haven't looked closely yet at what the author did, and I've forgotten some details of what I did, but I can speak generally to our implementation comparing branching and branchless. For repeated lookups, the first couple levels will all be hit in L1 cache regardless of which way the comparison goes. The branch prediction penalty is about 15 cycles, and the L1 access is about 5. The next level might be in L2 at 12 cycles, then the next few levels are in L3, with a ~40 cycle access time, then RAM with 100+ cycles of access. The last few accesses will be within the same 64B cacheline (128B with buddy prefetch), and thus will be in L1 after the first access. The branchless conditional move approach has a data dependency, while the branching "if" approach is a control dependency. Modern processors "run ahead" with speculative execution past control dependencies (executing the instructions for one branch but not retiring them), while the conditional moves are issued but cannot be executed until the corresponding comparison has been made. Because of speculative execution, the branching approach effectively has a 50% accurate automatic prefetcher that runs several iterations ahead. The math works out so that for some access patterns this can be a significant advantage. The speed gap can be closed (and if I remember correctly, reversed) by adding explicit prefetch instructions to branchless approach. The branching approach can also benefit from judicious use of prefetch, so that each branch fetches acts as a prefetch for the opposite branch, which makes for faster recover after a branch prediction error. As the author concluded, we also found that a batch approach could be beneficial. You can mitigate latency from RAM (and even from L3) if you can arrange to have about 10 outstanding requests at a time. For a single core, batch and prefetch approaches had similar top speeds. For multicore (untested) presumably the excessive memory bandwidth of the "wrong" prefetches would give the advantage to batch. Similar to the author's experience on Broadwell, we found that on Haswell the SIMD gather had minimal advantage over repeated scalar loads. We have a Skylake machine coming soon, and are hoping the hardware gather approach might finally take the lead.

pcwalton 11y ago
> Similar to the author's experience on Broadwell, we found that on Haswell the SIMD gather had minimal advantage over repeated scalar loads. I've read that VPGATHERDD is microcoded to N separate loads on Haswell, unfortunately.

gfody 11y ago

I experimented with cmov for a lot of cpu-bound graphics routines years ago and found that it was rarely faster than branching and never faster than a branchless version w/o cmov. The folks on c.l.a.x said this was due to cmov being microcoded on modern CPUs and so under the hood your still just branching and the only benefit really was instruction cache.

nkurz 11y ago
I don't know when the change was made, but conditional moves are fast and efficient on the last several generations of AMD and Intel processors. Usually, you are trading 1 or 2 extra cycles of latency against the chance of a ~15 cycle mispredicted branch penalty. If your branch cannot be predicted correctly ~85% of the time, this can be a significant win.

susi22 11y ago

It's because the computation complexity increased: http://cs.stackexchange.com/questions/29755/why-is-binary-search-faster-than-ternary-search http://cs.stackexchange.com/questions/29755/why-is-binary-se...