The way I see it as working, is that the i'th bit in x is initially added to the i'th bit in diff, and subsequently subtracted from the (i-1)th, the (i-2)th, ... the 0th bit of diff.
So this bit of x, if set, contributes (1<<i) - (1<<(i-1) + 1<<(i-2) + ... + 1<<0) = 1 to diff altogether.
int popcnt(unsigned int n) {
int p = 0;
while (n) {
p++;
n &= n-1;
}
return p;
}
But it has a branch in it, so I don't know if it's competitive with the "simple" version of just counting the ones or this version, even though the loop should run fewer iterations. Obviously the real answer is to just use the compiler intrinsics for this, but what fun is that?
The builtin POPCNT that came with Intel's SSE4 (SSE4a for AMD) is much faster. However, at a certain point, using AVX2 (and AVX-512 if present) is actually faster yet [1] - at least for 512 byte inputs or larger.
The version from Hacker's delight is fun and does not branch:
int popcount32(unsigned i) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = ((i + (i >> 4)) & 0x0F0F0F0F);
return (i * 0x01010101) >> 24;
}
If the compiler is allowed to do loop idiom recognition and scalar optimization, writing the dumb thing rather than reaching for an intrinsic can have the same result as the intrinsic.
That's true, but in any scenario where it mattered, I'd hate to rely on it. Compilers have the idiom recognition pass as a sort of hack for speeding up existing codebases but it's ultimately just a heuristic. When I write code, I would much prefer to be explicit about things like that.
Exactly. Write your intention first. Only write something else if you had a measurable performance problem and the change fixed it. If you didn't measure, that wasn't a performance improvement, it just was wanking.
Let the compiler, and library writers take care of most of the work of translating your intention into good runtime performance and only intervene when they don't get the job done.
The point is that writing "__builtin_popcount" makes your intentions clearer than implementing popcount as a loop. The guaranteed performance is downstream of the clarity: since the code is more explicit, the compiler doesn't have to rely on heuristics to guess that you want popcount, so it will always do the right thing.
I'm picturing a naive lookup table solution for a 32-bit popcount, and wondering if there are any text editors that could handle the source gracefully.
You can format the source so any editor can handle it. But a 32-bit table is clearly going to be huge. Better to break it into two 16-bit or four 8-bit pieces and add the counts together.
Of course you can do the not-naive thing to make your editor happy. There's lots of reasons to do the not-naive thing, including but not limited to binary bloat and startup time. Doesn't really answer the question though, does it.
Table lookups aren't fast if the table isn't in cache. A modern processor can do a lot of instructions in the time it takes to do a cold memory access.
"You can use popcount() to implement a sparse array of length N containing M < N members using bitmap of length N and a packed vector of M elements. A member i is present in the array if bit i is set, so M == popcount(bitmap). The index of member i in the packed vector is the popcount of the bits preceding i."
FWIW: These kind of sparse array tricks have been around forever:
For production code as opposed to exams of job interviews, it’s usually better to use hardware implementation. All modern CPUs have instructions for that, popcnt on Intel/AMD, vcnt.8 on ARM Neon.
Many languages have standard library functions, or hardware intrinsics, to emit these instructions: std::popcount in C++/20, _popcnt32 and _popcnt64 intrinsics for Intel/AMD, __builtin_popcount in gcc/clang, BitOperations.PopCount in C#, etc.
Not in the embedded space. Here's the architectures supported by gcc. I suspect most of them do not have popcount equivalent instructions. I've used quite a few of them and the only places I expect hardware support are on Intel and ARM. Rarely does another arch have it.
Compilers can often recognize idiomatic implementations of intrinsics in languages where it is not part of the standard library, doing the appropriate substitution at compile-time. This has the advantage of being highly portable to environments that either lack the intrinsics or don't recognize the idioms without conditional compilation. This typically requires a little experimentation with Godbolt or similar to identify idiomatic C expressions of intrinsics that are consistently recognized across most/all popular compilers.
That said, the reduction in diversity of target platforms, at least on the server side, combined with convergence of language extensions support in compilers has made this less useful than it used to be. I mostly just used builtins and intrinsics these days.
Speaking of the while head, after posting this I realized that there is an optimization you can do by moving the bitshift into the while head, like this:
while (x >>= 1)
This makes gcc compile the code to one instruction less per iteration because it can use the status flags generated by the bitshift to determine whether to jump. Now the loop will only be 3 instructions long and the entire function 8 instructions. https://godbolt.org/z/fna8de367
Which of the 2 versions is more readable is a matter of personal opinion.
Many people consider that the most readable programs are those in which nothing is written in a longer more complex form, if it can be written in a shorter simpler form.
The implicit conversion of a value of any type to a Boolean value is not something invented by C. This was first used in LISP I (1960), then in many other programming languages.
These are not guaranteed to be equivalent expressions even for integer types. It improperly conflates boolean casts (the first case) and boolean comparisons (the second case). In languages like C++ this is an important and commonly used semantic distinction that enables cleaner abstractions because the latter case is making assumptions about the type implementation.
Both styles are used but they have distinct meanings in context.
33 comments
[ 4.6 ms ] story [ 78.3 ms ] threadSo this bit of x, if set, contributes (1<<i) - (1<<(i-1) + 1<<(i-2) + ... + 1<<0) = 1 to diff altogether.
https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_pr...
[1]: https://godbolt.org/z/b9rK3sYah
[1]: https://github.com/WojciechMula/sse-popcount
Let the compiler, and library writers take care of most of the work of translating your intention into good runtime performance and only intervene when they don't get the job done.
My favourite use of popcount is for packing sparse vectors.
"You can use popcount() to implement a sparse array of length N containing M < N members using bitmap of length N and a packed vector of M elements. A member i is present in the array if bit i is set, so M == popcount(bitmap). The index of member i in the packed vector is the popcount of the bits preceding i."
FWIW: These kind of sparse array tricks have been around forever:
https://gcc.gnu.org/ml/gcc-patches/2007-03/msg01308.html
The original idea for that patch didn't come from philip bagwell's paper, but from some code from the late 80's i saw at IBM.
Thus, i suspect this kind of thing has been around forever
Many languages have standard library functions, or hardware intrinsics, to emit these instructions: std::popcount in C++/20, _popcnt32 and _popcnt64 intrinsics for Intel/AMD, __builtin_popcount in gcc/clang, BitOperations.PopCount in C#, etc.
Not in the embedded space. Here's the architectures supported by gcc. I suspect most of them do not have popcount equivalent instructions. I've used quite a few of them and the only places I expect hardware support are on Intel and ARM. Rarely does another arch have it.
https://gcc.gnu.org/backends.html
That said, the reduction in diversity of target platforms, at least on the server side, combined with convergence of language extensions support in compilers has made this less useful than it used to be. I mostly just used builtins and intrinsics these days.
I never realized how much I hate this style of code until I started using Go. Go only allows Boolean conditions, so you have to do this:
> while (x >= 1)
Yeah, it's more code, but it's more readable too.
while (x >>= 1)
This makes gcc compile the code to one instruction less per iteration because it can use the status flags generated by the bitshift to determine whether to jump. Now the loop will only be 3 instructions long and the entire function 8 instructions. https://godbolt.org/z/fna8de367
Many people consider that the most readable programs are those in which nothing is written in a longer more complex form, if it can be written in a shorter simpler form.
The implicit conversion of a value of any type to a Boolean value is not something invented by C. This was first used in LISP I (1960), then in many other programming languages.
Both styles are used but they have distinct meanings in context.