4 ms·

It is _very_ useful when hand optimizing loops in assembly. But for the compiler, the newer processors have such incredible branch predictors it is usually a ba

by wscott 10y ago

It is _very_ useful when hand optimizing loops in assembly. But for the compiler, the newer processors have such incredible branch predictors it is usually a bad idea for the compiler assume a branch is poorly predicted. Now if you are using profile guided optimizations (--prof-gen/prof-use) AND you use the processor's performance counters as part of the feedback to the compiler _then_ I could see the compiler correctly using this instruction.

snaky 10y ago
I have a mixed feeling about that incredible progress in modern CPUs branch prediction. Don't they just use idle execution units and run both branches in parallel behind the scenes? It looks great on microbenchmarks when there's a bunch of idle execution units to use, a memory bus and caches are underused. It may not perform so well on real load when there's no idle execution units available to use for free, and memory bus and cache lines are choking on load. Is it somewhat similar to these two examples? > If it owns that line then CAS is extremely fast - core doesn't need to notify other cores to do that operation. If core doesn't own it, the situation is very different - core has to send request to fetch cache line in exclusive mode and such request requires communication with all other cores. Such negotiation is not fast, but on Ivy Bridge it is much faster than on Nehalem. And because it is faster on Ivy Bride, core has less time to perform a set of fast local CAS operations while it owns cacheline, therefore total throughput is less. I suppose, a very good lesson learned here - microbenchmarking can be very tricky and not easy to do properly. Also results can be easily interpreted in a wrong way http://stas-blogspot.blogspot.com/2013/02/evil-of-microbenchmarking-cas.html http://stas-blogspot.blogspot.com/2013/02/evil-of-microbench... > On current processors, POPCNT runs on a single execution port and counts the bits in 4B per cycle. The AVX2 implementation requires more instructions, but spreads the work out across more ports. My fastest unrolled version takes 2.5 cycles per 32B vector, or .078 cycles/byte (2.5/32). This is 1.6x faster (4 cycles per 32B /2.5 cycles per 32B) than scalar popcnt(). Whether this is worth doing depends on the rest of the workload. If the rest of the work is being done on scalar 64-bit registers, those other scalar operations can often fit between the popcnts() "for free", and the cost of moving data back and forth between vector and scalar registers usually overwhelms the advantage. https://news.ycombinator.com/item?id=11279047 https://news.ycombinator.com/item?id=11279047
- gpderetta 10y ago
  > I have a mixed feeling about that incredible progress in modern CPUs branch prediction. Don't they just use idle execution units and run both branches in parallel behind the scenes? No, I do not know of any production CPU that does it; Branch predictor accuracy today is ~98-99% so it would be a waste of power and execution capability to speculate both paths of a branch. Also, I think code in average executes 1 jump every 5 instructions and an OoO core can speculate hundreds of instructions in advance, so the number of possible code paths would explode very quickly.

by wscott 10y ago

snaky 10y ago

I have a mixed feeling about that incredible progress in modern CPUs branch prediction. Don't they just use idle execution units and run both branches in parallel behind the scenes? It looks great on microbenchmarks when there's a bunch of idle execution units to use, a memory bus and caches are underused. It may not perform so well on real load when there's no idle execution units available to use for free, and memory bus and cache lines are choking on load. Is it somewhat similar to these two examples? > If it owns that line then CAS is extremely fast - core doesn't need to notify other cores to do that operation. If core doesn't own it, the situation is very different - core has to send request to fetch cache line in exclusive mode and such request requires communication with all other cores. Such negotiation is not fast, but on Ivy Bridge it is much faster than on Nehalem. And because it is faster on Ivy Bride, core has less time to perform a set of fast local CAS operations while it owns cacheline, therefore total throughput is less. I suppose, a very good lesson learned here - microbenchmarking can be very tricky and not easy to do properly. Also results can be easily interpreted in a wrong way http://stas-blogspot.blogspot.com/2013/02/evil-of-microbenchmarking-cas.html http://stas-blogspot.blogspot.com/2013/02/evil-of-microbench... > On current processors, POPCNT runs on a single execution port and counts the bits in 4B per cycle. The AVX2 implementation requires more instructions, but spreads the work out across more ports. My fastest unrolled version takes 2.5 cycles per 32B vector, or .078 cycles/byte (2.5/32). This is 1.6x faster (4 cycles per 32B /2.5 cycles per 32B) than scalar popcnt(). Whether this is worth doing depends on the rest of the workload. If the rest of the work is being done on scalar 64-bit registers, those other scalar operations can often fit between the popcnts() "for free", and the cost of moving data back and forth between vector and scalar registers usually overwhelms the advantage. https://news.ycombinator.com/item?id=11279047 https://news.ycombinator.com/item?id=11279047

gpderetta 10y ago
> I have a mixed feeling about that incredible progress in modern CPUs branch prediction. Don't they just use idle execution units and run both branches in parallel behind the scenes? No, I do not know of any production CPU that does it; Branch predictor accuracy today is ~98-99% so it would be a waste of power and execution capability to speculate both paths of a branch. Also, I think code in average executes 1 jump every 5 instructions and an OoO core can speculate hundreds of instructions in advance, so the number of possible code paths would explode very quickly.