3 ms·
I'm actually surprised by this. I would think the AVX instructions have complex microcode that would take longer than a simple bit shifter with an AND to check
by colejohnson66 11y ago
I'm actually surprised by this. I would think the AVX instructions have complex microcode that would take longer than a simple bit shifter with an AND to check and add the final bit. I assume `popcnt' isn't used that frequently, so maybe Intel spend a lot of time fine tuning the microcode for AVX but not `popcnt'.
- lqdc13 11y agopopcnt is used very frequently IMO. One example is Bloom filter which is used extensively in many domains. Another example is Tanimoto distance that has to be super fast for computational chemistry http://www.dalkescientific.com/writings/diary/archive/2011/11/02/faster_popcount_update.html http://www.dalkescientific.com/writings/diary/archive/2011/1...
- Coding_Cat 11y agoThere is also the effect of pipelining: AVX might be slower in terms of execution latency/bit. but if this algorithm can fill the entire chain than its speed in terms of throughput can still be greater. For example: say popcnt takes 5 cycles from start to finish per word, and uses 1 execution unit (we will assume there is 1 of each type of EU, which isn't true). Then it can process at most 1/5th a word per cycle. The AVX implementation might take 20 cycles from start to finish per word, but it uses 5 execution units in serial (each taking 4 cycles). Then when the first word passes the first stage (4 cycles later) the second word can be passed to stage 0. Then the throughput for larger strings becomes 1 word/4 cycles = 1/4th word per cycle. So 25% more throughput even though it's 4 times as slow when measured for a single word. In real-life situations this can become quite a nightmare (or a fun little puzzle :]) if you need to intersperse this "popcnt" with multiple other operations.
- stephencanon 11y agoThe vast majority of AVX instructions are single uop. Even the complex instructions that are made up of a couple uops aren't traditional "microcode".
- ajross 11y agoAVX instructions (at least the one's we're talking about here) are fully pipelined and none have microcoded implementations that I'm aware of. And recognize that the news here is "on Haswell". On earlier SSE/AVX implementations POPCNT is indeed faster. Something changed with Haswell that allows this code to run faster than the purpose-designed instruction. Most likely those two adjacent PSHUFB instructions were limited on earlier architectures to running on a single execution port (with a "PSHUFB engine"), and on Haswell it got insantiated on another ALU and they can now be executed in parallel.
- stephencanon 11y agoThere's no need to speculate, this stuff is all in Intel's manuals. All shuffles are port 5 on Haswell, and they're single-cycle latency / single-cycle throughput. Actually, Nehalem - Ivy Bridge could execute two PSHUFBs per cycle; Haswell reduced the throughput while adding a 256b-wide version, so the total work per cycle remains constant if you adopt the new instruction. The SSSE3 popcount implementation was never bottlenecked on PSHUFB[1]. The speedup is because Haswell is a physically wider machine (it has more execution ports) and can execute more uops each cycle. [1] Except on Merom, where PSHUFB was cracked to 4 or 5 uops IIRC, but that's a ten year old part now.
- stephencanon 11y agoToo late to edit, but I mangled the last sentence of this comment; it should instead be something like "The speedup is because Haswell has wider vector instructions and more execution ports (it can execute more uops each cycle)."
- nkurz 11y agoSomething changed with Haswell that allows this code to run faster than the purpose-designed instruction. The change is primarily that AVX2 (which Haswell is the first generation to support) extended binary and integer vector operations to 32B registers, while AVX only supported 32B floating point operations. Instructions that previously operated on 16B doubled their throughput by handling 32B with (usually) the same latency: https://software.intel.com/sites/landingpage/IntrinsicsGuide/#techs=AVX,AVX2 https://software.intel.com/sites/landingpage/IntrinsicsGuide...