3 ms·
Very interesting result! However, this workload involved a loop summing the popcounts of a series of values, with intermediate results not needed. Beating pop
by JoshTriplett 11y ago
Very interesting result!
However, this workload involved a loop summing the popcounts of a series of values, with intermediate results not needed. Beating popcount on that workload with AVX2 instructions seems plausible; splitting the work across several instructions gives the CPU more to work with simultaneously, and batching the last sum makes it effectively free when amortized across enough iterations.
However, if the popcounts in your workload remain independent, and you immediately need the values from them, I don't think this approach will help.
- nkurz 11y agoHowever, if the popcounts in your workload remain independent, and you immediately need the values from them, I don't think this approach will help. This can be true, but it depends on whether the rest of the workload is vectorized. If you already have the data in vector registers, or can make use of it there afterward, this approach turns out to be even more beneficial than the microbenchmark numbers imply. We've been working with Wojciech's approach for a while now, and thus can even point to real-world code: https://github.com/RoaringBitmap/CRoaring/blob/master/src/containers/bitset.c https://github.com/RoaringBitmap/CRoaring/blob/master/src/co...
- JoshTriplett 11y agoThat looks like another case of a bitset, where you want to accumulate the popcounts over the whole bitset. That seems quite similar to the case in this article. (I still find it surprising that popcount doesn't have enough internal optimization to win, but the numbers certainly prove that.) The case I'm talking about is when you need a single popcount value in isolation as part of some larger computation that doesn't otherwise involve popcounts. For example, I've worked with libraries that manipulate variable-length data structures where each bit in a flags field indicates the presence of a chunk of data. To compute the size of the data, you need the popcount of the flags field. So you get the popcount (using __builtin_popcount when available), and then immediately use that value.