4 ms·
As the author states in another comment here (https://news.ycombinator.com/item?id=11278640 https://news.ycombinator.com/item?id=11278640) the charts he has in
by nkurz 11y ago
As the author states in another comment here (https://news.ycombinator.com/item?id=11278640 https://news.ycombinator.com/item?id=11278640) the charts he has in the article understate the potential advantage of the AVX2 approach over POPCNT. On current processors, POPCNT runs on a single execution port and counts the bits in 4B per cycle. A fast unrolled solution thus gets down very close to .125 cycles/byte (1/8).
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.
But if you are already dealing with vector registers, the speedup can be even greater than a microbenchmark would imply. We've been using Wojciech's approach for operations on compressed bitsets, and find it fantastic: https://github.com/RoaringBitmap/CRoaring/blob/master/src/containers/bitset.c https://github.com/RoaringBitmap/CRoaring/blob/master/src/co...
And since wider registers are almost certainly coming, the vectorized approach seems likely to pull even farther ahead in the future. AVX512, the 64B successor to AVX2, is currently scheduled for Skylake Xeon. Unless a second execution port is added for popcnt() (not likely) the vectorized version will probably end up about 3x as fast in a couple years.
- pcwalton 11y ago> And since wider registers are almost certainly coming, the vectorized approach seems likely to pull even farther ahead in the future. AVX512, the 64B successor to AVX2, is currently scheduled for Skylake Xeon. This is fantastic news. I hope this makes it down to consumer CPUs in time as well. The current trend of ridiculously wide SIMD vectors is a pretty exciting development and is (IMO) a reason to be optimistic in spite of the current climate of "Moore's Law is over and the multicore experiment has failed, we're doomed" handwringing. If you can express your problem as a tight parallel numeric loop, things look good for getting better and better performance in the future.
- boulos 11y ago<rant> Intel has decided to make Xeon Laptop parts. Xeon for Skylake means has AVX512. It amazingly doesn't mean what it historically meant ("server part"). I don't like that this means most developer laptops won't have AVX512 (I'm hoping for a new Skylake "Xeon" mbp), but Lenovo and others have already released some. </rant>
- ploxiln 11y agoOn the other hand: this means that it is finally possible to get a laptop with an intel cpu and ECC DRAM! (And I'm guessing, really I hope, that I won't have to look up every xeon laptop part in intel ark to see if it supports vt-x and vt-d - I hope xeon means "no need for further market segmentation, all features that make sense are enabled")
- Nullabillity 11y agoI thought Skylake finally made VT-d a baseline feature (like VT-x has been for a while).
- vardump 11y agoAFAIK, no Skylake (Xeon or other) chips scheduled for 2016 are going to support AVX-512.
- nkurz 11y agoThis matches my belief as well. It's currently scheduled for 2017, but since it's slipped once already and since Intel isn't facing a lot of high end competition, who knows what will actually happen. The naming scheme is terrible, because although "Skylake Xeon" is what many sources are referring to, this turns out not to mean all chips from the Skylake Generation that are marketed as Xeon. Rather, it means something like "Skylake that's actually designed for servers" rather "Current Skylake for which we didn't disable ECC". So despite what others are reporting, I probably should have said that AVX512 is expected to come with "Skylake Purley", which is expected to be marketed as "Skylake Xeon" for the server market: http://wccftech.com/intel-skylake-purley-platform-upto-28-cores-56-threads/ http://wccftech.com/intel-skylake-purley-platform-upto-28-co...