81–90 of 98 posts
Here's a dumb question. If someone asked me to do it I'd probably write code like: while(x != 0) { c += x&1; x >>= 1; } Is this something that should be added to LLVM? Edit: flip the order
Both clang and gcc have __builtin_popcnt variants.
Earlier quoted context omitted.
When the integer is expected to be dense, you have the corresponding trick size_t count = sizeof(x) * 8; while(x != -1) { x |= x+1; --count; } return count;
This is essentially equivalent to feeding the input through bitwise-NOT first. Unfortunately, there are far more integers that are neither sparse nor dense than integers that are sparse or dense.
Obviously using a dedicated instruction is fastest in normal cases. But if you need to implement popcount or many other bit manipulation algorithms in software, a good book to look at is "Hacker's Delight" by Henry S. Warren, Jr, 2003. "Hacker's Delight' page 65+ discuss "Counting 1-bits" (population counts). There are a lot of software algorithms to do this. One approach is to set each 2-bit field to the count of 2…
Discussed at the time: https://news.ycombinator.com/item?id=20914479
In this discussion someone offers: “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.” I’m no longer a programmer, but I wondered why it wasn’t “return (__builtin_popcount(x) == 1)” - just out of interest.
== is a boolian comparison operator. Therefore, we are returning true or false depending on how the expression evaluates. __builtin_popcount(x) will return the number of set '1' bits in the binary int x. Since powers of 2 in binary are always a single 1 followed by 0's, this expression is checking whether the number of 1's in the binary representation of x is equal to 1, and returning true if this is the case. Otherwise, if there are more than 1 '1's, this indicates that x is not a multiple of 2, and should return false.
Example: 15 in binary is 01111. There are 4 '1's, so the 1 == 4 comparison returns false. Increment to 16, or 10000, and there is exactly 1 '1', and so the comparison 1 == 1 returns true.
Hope this helped. :)
It is appalling that, after every other general-computing architecture in common use either started out with a popcount instruction, or had one added later at substantial expense, RISC-V came out without one. It still doesn't have any. The proposed B, "bitmanip" extension has it (along with a raft of trivial variations: count leading zeroes, count trailing ones, yada yada) but that is not ratified and not implemented…
Bitmanip includes other some nice stuff that other CPUs lack-- but I'd give it up happily to be able to count on popcount and clz being there.
I'm doubtful with your academic origins speculation. Even MMIX has SADD. It may be more the case that CLZs and popcounts are relatively rare. But in essentially every case they're used there in some performance critical inner-loop. They're not even necessarily obvious in source code because modern compilers are smart enough to detect obvious constructions and substitute the instruction.
The world of arm is full of important extensions that are optional but the world gets by. Hopefully at some point someone will standardize some RISC-V edition that turns a number of optional things mandatory and after it becomes popular enough that's what people will target.
It is appalling that, after every other general-computing architecture in common use either started out with a popcount instruction, or had one added later at substantial expense, RISC-V came out without one. It still doesn't have any. The proposed B, "bitmanip" extension has it (along with a raft of trivial variations: count leading zeroes, count trailing ones, yada yada) but that is not ratified and not implemented…
Indeed, lack of CLZ is also pretty horrible making a lot of (de)compression and signal processing code needlessly much slower. Bitmanip includes other some nice stuff that other CPUs lack-- but I'd give it up happily to be able to count on popcount and clz being there. I'm doubtful with your academic origins speculation. Even MMIX has SADD. It may be more the case that CLZs and popcounts are relatively rare . But in…
An instruction executed relatively rarely in the course of running a program may achieve critical importance by reducing the latency of the most important result, or by each replacing what would otherwise be dozens of other instructions. Among candidates for such a distinction, popcount takes honors second only to multiplication.
Count-leading-zeroes and other variations rely on the same circuitry and can be emulated by preceding popcount with one or two conventional ALU operations, so are conveniences; popcount is the fully general, indispensible primitive.
Earlier quoted context omitted.
Half of this instruction is present in AMD64's BMI2 extension as PEXT, and the reverse operation as PDEP. Unlike "sheep and goats", PEXT just extracts the sheep into the LSB and ignores the goats. If I recall the Knuth lecture correctly, given a "sheep and goats" instruction where one of the sets is packed in reverse order, you can implement any n-bit permutation in something like log2(n) instructions. I don't rememb…
Succinct (space-saving) data structures often need "rank" and "select" operations. Rank(n) is the number of 1 bits up to position n. Select(n) is the reverse: at which position is the n-th 1 bit. For "rank", the "popcount" instruction can be used. Interestingly, for "select", the "PDEP" instruction can be used: you can put the data array in the PDEP mask, and 1 I wonder if those succinct data structures are in any wa…
GPU-programmers use popcount-based programming all the time these days, but the abstractions are built on top and are hardware accelerated. CUDA's __activemask(); returns the 32-bit value of your current 32-wide EXEC mask. That is to say, if your current warp is: int foo = 0; if(threadIdx.x %= 2){ foo = __activemask(); } foo will be "0b01010101...." or 0x55555555. This __activemask() has a number of useful properties…
This is one of those moments!
PS: I once wrote a 3D engine, but clearly my knowledge is now so out of date as to be practically stone age compared to this kind of thing...
Earlier quoted context omitted.
so, do you want 2 modern oxen or 1024 modern chickens?
Gimme dem modern wide supercalar OOO cached chickens, please. Cray was right back then but he is no longer right now. If he were, the market would say so.
Today we know how to put 16 4 GHz CPUs on a single die. If we want, we can hook chips together to build a computer with 16,384 CPUs.
But we can't build a single chip running usefully at 16x4 GHz. We can't build a single system running at 16384x4 GHz.
If we could build that fast chip or system, all else being equal, the market would choose the single fast CPU over the pile of slow CPUs.
Right now "the market can't say so". It's impossible to provide such a system to the market. We're forced to buy computers with so many CPUs because we've pretty much hit the wall in terms of frequency scaling.
Intel Pentium 4, circa 2001, ran at about 1.4 GHz.
Intel Core i9, circa 2021, runs at about 3.5 GHz, with turbo boost to about 5.2 GHz.
That's about a 3x improvement in clock speed in 20 years. We simply can't make CPUs that run faster than that.
(I had to use x to represent multiplication, HN formatting gets funny with asterisks).
Earlier quoted context omitted.
> But if you need to implement popcount or many other bit manipulation algorithms in software Power9, ARM, x86 BMI, Nvidia PTX, AMD GCN, and AMD RDNA all have a popcount instruction. Yeah, all mainstream CPUs and GPUs made in the past decade... Unfortunately, there's no system I can think of where you'd need the software solution anymore... Maybe if you wanted popcount on an Arduino??
Yet, practically all software running on 64-bit x86 machines is compiled without, because the original amd64 released in 2003 lacked it, and distributions still target that. Likewise, MSVC. There would be good reasons for Apple XCode not to, but that doesn't mean they don't. If you tell MSVC to issue a popcount instruction with "__popcnt64()" (etc.), it will. If you ask Gcc to issue a popcount instruction with "__bui…