I used to use "implement popcount" as an interview question (for c programmers), I'm not super convinced that it was a good question, although it definitely tells you quite quickly how comfortable a candidate is with bit manipulation.
There are three or four reasonable ways to implement it in c, including one weird trick, but which is most efficient tends to be very CPU dependent (at the time I worked on a project that targeted four or five esoteric CPUs so I had the luxury of being able to verify this)
I remember in one interview I was asked to write a function that returns true iff x is a power of two, so I wrote return 1 == __builtin_popcount(x). They liked that.
But they didn't like it. So I wrote the naivest possible popcount and returned 1 == naive_bitcount(n).
They didn't like that. I explained to them that the compiler will optimize or the loop so this will be fast and that they should check it on godbolt. (did I mention that I was coding on the white board?) There's a loop in the source code, but there isn't a loop in the machine code, and it's like three instructions.
They didn't like that either, so I worked out the n & (n-1) method from first principals. I didn't do it optimally, there was some redundancy in my code, which the interviewer smugly explained to me. I can't remember if I told him "that's nice, but it's still an extra instruction compared to the trivial, obvious, easy to maintain method I showed you ten minutes ago." I'm pretty sure I didn't, too afraid to make a bad impression.
I didn't get the job. In hindsight, I'm glad I didn't. Those guys are dicks.
> I explained to them that the compiler will optimize or the loop so this will be fast and that they should check it on godbolt. (did I mention that I was coding on the white board?) There's a loop in the source code, but there isn't a loop in the machine code, and it's like three instructions.
Did you check this yourself? These sorts of "grand" pattern-matches tend to be low-productivity optimizations for compilers (the speedups you get are not worth the extra compile-time). LLVM tends to have a higher tolerance for this than GCC. But even looking at LLVM's source code, the "naivest possible popcount" [1] is not going to pass the loop idiom recognizer for a popcount.
> I can't remember if I told him "that's nice, but it's still an extra instruction compared to the trivial, obvious, easy to maintain method I showed you ten minutes ago."
n & (n - 1) should come out to 2 cycles of latency. 1 == popcount(n) would come out to 4 cycles of latency (3 latency for the POPCNT, 1 for the comparison at the end).
[1] I'm assuming by this that you mean iterating over all bits and individually checking each one for set/unset. Both gcc (since version 9) and LLVM handle the case where you iterate through set bits in a for (; x; x = x & (x - 1)) loop.
I would not be surprised if the compiler detected the second version as well and replaced it with a popcnt. In any case, it seems like you ended up with the stereotypical “bad interviewer” so I doubt it would have mattered to point this out.
If that was their mission (rather than to hire someone), they succeeded in their personal mission, at the expense of the company's intended mission for them.
popcnt is generally going to take multiple cycles though, I'd expect the n&(n-1) method to be more performant. It's also vectorizeable and more portable.
A popcnt/test/jmp cycle should have roughly 4 cycles of latency: a test+jmp can be fused into one uop, and popcnt would be 3 cycles of latency. n&(n-1) == 0 would compile down into a DEC, TEST, JMP, which is 2 cycles of latency (again, test+jmp are fused into one uop), as dec is just 1 cycle of latency.
So n&(n-1) is faster for checking if it's a power of two.
In the following I confirm that n&(n-1) is faster than popcount (compiled with "cc -march=haswell check_pow2.c -O3"), at 699 vs. 1016 microseconds, respectively:
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
const int N = 2*1000*1000;
int count_popcnt(unsigned int *data) {
int sum = 0;
int i;
for (i=0; i<N; i+=8) {
sum += (
(__builtin_popcount((data+i)[0]) == 1) +
(__builtin_popcount((data+i)[1]) == 1) +
(__builtin_popcount((data+i)[2]) == 1) +
(__builtin_popcount((data+i)[3]) == 1) +
(__builtin_popcount((data+i)[4]) == 1) +
(__builtin_popcount((data+i)[5]) == 1) +
(__builtin_popcount((data+i)[6]) == 1) +
(__builtin_popcount((data+i)[7]) == 1)
);
}
return sum;
}
int count_wegner(unsigned int *data) {
int sum = 0;
int i;
for (i=0; i<N; i+=8) {
sum += (
((((data+i)[0]) & ((data+i)[0]-1)) == 0) +
((((data+i)[1]) & ((data+i)[1]-1)) == 0) +
((((data+i)[2]) & ((data+i)[2]-1)) == 0) +
((((data+i)[3]) & ((data+i)[3]-1)) == 0) +
((((data+i)[4]) & ((data+i)[4]-1)) == 0) +
((((data+i)[5]) & ((data+i)[5]-1)) == 0) +
((((data+i)[6]) & ((data+i)[6]-1)) == 0) +
((((data+i)[7]) & ((data+i)[7]-1)) == 0)
);
}
return sum;
}
int main(void) {
unsigned int data[N];
FILE *f = fopen("/dev/urandom", "rb");
if (!f) {
perror("Cannot open /dev/urandom");
exit(1);
}
if (fread(data, sizeof(unsigned int), N, f) != N) {
perror("Cannot read enough items");
exit(1);
}
/* Use only a few bits */
for (int i=0; i<N; i++) {
data[i] = data[i] & 31;
/* Don't worry about handling 0 */
if (data[i] == 0) {
data[i] = i + 1;
}
}
struct timeval time1, time2;
int n;
gettimeofday(&time1, NULL);
n = count_popcnt(data);
gettimeofday(&time2, NULL);
printf(" popcnt: %d in %8ld us\n",
n,
(time2.tv_sec-time1.tv_sec) * 1000*1000 +
(time2.tv_usec-time1.tv_usec));
gettimeofday(&time1, NULL);
n = count_wegner(data);
gettimeofday(&time2, NULL);
printf("n&(n-1): %d in %8ld us\n",
n,
(time2.tv_sec-time1.tv_sec) * 1000*1000 +
(time2.tv_usec-time1.tv_usec));
return 0;
}
It's faster because both GCC and Clang now optimize loops with n&(n-1) to use AVX2 SIMD! I haven't looked closely to confirm, but I think they may in fact even do Harley-Seal for "naive popcount" loops.
C is no longer portable assembly. If you want to test whether a particular algorithm is faster than another, you probably need to write assembly --- or at least confirm that the compiler did what you thought it did.
Yes, that's exactly what it's for.
The answer I hope for is that they don't care about the case of x==0, so that I can leave out the "x &&" part, leaving the noticeably simpler answer
That code only goes up to the POPCNT instruction. Faster implementations use AVX2 instruction set to implement the Harley-Seal algorithm, and there's VPOPCNTDQ in AVX 512 which does 512 bits at a time.
Table of my preprint at https://chemrxiv.org/articles/The_Chemfp_Project/7877846 shows the comparison of the most reasonable algorithms (for my definition of 'reasonable') on relatively modern hardware. For my case, the AVX2 implementation, fully optimized, is 11x faster than a lookup table and 30% faster than AVX2.
Note that my case handles (typically) multiword popcounts containing 512-2048 bits. Some of the implementations sum the popcount of each word, a few of them use techniques to work on multiple words at a time.
The simplest is a loop that increments a counter if the least significant bit is 1 and right shifts the word by 1 each iteration. Bonus points for early termination
One weird trick is to consider (w & (w - 1)) which unsets the lowest set bit
The other major approach is to use lookup tables for some segment of the word, usually nybble or byte, if this is done on a divide and conquer approach you can short-circuit parts of the word that are zero
[Edit] dalke's answer is much more detailed! I last thought about this stuff in about 2001 or so
Btw, depending on application, sometimes you don't want early termination.
Eg for some cryptographic applications you don't want to leak information about what data you are working on in the runtime of your algorithm.
Another (more far-fetched?) scenario might come up with either branch prediction and CPU pipelining, or your compiler's optimizer recognising the simple loop but not the one that has early abort.
Why?
Its the sort of thing that is used infrequently and you can look it up online. From what I remember the quickest way to do it would be with a lookup hash.
I agree that it's a relatively low signal question, its basically a fizzbuzz for bit twiddling.
That being said "Its the sort of thing that is used infrequently and you can look it up online" pretty much describes interview coding questions in general
I was definitely just using it as a warm-up/screener question. At the time other popular questions were:
• Implement malloc
• Pack this nested data structure into contiguous memory
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.
Popcount 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.
That 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.
Sometimes 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...
I 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.
That 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.
Succinct 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.
The Bitmanip extension definition document for RISC-V explains a wide variety of what were, for me, unfamiliar but terribly useful bitwise operations. Well worth reading even if you have no particular interest in RISC-V. Many of the instructions detailed have analogs in AVX, NEON, and recent POWER instruction sets. Often these instructions are poorly explained in the official manuals.
MMIX has a "SADD" instruction, which does popcount(x&~y). (You could use this to count trailing zeros with two instructions, each taking only one clock cycle.)
I thought JavaScript ought to have a built-in popcount function for the new integer type, but last I checked, it doesn't have. (It would be faster than writing JavaScript code to emulate it.) (I can think of uses for popcount on arbitrary length integers. Of course this won't work with negative numbers (I don't care what it does if the input is negative, although they should define what it does in that case), but for nonnegative numbers would be good to have.)
I have also used the __builtin_popcount function in GNU C. I did not know that it can detect an implementation of popcount and replace it; I have just used the built-in function.
I also did not know of all of the uses mentioned in the linked document (but I did know of some other uses).
JavaScript does have clz32 from back before WASM was the new target for compile-system-language-to-browser but not ctz32 and I doubt it'd be added as that's no longer the focus.
I like popcount for converting a 2^N-bit uniformly-distributed random number into a N-bit binomially-distributed one. Each bit of the input simulates a random coin flip.
Not if you already have 2^n bits at hand. In fact, if you have 2^n bits of entropy, popcount is probably more efficient than generating n more bits randomly.
It's also an instruction in WebAssembly, which has a pretty sparse instruction set. There are only 29 integer operations, and this is one of them. There are also "clz" and "ctz" which count leading and trailing zeroes. Other than that all the instructions are run-of-the-mill arithmetic, comparison, bitmasking and shifting.
The fact that GCC and Clang can identify a manual implementation of count-bits-set and substitute it with an invocation of popcount is fascinating. What other idioms of similar or higher complexity can these compilers recognize and convert to instructions?
It is should be pointed that they can identify some implementations but miss many common idiomatic implementations that may be superior if you do not have a popcount() instruction. I am often surprised by the algorithms they can't see. You will need to check the code generation. This true for many of the bit-twiddling instructions available on modern CPUs.
As for why someone might care, most bit-twiddling intrinsics cannot be used in "constexpr" functions in C++ (though this is starting to change). Finding a C++ code implementation of bit-twiddling that is reliably converted to the underlying instruction allows you to use the same constexpr implementation in both compile-time and run-time contexts with correct code generation.
Does this imply that it might be better to use the "worse" or "naïve" implementation, if you know that the compiler will identify it and do something architecture-appropriate?
Yes. Surprisingly, many naive implementations you might assume would be identified aren't. You are far more likely to write a naive implementation that is not identified than one that is. I've spent a few weekends testing many different implementations to better understand the limitations of the compiler at identifying bit-twiddling instructions and it still doesn't work nearly as well as you might hope.
Also, not every compiler will identify a specific bit-twiddling implementation, Clang seems to identify more of these idiomatic implementations than GCC in my experience, but that is anecdotal. The set of code patterns they can identify is not documented anywhere that I've seen, though it must be in the compiler source code somewhere.
I strongly disagree with the sibling comments. It is better and more clear to call the compiler built-in than do some magic incantation that gets the compiler to optimize it and hope that future compilers don’t regress.
This does not address the real-world case where built-ins will not compile in some valid code contexts. It is not "better" to do something that literally doesn't work. No one is doing this for fun, it is working around a well-known limitation in current compilers.
Because it is an unfortunate limitation on built-ins that reduces their utility, fixing this is on the roadmap for most popular compilers.
On top of that, the popcount built-in will always compile even if there is no instruction for it, as it can generate fallback code. It actually does so for a naive invocation of gcc or clang for x64 as the original x64 IS did not contain popcount. You need to pass some arch that supports the instruction, or -mpopcount to explicitly enable it. Handling all those builtins properly is tedious.
Assuming they are correct that the 'worse on paper' is the only one detected (I don't know if this is true or not) that would be the logical conclusion, yes.
> What other idioms of similar or higher complexity can these compilers recognize and convert to instructions?
Both GCC and clang (really LLVM) will try to autovectorize your loops, replacing operations on individual words with SIMD instructions (provided the compilation target supports them).
Similarly, both should replace `popcnt`-style functions (e.g., count-leading-zeros) with their instruction equivalents, provided the implementation is idiomatic enough. The overarching challenge is that users who don't know about instructions like `popcnt` and `clz` are also less likely to write implementations that are easy to detect and swap.
I don't recall seeing bit counting in the LLVM idiom recognition, but it's been years since I pored over it. Could you maybe Godbolt an example where this substitution happens? I'd be happy to be wrong in this case :)
It could be a bug; I don't see an immediate reason to zero eax in this fragment. Sometimes it's easy to miss the reasons why compilers zero apparently unused things though: it can be about breaking data dependencies or making sure flags are in a known state.
It is a bug, but in the CPU. Until recently, on intel cpu, the popcnt instruction had an implicit dependency on its output register, which can be a performance issue. Explicitly clearing the register (which is very fast and almost free), is an easy way to workaround it.
A lot of things. Even somewhat complicated arithmetic will become a constant if possible. Certain formulas are hardcoded (e.g. the constant-time sum of the first n positive integers). It’ll perform inlining and tail call recursion elimination. Certain loops can be vectorized automatically. And a lot of library functions are “intrinsics” that the compiler knows a lot about: if you implement you own it might replace it with the standard one, or it may specialize your call to the standard library function to suit your specific use (e.g. a 16-byte memcpy for local variables might just be a load into the XMM registers). Godbolt is a really great resource to see what the compiler will and will not do for you.
Even somewhat complicated arithmetic will become a constant if possible.
That's one of the simplest optimisations to implement even in a toy compiler, can be done at the asme time as parsing, and comes practically "for free" --- if all operands of an operator are constant, perform the operation and replace the operator and its operands with the constant result; and repeat this recursively.
Everything else is done based on pattern-matching the AST and performing the appropriate transformations.
Hm, last time I wrote a constant elimination I did so in the optimizer pass over the AST (as part of a lecture, we built a custom C frontend for LLVM and added some optimization passes). What you describe replaces e.g. "x = 3 + 4;", but you get that for free once your optimizer is able to replace more complicated things (e.g. "a = 3; b = 4; x = a + b;").
Also, your parser becomes more complicated; when writing a toy compiler, I think having a clean parser is worth a lot.
The question of whether the CPU can identify an implementation of it and perform it quicker in dedicated hardware is more interesting, and leads to the argument for CISC --- if POPCNT was there since early x86 but microcoded, it would only get faster once the microarchitecture provides dedicated hardware, and there would be no need to recompile or detect CPU features. On older CPUs without the hardware, it wouldn't be any slower, since the CPU would internally execute the equivalent of a manual implementation, only without needing to fetch and decode each individual macro-instruction of it.
The argument for RISC was that the CPU was simpler but could be made much faster. That proved to be overly simplistic. Like the rest of computing it was solved with another layer of abstraction, where CISC processors break instructions into µ-ops.
It also turned out that memory latency would not scale so CISC can be thought of as an instruction stream compression mechanism. Specifically x86 decode is more or less a fixed size block but we have ever more transistors available.
Then RISC ended up adding in a bunch of the complexity it was supposedly going to avoid because in the real world we just need to make the damn thing fast, purity be damned. It didn't help that some architectures made really bad design decisions (hello branch delay slots). Also many RISC cpus have microcode and break down some instructions, though not nearly to the degree a classic CISC cpu does.
It's all very messy and all the armchair theorizing in the world turns out not to matter. What matters is taking the silicon and measuring your workload on it.
It's not that fast; IIRC the microcode implementation is either just a loop over all bits or a nibble/byte-wide lookup table for the result. It's not that fast, from my experience, atleast compared to manually doing it.
Byte (endian) swapping is another one. GCC and Clang can recognize (some) implementations of that and replace with single instruction version (like bswap).
On the other hand until relatively recently they have been bad at recognizing loads/stores of larger integers implemented using byte loads and shifts and then optimizing that into larger loads (for architectures where unaligned loads are allowed). Doing it this way allows you to completely delegate any little/big/weird endian concerns to the compiler.
It's not recognizing a loop, but I've always liked the "turn integer division by a constant into a multiplication by a magic number" optimization: https://godbolt.org/z/Z0FgPW
This and many many other bit-twiddling hacks are described in Hacker's Delight: https://hackersdelight.org/. Compiler developers tend to go through this book and implement all the ones that seem interesting to them.
Yes; in fact memcpy/move are intrinsics in LLVM IR and are one of the more common targets of its idiom recognizer. Fun fact: many loop replacements and vectorizations depend on signed induction variable, so that the compiler doesn't have to prove it doesn't overflow. (Unsigned overflow is defined, signed overflow is UB and thus can be ignored)
That kind of thing is actually fully general, and called the scalar evolution (SCEV) analysis. LLVM for example has a full engine [1] for solving all sort of polynomial recurrences, so you can solve, say, sum i^2 with clang too: https://godbolt.org/z/-nHe78
I assume this is advantageous because then they can unfurl the loops and parallelize instructions across loop 'boundaries'? I wonder if there are other advantages.
For whatever it's worth, this article is a good example of why HN's (only theoretical, by now) policy of keeping the original headline intact makes sense. I wouldn't have clicked on an article with the title "You Won’t Believe This One Weird CPU Instruction!", and I would not feel regret.
> For whatever it's worth, this article is a good example of why HN's (only theoretical, by now) policy of keeping the original headline intact makes sense.
My understanding is that the set-up time is slower than the POPCNT cpu instruction, but throughput is higher. Useful if you need to count bits not on a register, but on a whole array.
It looks the conclusion is that the POPCNT instruction ("cpu") is faster than any of the SSE implementations. Only AVX2 outperforms POPCNT, and only for large enough bitstrings.
Yikes I remember reading that thread on usenet. John Nagle, Rob Warnock and Roger Shepherd. Good times. Roger oddly didn't mention the story about guys in black suits and mirrored sunglasses showing up as the reason the T414 lacked popcount but the T800 added it.
For what it's worth, I've tested my AVX2 copy of their code on a couple of different machines, and found it faster than my POPCNT-based implementation. (See my comments elsewhere here.)
Here's my laptop numbers for my benchmark:
2048 Tanimoto (RDKit Morgan radius=2) 1000 queries
chemfp search using threshold Tanimoto arena, index, single threaded (popcnt_128_128)
threshold T=0.4 popcnt 19.33 ms/query (T2: 19.81 ms check: 189655.09 run-time: 39.2 s) (allow specialized)
chemfp search using threshold Tanimoto arena, index, single threaded (avx2_256)
threshold T=0.4 avx2 12.63 ms/query (T2: 14.04 ms check: 189655.09 run-time: 26.7 s) (allow specialized)
That's 19.33 ms/query on 2048-bit (256 byte) bitstrings using POPCNT unrolled to two loops of 128 bytes each, and 12.63 ms/query using AVX2 specialized for 256 bytes.
My testing showed there was no advantage for a fully unrolled POPCNT implementation. One thing to know is that there is only one execution port for POPCNT on my Intel processor. An AMD processor with 4 execution ports (Ryzen, I think?) may be faster. I don't have that processor, and my limited understanding of the gcc-generated assembly suggests it isn't optimized for that case.
I'm one of the authors on the paper. This is a good point. I think the answer is "it might". In practice (as 'dalke' points out) the AVX2 approach still ends up faster on common Intel hardware with Turbo enabled, but there might be cases where it doesn't, and the measured degree of difference certainly might change with Turbo on or off.
Complicating things, some but not all AVX2 operations benefit from Turbo frequencies as well. It depends on other things on the exact mix of instructions. The technical term is "license", and regardless of the setting of Turbo you processor chooses a frequency depending on the license that the instruction mix allows. Daniel has a blog post (co-written with Travis) on how this affects AVX512, but it also affects AVX2: https://lemire.me/blog/2018/09/07/avx-512-when-and-how-to-us.... The specifics are not well documented, and Travis probably has the best understanding of the exact behavior of anyone I know.
Anyway, we turn Turbo off and try to run the processor at a constant frequency because it makes some of our other measurements more reliable, but yes, when making claims that a SIMD solution is faster than a scalar solution, we should probably be testing whether the conclusion holds even when we turn Turbo back on. I think it's still best practice to do most measurements with it off, but I'll try to remember to do an extra test with it turned of if comes up in future papers.
Thanks for your answer - great blog link - most relevant:
"Intel made more aggressive use of AVX512 instructions in earlier versions of the icc compiler, but has since removed most use unless the user asks for it with a special command line option.".
For other readers, short summary copied from the link with very light editing:
* There are heavy and light AVX instructions. "Heavy" instructions roughly are those involving floating point operations or integer multiplications operating on 512 bits.
* Intel cores can run in one of three modes: license 0 (L0) [normal], license 1 (L1) is slower, and license 2 (L2) is the slowest. To get into license 2, you need sustained use of heavy 512-bit instructions, where sustained means approximately one such instruction every cycle.
* The processor does not immediately move to a higher license when encountering heavy instructions: it will first execute these instructions with reduced performance (say 4x slower) and only when there are many of them will the processor change its frequency. Otherwise, any other 512-bit instructions will move the core to L1.
* Downclocking is per core and for a short time after you have used particular instructions (e.g., ~2ms).
* The downclocking of a core is based on: the current license level of that core, and also the total number of active cores on the same CPU socket (irrespective of the license level of the other cores).
The constraints and suggested workarounds are complex. Also the word choice "license" by Intel is bizarre (since it implies the throttling is to reduce performance for business reasons rather than technical reasons?).
Be aware though that Intel POPCNT instruction throughput is pretty low by today's standards. When you need to popcount a lot of bits, on Intel it might make sense to do it without the use of POPCNT. This oldie but goodie still holds, on Intel: https://danluu.com/assembly-intrinsics/
In contrast, AMD can retire 4 (!) popcounts per cycle per core, if your code is able to feed it.
There's vectorized popcount in some of the optional AVX512 instruction sets, but for those to make it into consumer CPUs AMD would really have to hurt Intel pretty bad, marketshare-wise. :-)
We used a “popcount” style operation + bitwise AND to determine how similar two people were by interest. We had a bitmap where each bit represented an interest and 1 meant they had that interest and 0 meant they did not. Bitwise AND filters out the non overlapping interests and popcount to measure the “intensity” of their similarity (to tease out people who had almost every or almost no interests selected matching others like that — bell curve kind of thing).
If anyone needs that to go fast, for fixed-length (up to ~4k bits) try out my code, chemfp at http://chemfp.com/ . It's designed for cheminformatics, but can work with any data set which can be described by a fixed-length byte string and an identifier.
The same computer architect who first told me about popcount's desirability to the NSA also believed that the massive simultaneous multithreading first introduced to the HPC world commercially by Tera—now owner of the "Cray" name—was also a big win for the spooks.
I highly recommend Matt Godbolt's talk "What has my compiler done for me lately?"[0] and its follow-up[1]. Both are great presentations going into details on some of the crazy optimizations compilers will do. As someone who knows very little about the inner workings of compilers my mind was blown when I saw some them.
If you're building a binary tree incrementally, comparing the length of your stack of partially completed subtrees to the popcnt of the number of leaves so far tells you how many subtrees you need to merge :)
The Popcount instruction seems to be a meme on hacker news. You're cool if know about it and cooler if you've used it. That aside, this article is a good one for applications of it.
Thus can be said about almost all CPU instructions. x64 has tons of SIMD intrinics. You can do absolutely crazy stuff with them if you are willing to invest the time.
True enough, but bitmaps are very easy to use portably, with just &, |, ~, ^, and ++ operations. The only exotic needed very frequently is popcount, but you get that portably from std::bitset (except, evidently, in MSVC).
The compilers are perfectly happy to keep an unsigned and a bitset variable in the same register, so that assigning from one to the other is a no-op.
It's a feature for hardware designers working with 250 nm transistors.
Modern designers working with modern processes have the problem of discovering what they can throw a million transistors at that will actually make real programs faster. Hint: bitmanips!
Popcount comes up in chess engine programming, where boards are regularly represented as a series of bits for each type of piece. The Chess Programming Wiki has a lot of information about both usage and implementation:
I think the most probable reason for this instruction is for calculating parity bits. This would need to be done fast so it makes sense that there would be a CPU instruction to do most of the work.
Parity is much easier than counting. It's so easy that you get it for free in the x86 flags register. (… and because the 8008 was designed to run a terminal.)
Each iteration from the 8080 through x64 have a parity bit in the flags register for backwards compatibility with the previous generation. The 8008 was a microprocessor implementation of the Datapoint 2200 architecture.
Early protocols didn’t have error correction in the lower layers. The parity flag was equivalent to a CRC instruction nowadays. Presumably if parity was incorrect, that would mean the byte was transmitted incorrectly.
I've used _BitScanReverse (popcount-ish MSVC intrinsic) with a custom octree indexing scheme, where higher level voxels have more unset bits from the left. Neat stuff.
It's surprisingly easy to implement a popcount user defined function in C for postgres. It would be a problem for hosted postgres with extension restrictions though.
RISC-V delegates pcnt to the “B” Standard Extension for Bit
Manipulation, and the status of B version 0.90 is Open, meaning it hasn't been finalized. So realistically, RISC-V doesn't have the pcnt instruction. Versions supporting B will have it but that will be at some point in the future.
Worse, it's a fertile ground for "interesting" bugs, because VADDV (which sum-reduces the result) reduces into an 8 bit uint. So if you e.g. accumulate two or more quadword VCNTs into a uint8x16_t and then VADDV it, you could end up with something other than the actual overall bit count (because 2 quadwords can have _256_ bits set). Same with accumulating 8 or more VADDVs, except now individual bytes could wrap around if you don't widen in between.
The original name was "sideways addition". There are many other names, including Hamming weight. The Wikipedia entry for Hamming weight says the HP-16C developers agree with you:
> Some programmable scientific pocket calculators feature special commands to calculate the number of set bits, e.g. #B on the HP-16C[3][17] and WP 43S,[18][19] #BITS[20][21] or BITSUM[22][23] on HP-16C emulators, and nBITS on the WP 34S.[24][25]
There are a lot of potential use cases, but one of the early discussions was around quickly scanning for known HTTP headers. You can see that in use here: https://github.com/aspnet/AspNetCore/blob/caa910ceeba5f2b2c0...
If you really need help falling asleep, here's the discussion going back to 2015: https://github.com/dotnet/corefx/issues/2209
Disclaimers: Microsoft employee, Nazgûl