3 ms·
It’s of course useful, the question is it useful enough to warrant its own instruction
by nwoli 3y ago
It’s of course useful, the question is it useful enough to warrant its own instruction
- inetknght 3y ago> It’s of course useful, the question is it useful enough to warrant its own instruction I argue: yes absolutely.
- chaboud 3y agoWhether it’s shift, mask, multiply, Kernighan’s method, or something else, it’s going to be multiple instructions and tens or hundreds of cycles to do this in software. pop count instructions take a handful of cycles to run (~10 on ARM, ~3 on Intel?). It’s one of those things that silicon can do very well.
- fear91 3y agoNew Intel/AMD CPU's do a register based popcount in a single clock.
- angiosperm 3y agoUsed to be three cycles. Unfortunately, the original AMD64 back in 200x lacked a popcount, so most software built for PCs even today lacks any instances of the instruction. Means to get the instruction generated are finicky, non-portable, and often result unexpectedly in a function call, instead. E.g., without a "-m" option, Gcc and Clang will turn "__builtin_popcount()" into a function call. Likewise, "std::popcount()" and "std::bitset<>::count()". Always use at least "-mavx".
- RetroTechie 3y agoQuestion is whether performance critical code that would benefit from a pop count instruction, is common enough to warrant inclusion. As long as it isn't a bottleneck in common software, a few shifts/masks/add/integer multiply or whatever, are very quick on modern cpus. Often 1-cycle. If not >1 such instructions in parallel per clock.
- dalke 3y agoI work in cheminformatics, and wrote one of the documents cited by Sagar. The answer is "yes and no". My area of focus is a part of molecular similarity. The overall idea is that molecules which are similar tend to have similar functionality. There are many approximate ways to estaimte molecular similarity. The one I focus on maps chemical substructures ("features" or "descriptors") to 1 or several bits on a bitstring of length ~1024 bits, called a fingerprint. We use Jaccard similarity (called Tanimoto similarity in my field) of two fingerprints as a proxy for molecular similarity computed as popcount(A & B) / popcount(A | B). Since popcount(A) and popcount(B) can be pre-computed, this ends up being popcount(A & B) / (popcount(A) + popcount(B) - popcount(A & B). If the fingerprints are grouped by popcount then this boils down to computing popcount(A & B), plus some tiny amount of integer math. This can be used to find the k-nearest matches to a single query, to cluster the fingerprints, to identify diverse fingerprints, and so on. These methods bounded by two things: 1. the time needed to compute popcount of (A & B), and 2. the memory bandwidth. The CPU bottleneck really is the popcount calculation. At https://jcheminf.biomedcentral.com/articles/10.1186/s13321-019-0398-8/tables/1 https://jcheminf.biomedcentral.com/articles/10.1186/s13321-0... I compared different popcount implementations and found POPCNT about 2-3x faster than the fastest pure-C popcount. However, POPCNT on Intel processors isn't all that fast. Rather, when I was really focused on this 5+ years ago, Intel processors only had one execution port than could handle POPCNT, so I could only get one 8 bytes per cycle. (Some AMD processors have several such ports, but I never tried one of those CPUs.) Instead, Wojciech Mula, Nathan Kurz and Daniel Lemire showed that AVX2 instructions were even faster than sequential POPCNT instructions because AVX2 could handle more things in parallel. See my table for numbers. For small bitstrings (I think 512 bits was the boundary) POPCNT is still the fastest. With AVX2 it's fast enough that memory bandwidth becomes the limiting issue, and I need to start worrying about cache locality.
- adrian_b 3y agoSince Intel Ice Lake and AMD Zen 4, the Intel and AMD CPUs with AVX-512 support (or AVX10 in the future) have the VPOPCNT instruction, which works on a short vectors of up to 512-bit length. With VPOPCNT it is easy to accelerate any POPCNT dependent algorithm to speeds far beyond of what is possible with any other instructions.
- deleted 3y ago[deleted]
- Symmetry 3y agoWhy wouldn't it be? The cost is pretty trivial in the context of a modern core, though I can see the argument against in 1961. The biggest cost is in using up an instruction encoding, though when looking at that you have to compare the usefulness of popcount with whatever would replace it.
- jandrewrogers 3y agoIt is broadly useful for bit vectors and integer algorithm performance engineering, showing up all over the place. One advantage the instruction has is fast constant-time performance, whereas algorithms composed from ALU primitives either have performance that is highly sensitive to the bit distribution or have consistent performance but relatively slow. It also uses less space in the instruction cache. The non-classical bit-wise instructions that I find indispensable are popcount and PDEP/PEXT. For some codes, these can turn very messy integer work into a tight, elegant algorithm. Where performance matters, I would not want to live without them.