5 ms·
One way popcount is useful not mentioned in the OP is in the graph analysis. For example, you can use the following std::bitset<N>* graph = new std::bitset<N>
by monday_ 7y ago
One way popcount is useful not mentioned in the OP is in the graph analysis. For example, you can use the following
std::bitset<N>* graph = new std::bitset<N> [N];
to store the adjacency matrix for a graph with up to N vertices in N^2 bits of memory. The nice thing is that std::bitset::count uses popcount to compute the number of bits set to one.
This makes some graph operations extremely fast even for a pretty large N. For example, graph[i].count() will produce a degree of a vertex and (graph[i] & graph[j]).count() will produce a number of vertices adjacent to both i and j.
- snovv_crash 7y agoCareful, std::bitset.count() doesn't use popcnt on msvc, only gcc and clang.
- monday_ 7y agoThanks for the warning. Fortunately, I'm using it with gcc.
- ncmncm 7y agoPopcount was not supported on the original AMD64 ISA. You have to tell your compiler to generate code for a recent chip before it will generate the instruction.
- snovv_crash 7y agoThat still doesn't work. Here is an example with codegen for AVX2, and an intrinsic call to popcnt, that still doesn't use popcnt for std::bitset.count() with a bitset size of 32 bits. Compare it to the GCC generated code. https://godbolt.org/z/27TmQY https://godbolt.org/z/27TmQY
- ncmncm 7y agoI guess you're talking about MSVC. I find it hard to care much what that does. Code where performance matters much is not built with it. But you're right, their std lib not using their own intrinsic is pathetic.
- snovv_crash 7y agoSometimes we don't have a choice of toolchain used due to distribution targets or other dependencies :-( I'd prefer to be using GCC / Clang for everything too...
- ncmncm 7y agoI wrote to a maintainer of the MSVC lib. He says their lib has to work on all amd64s, but some (specifically, AMD before K10, and Intel before SSSE3) have no popcount. He says their intrinsics are defined to emit exactly the instruction named, unlike Gcc's, so they can't use that in their library. No explanation why they use the loop form, except that the code hasn't been touched in a long, long time.
- snovv_crash 7y agoSurely they can check if AVX is enabled and use the intrinsic if so?
- ncmncm 7y agoThat would involve changing code not touched since before AVX or even SSSE3 existed. Probably not even since before amd64 existed. But it's hard to switch on use of a single instruction. Checking at the use site consumes a branch predictor slot. Switching in a function pointer interferes with inlining. Self-modifying code would have been the old way. The modern way might be rewriting in the linker or loader, or JIT compiling. I have discovered that compilers are extremely bad at recognizing hand-coded byte-order swapping and dropping in movbe or bswap instructions. That Gcc and Clang recognized ham-handed pop counting loops seems miraculous now.
- yvdriess 7y agoSuccinct datastructures (mentioned in the article) are used for storing graphs, using a similar principle. Popcount and its count leading/trailing zeroes siblings are used heavily in those rank/select datastructures. His link to it is worth a read.