alt.hn

12/11/2025 at 2:30:28 PM

Pop Goes the Population Count?

 https://xania.org/202512/11-pop-goes-the-weasel-er-count

by hasheddan

12/11/2025 at 8:08:10 PM

I still find it wild that Godbolt is his actual name and not some cool term used for the tool to see what compiler output looks like.

by dhosek

12/11/2025 at 9:02:34 PM

Same! I always assumed it was the name of the tool until I found out it was a person not long ago.

Maybe a bit of a stretch, but I could see it fitting - https://en.wikipedia.org/wiki/Aptronym

by silisili

12/11/2025 at 5:36:45 PM

Isn't this the instruction that apparently the NSA asked for?

by bombcar

12/11/2025 at 6:12:29 PM

It goes back to the CDC 6600 at least, and is most often seen as part of Hamming distance computation (pop(xor(x,y))). But it turns out to be really useful for other things (trailing zero count), and worth having in hardware since the software sequence is a ~dozen instructions for 64 bits.

by pklausler

12/11/2025 at 6:03:03 PM

yeah. They understood how useful computing on bits can be before anyone else.

by adgjlsfhk1

12/11/2025 at 11:06:40 PM

As impressive as this analysis is by the compiler, I shudder to think how much time the compiler spends doing these kinds of optimizations. In my opinion, a better architecture would be for the compiler to provide a separate analysis tool that suggests source level changes for these kinds of optimizations. It could alert you that the loop could be replaced with a popcount (and optionally make the textual replacement in the source code for you). Then you pay the cost of the optimization once and have the benefit of clarity about what your code _actually_ runs at runtime instead of the compiler transparently pulling the rug out from underneath you when run with optimizations.

Side note: many years ago I wrote the backend for a private global surveillance system that has almost surely tracked the physical location of anyone reading this. We could efficiently track how often a device had been seen at a location in the prior 64 (days|weeks|months) in just 192 bytes and use popcount to compute the value. I am not proud that I built this.

by thefaux

12/12/2025 at 9:02:19 AM

The issue is that many optimization opportunities only appear after monomorphization, inlining, de-virtualization, etc. etc.

Not that you couldn't do source level analysis as you suggest... it just wouldn't be effective in many cases.

It would also be 'unstable' in the sense that it might depend on architecture, etc.

by Quekid5

12/12/2025 at 2:03:02 AM

Especially in languages that allow generic programming, the right thing to do will be context dependent.

by adgjlsfhk1

12/11/2025 at 5:56:45 PM

Hey! Popcount used to be my favorite instruction. Now I think I prefer LOP3 though :)

by majke

12/12/2025 at 6:00:17 PM

Could you explain more please?

by azinman2

12/11/2025 at 6:55:50 PM

There's a fun approach where do the computation as a tree in parallel. You do a little masking and shifting to add all the even-numbered bits to all the odd-numbered bits, and come up with a set of (assuming we're working on a 64-bit value) 32 partial sums of 2 bits each. Then you add pairs of those to get 16 partial sums of 4 bits each, and so forth until you get to the top. This requires six sums, plus shifts and masks for each one.

I don't know if compilers are able to detect this and compile it down to a single instruction, though.

by wat10000

12/11/2025 at 8:35:01 PM

I <3 [AT]BM and BMI[12], and functional-equivalency matching with cost minimization optimization compiler passes.

I wish GCC and LLVM had compiler passes to semi/automagically "vectorize" hot sections using SIMD, i.e., magic transformation of UTF-8 conversion, regex matching, and string functions.

by burnt-resistor

12/11/2025 at 7:25:07 PM

Somewhat related, "Gosper's hack" is a fun way to loop through all of the values that have the same number of 1s.

by taeric