10 ms·

The NSA Instruction (2019)

244 points by cjg 5y ago

deleted 5y ago
[deleted]
oefrha 5y ago
Discussed at the time: https://news.ycombinator.com/item?id=20914479 https://news.ycombinator.com/item?id=20914479
- implements 5y ago
  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.
  - throw5away 5y ago
    If you accidentally write "return x = 1" when x is a variable, you always return true. If you return "1 = x", you cause a syntax error. So some people have gotten into the habit of writing constants on the left, even if the return value of __builtin_popcount is not assignable.
    - implements 5y ago
      Thanks for explaining - that makes sense.
  - IntrepidWorm 5y ago
    > 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. :)
NobodyReport 5y ago
I have always been a lurker and I am trying to add my account to my Keybase but it requires 2 karma. Could a few kind sirs give me the juice?
- NobodyReport 5y ago
  Not gonna spam. Just this one comment to do and hope it works out. Edit- Thank you to the two who did but sadly someone down voted so my total is 1. I respect the community. I don't wish to spam just trying to take control of all online identities.
graderjs 5y ago
This is a great piece of writing. I wish more blogs tied together so many technical perspectives like this. Bravo auteur!
4gotunameagain 5y ago
Another interesting application of popcount is in computer vision, namely in matching keypoints that use binary descriptors for 3D reconstruction in SLAM/TRN etc
- jonatron 5y ago
  Yep, I've used __builtin_popcountll for ORB from OpenCV (256 bit binary descriptors).
  - 4gotunameagain 5y ago
    Looks like we've done similar things :) Horror story: I was once developing a TRN system for a spacecraft instrument which uses an ancient x86 processor that does not have popcnt, ended up using a look-up table instead...
    - solarexplorer 5y ago
      Did you know about HAKMEM 169? I guess it was/is not widely known since many people mention lookup tables as the only fast alternative to the popcnt instruction. http://www.hakmem.org/#item169 http://www.hakmem.org/#item169
      - 4gotunameagain 5y ago
        That's interesting, thanks. It seems that look up tables are still faster when memory allows it though (http://www.dalkescientific.com/writings/diary/archive/2008/07/03/hakmem_and_other_popcounts.html http://www.dalkescientific.com/writings/diary/archive/2008/0...)
bsmith0 5y ago
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
- nickysielicki 5y ago
  Popcount is easily recognized by llvm (and it’s actually mentioned in the article...) In the case of the code you’ve posted, you’re shifting out the LSB before you check the bit, so it’s not quite right, but (in general) popcount is recognized and used when possible.
  - bsmith0 5y ago
    Yep my bad! I think flipping the order should work still though. The two links in the article: https://lemire.me/blog/2016/05/23/the-surprising-cleverness-of-modern-compilers/ https://lemire.me/blog/2016/05/23/the-surprising-cleverness-... And the LLVM source indicate to me it only picks up on x&(x-1) pattern, which would miss the popcount optimization on code like mine.
    - nickysielicki 5y ago
      Flipping the order works, except if the LSB on x is set. https://godbolt.org/z/qdWhxMPsf https://godbolt.org/z/qdWhxMPsf Note the run output under clang. edit: > And the LLVM source indicate to me it only picks up on x&(x-1) pattern, which would miss the popcount optimization on code like mine. Thanks for teaching me something this morning. That's annoying. I think the portable solution is std::popcount in C++ (or equivalent in Rust).
      - tialaramex 5y ago
        > or equivalent in Rust https://doc.rust-lang.org/std/?search=count_ones https://doc.rust-lang.org/std/?search=count_ones Internally Rust actually just staples LLVM's implementation into your code, via an intrinsic - but if that were ever to change the standard library count_ones() methods will do whatever happens instead so you should use that.
torgoguys 5y ago
>You might be wondering, like I was, if there’s more to this instruction, but that’s all it does! This doesn’t seem very useful, right? I have a hard time understanding how anybody who has done most any non-trivial amount of bit maniplation couldn't think of plenty of uses.
- mrobot 5y ago
  Why did you write this comment?
  - l33t2328 5y ago
    It’s immediately relevant to the very beginning of the article.
    - Alekhine 5y ago
      But taken in the context of the whole article, it adds nothing of any value. The author literally spends the rest of the post describing how it is useful. Saying 'doesn't seem useful, does it?' at the beginning is a rhetorical device. The author is assuming that the reader probably doesn't have experience using bit manipulations for complex problems. I am so tired of HN pedantry.
      - pc86 5y ago
        How else are we supposed to feel intellectually superior to literally everyone if we're not pedantic assholes to each other?
        tbrake 5y ago
        Put a little more blunt than I would have but there's nothing wrong there. Rarely a submission goes by where the first comments aren't people racing in to argue with the author. There's an adversarial air that exists around dissecting, criticizing, nit-picking etc ideas presented, both here and in the tech world at large. As if one's most valuable contribution to a conversation is assuming the role of smug contrarian. It's frankly tiring and obnoxious. I used to think non-geeks were just bad at communicating with us; that the fault was on their side somehow. But now I think we're just dicks.
rcgorton 5y ago
It is also incredibly useful for doing string scanning - look at strlen/strchr in various libc imp lementations
- chrchang523 5y ago
  Nitpick: it's the related "count trailing zeros" operation that is useful (in combination with movemask) there, not popcount itself.
dragontamer 5y ago
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 should you use __popc with it. popcount(__activemask()); returns the number of threads executing. lanemask_lt() returns "0b0000000000000001" for the 0th lane. 0b0000000000000011 for the 1st lane. 0b0000000000000111... for the 2nd lane... and 111111111...111 for the last 31st lane. popcount(__activemask() & lanemask_lt()); returns the "active lane count". All together now, we can make a parallel SIMD-stack that can push/pop together in parallel. int head = 0; char buffer[0x1000]; while(fooBar()){ // Dynamic! We don't know who is, or is not active anymore int localPrefix = __popc(__activemask() & __lanemask_lt()); int totalWarpActive = __popc(__activemask()); buffer[head + localPrefix] = generateValueThisThread(); if(localPrefix == 0){ head += totalWarpActive; // Move the head forward, much like a "push" operation in single-thread land // Only one thread should move the head } __syncthreads(); // Thread barrier, make sure everyone is waiting on activeThread#0 before continuing. } ------------ As such, you can dynamically load-balance between GPU threads (!!!) from a shared stack with minimal overheads. If you want to extend this larger than one 32-wide CUDA-warp, you'll need to use __shared __ memory to share the prefix with the rest of the block. It is a bad idea (too much overhead) to extend this much larger than a block, as there's no quick way to communicate outside of your block. Still though, having chunks of up to 1024 threads synchronized through a shared data-structure that only has nanoseconds of overhead is a nifty trick. ----------- EDIT: Oh right, and this concept is now replicated very, very quickly in the dedicated __ballot_sync(...) function (which compiles down to just a few assembly instructions). Playing with the "Exec-mask" is a hugely efficient way to synchronously, and dynamically gather information across your warp. So lots of little tricks have been built around this.
- jiggawatts 5y ago
  Occasionally I am humbled to realise that even in IT there are vast fields of knowledge that are so far removed from my ordinary knowledge as to appear almost like magic. 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...
st_goliath 5y ago
Some years back, I got myself a copy of Andrew Hodges "Alan Turing - The Enigma", a biography and IMO generally a good read, but also with some gems regarding very early computing history in it. Specifically, after WWII, Turing worked on the ACE 1 (later reduced to Pilot ACE) project to build an electronic computer, which didn't really progress due to management and bureaucracy overhead. He eventually went to Manchester, once they got their Manchester Mark 1 off the ground, which they tried to commercialize as "Ferranti Mark 1" (https://en.wikipedia.org/wiki/Ferranti_Mark_1 https://en.wikipedia.org/wiki/Ferranti_Mark_1). While employed for the University, Turing IIRC continued to work as an external consultant for whatever became of G.C. & C.S. on the side. According to the book, he convinced them to buy such a machine (presumably for crypt-analysis?) and, on the Manchester side of things, insisted on some modifications to be made, including a "horizontal adder", so it could count the number of bits set in a word with a single instruction, i.e. a popcount instruction. This would pre-date the IBM Stretch mentioned in the article.
adrian_b 5y ago
It is possible that the "population count" instruction has been included in the instruction sets of most American supercomputers at the request of NSA, which was an important customer for them. Nevertheless, the first computer having this instruction was a British computer, the Ferranti Mark I (February 1951). The name used by Ferranti Mark I for this instruction was "sideways add". Also notable was that Ferranti Mark I had the equivalent of LZCNT (count leading zeroes) too. Both instructions are very useful and they are standard now for modern instruction sets, but they were omitted in most computers after Ferranti Mark I, except in expensive supercomputers.
- adrian_b 5y ago
  Moreover, Ferranti Mark I included a hardware random number generator, another feature useful for cryptography, which was reintroduced only recently in modern CPUs.
  - iib 5y ago
    Hardware random number generators do have some security issues though. Linux devs were opposed to solely relying on them, because they can be compromised by the vendor [1]. So they are at best used in algorithms that they can not compromise (still in [1], but lower, in the comments). [1] https://web.archive.org/web/20180611180213/https://plus.google.com/117091380454742934025/posts/SDcoemc9V3J https://web.archive.org/web/20180611180213/https://plus.goog...
    - adrian_b 5y ago
      The security issues are not with hardware random number generators in general, but with those that are included inside complex devices like monolithic CPUs or TPMs, so that the owners of those devices cannot verify that the RNG's really do what they are claimed to do. Discrete hardware RNG's, like that of the Ferranti Mark I, are perfectly secure. For a modern device, the best way to implement a hardware RNG is to just include an ADC (analog-digital converter) input. Then you may connect externally on the PCB some noisy analog amplifier, e.g. one which has a noisy resistor or diode at its input. Digitizing the noise with the ADC will provide the random numbers and the ADC input can be isolated and tested separately at any time, so the user can verify that there is no hidden functionality. Most microcontrollers have ADC inputs, so it is easy to add a secure hardware RNG for them. The same could be done for a personal computer by making a noisy amplifier that can be plugged in the microphone input, or by making a USB device with a microcontroller.
ludamad 5y ago
My first thought "How else do you quickly count pieces on a bitboard?". Definitely chess programming caused me to never second guess the usefulness of `popcount`
dwheeler 5y ago
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 1-bit fields, then each 4-bit field to the count of 2 2-bit fields, etc., like this: x = (x & 0x55555555) + ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f); x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff); x = (x & 0x0000ffff) + (x >> 16); assuming x is 32 bits. I think this approach is a classic divide-and-conquer solution.
- amalcon 5y ago
  A neat one for large, sparse integers is: for(i=0; !x; ++i) { x = (x-1)&x } return i; Which runs only a number of iterations equal to the number of 1 bits. This works because (x-1) actually just flips the rightmost 1 bit and all zeroes to its right, then the & zeroes all of those. It's not that fast unless your integer is really sparse (since it has a branch), but I've always liked the bit hack.
  - pbsd 5y ago
    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;
    - throw5away 5y ago
      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.
      - jffry 5y ago
        But I can certainly imagine there could be problem domains where most of some collection of integers being manipulated are expected to be sparse or dense.
tptacek 5y ago
The consensus on the 1992 thread (including a really great comment from 'Animats) seems to be that `popcount` was generally not added to architectures at NSA's request --- that people familiar with those archs knew the actual reason `popcount` wound up in the ISA, and it preceded NSA purchases. https://groups.google.com/g/comp.arch/c/UXEi7G6WHuU/m/Z2z7fC7Xhr8J https://groups.google.com/g/comp.arch/c/UXEi7G6WHuU/m/Z2z7fC...
- Animats 5y ago
  The striking thing is that the IBM System/360 didn't have it. Nor does the System/370. Those were the standard mainframes for a generation. IBM Z-series machines do have population count, finally.
notacoward 5y ago
Back in the mid-2000s I worked at a company that made their own (MIPS-based) chips. NSA was one of our customers - supposedly the "defense" who could be considered the good side of NSA compared to the 10x larger "offense" but still. As we were planning for our second generation, they offered quite a bit of money if we'd implement a "sheep and goats" instruction. It would take two operands: an input and a mask. The masked-in bits of the input (the "sheep") would be packed toward the MSB of the output, while the masked-out bits (the "goats") would be packed toward the LSB. We had a lot of people on staff with serious chops in all sorts of math including cryptography, but none of them could identify an algorithm that would benefit from having such an instruction (as distinct from more conventional range-based bitfield instructions). Since the company went under shortly afterward, it remained a mystery. I still wonder about it.
- less_less 5y ago
  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 remember if this is true if they're both packed in forward order. But it would be nice for some hardware crypto designs, like DES or more recently GIFT. PEXT has at least two additional use cases I know of: manipulating bit indices for databases, and binary (GF2) matrix manipulation. I've used it in a (non-crypto) project to select a subset of columns from a binary matrix, to convert it to systematic form. This subroutine also used popcount. What I really wanted in that project was another "NSA instruction": bit matrix multiply. Cray supercomputers can multiply two 64x64 binary matrices in one instruction, though I have no idea how many cycles it takes. With AVX2, the best I could do is 6 instructions plus precomputation for 8x8 x 8x32, which is 1/128'th the work.
  - someguydave 5y ago
    indeed, Cray famously said "If you were plowing a field, which would you rather use: two strong oxen or 1024 chickens?" Unfortunately we only have 1024 chickens in modern computers.
FridayoLeary 5y ago
A bit off- topic but i want to know; is binary code (01etc) still used today in programming/coding? And for what applications?
- fortyrod 5y ago
  Maybe not for general-purpose computing. I've used it for on-the-fly code generation (hacking display rotation into the Windows 3x BitBlt engine) and programming special-purpose media accelerators. In both cases you end up creating a bunch of convenience #defines or macros that generate the bits, which immediately takes you back into tiny language territory rather than pure machine code. The relative ease of creating new programmable hardware in FPGAs is another place this might occur.
- ncmncm 5y ago
  This seems like a strange question. All computing today uses binary code. We often write things in other bases for convenience, but at the hardware level, it is nothing but ones and zeroes. But maybe you are asking about uses of independent bits. A maximally efficient representation for a set with a fixed universe of members uses each bit position in a large-enough integer type to represent presence or absence of a possible member. Then, AND and OR operations correspond to set intersection and union operations. C++ provides std::bitset for this use. Useful such sets include days in the week or month, and letters in the alphabet. The article mentions chess, where you might have a 64-bit word to represent the positions of (say) all the pawns on the board. Fairly simple bitwise operations identify all the positions those pawns threaten. Modern symmetric cryptographic primitives often use principally bitwise operations, including shifts.
drichel 5y ago
Counting bits was the bottleneck in the genomic scan I co-authored (Kanoungi et al. 2020). popcnt resulted in insane perfomance gains comared to all other methods. However, we re-discovered the fact that some Intel CPUs, including the Nehalem mentioned in the article, have a bug that severly affects popcnt's performance, see for example here: https://github.com/komrad36/LATCH/issues/3#issuecomment-267132818 https://github.com/komrad36/LATCH/issues/3#issuecomment-2671...
carapace 5y ago
(I just want to add that this is the best thread on HN i've read in a while. Y'all bringing a little nerdy tear to my eye. <3 )
pklausler 5y ago
Surely the Cray BMM (bit matrix multiplication) instructions have a better claim to that nickname.
ncmncm 5y ago
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 in any chip I know of. Since B is a huge extension, we can expect it will be routinely omitted even after it's ratified, and compilers will need special prodding to produce any such instructions. It should have been in the base instruction set. We probably can blame its lack on the academic origins of the design. CS professors probably think of it as a thing not needed to implement Lisp, therefore not worth class time. (Some people say, "Oh, but you can trap and emulate it", which adds insult to injury. Trapping and emulating eliminates all the value the instruction offers.)
- nullc 5y ago
  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 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.
  - ncmncm 5y ago
    The habit of assessing the importance of operations according only as how frequently they appear in static object files, or even as how frequently they are executed, yields a badly distorted picture. 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.

244 points by cjg 5y ago

deleted 5y ago

[deleted]

oefrha 5y ago

Discussed at the time: https://news.ycombinator.com/item?id=20914479 https://news.ycombinator.com/item?id=20914479

implements 5y ago
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.
- throw5away 5y ago
  If you accidentally write "return x = 1" when x is a variable, you always return true. If you return "1 = x", you cause a syntax error. So some people have gotten into the habit of writing constants on the left, even if the return value of __builtin_popcount is not assignable.
  - implements 5y ago
    Thanks for explaining - that makes sense.
- IntrepidWorm 5y ago
  > 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. :)

NobodyReport 5y ago

I have always been a lurker and I am trying to add my account to my Keybase but it requires 2 karma. Could a few kind sirs give me the juice?

NobodyReport 5y ago
Not gonna spam. Just this one comment to do and hope it works out. Edit- Thank you to the two who did but sadly someone down voted so my total is 1. I respect the community. I don't wish to spam just trying to take control of all online identities.

graderjs 5y ago

This is a great piece of writing. I wish more blogs tied together so many technical perspectives like this. Bravo auteur!

4gotunameagain 5y ago

Another interesting application of popcount is in computer vision, namely in matching keypoints that use binary descriptors for 3D reconstruction in SLAM/TRN etc

jonatron 5y ago
Yep, I've used __builtin_popcountll for ORB from OpenCV (256 bit binary descriptors).
- 4gotunameagain 5y ago
  Looks like we've done similar things :) Horror story: I was once developing a TRN system for a spacecraft instrument which uses an ancient x86 processor that does not have popcnt, ended up using a look-up table instead...
  - solarexplorer 5y ago
    Did you know about HAKMEM 169? I guess it was/is not widely known since many people mention lookup tables as the only fast alternative to the popcnt instruction. http://www.hakmem.org/#item169 http://www.hakmem.org/#item169
    - 4gotunameagain 5y ago
      That's interesting, thanks. It seems that look up tables are still faster when memory allows it though (http://www.dalkescientific.com/writings/diary/archive/2008/07/03/hakmem_and_other_popcounts.html http://www.dalkescientific.com/writings/diary/archive/2008/0...)

bsmith0 5y ago

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

nickysielicki 5y ago
Popcount is easily recognized by llvm (and it’s actually mentioned in the article...) In the case of the code you’ve posted, you’re shifting out the LSB before you check the bit, so it’s not quite right, but (in general) popcount is recognized and used when possible.
- bsmith0 5y ago
  Yep my bad! I think flipping the order should work still though. The two links in the article: https://lemire.me/blog/2016/05/23/the-surprising-cleverness-of-modern-compilers/ https://lemire.me/blog/2016/05/23/the-surprising-cleverness-... And the LLVM source indicate to me it only picks up on x&(x-1) pattern, which would miss the popcount optimization on code like mine.
  - nickysielicki 5y ago
    Flipping the order works, except if the LSB on x is set. https://godbolt.org/z/qdWhxMPsf https://godbolt.org/z/qdWhxMPsf Note the run output under clang. edit: > And the LLVM source indicate to me it only picks up on x&(x-1) pattern, which would miss the popcount optimization on code like mine. Thanks for teaching me something this morning. That's annoying. I think the portable solution is std::popcount in C++ (or equivalent in Rust).
    - tialaramex 5y ago
      > or equivalent in Rust https://doc.rust-lang.org/std/?search=count_ones https://doc.rust-lang.org/std/?search=count_ones Internally Rust actually just staples LLVM's implementation into your code, via an intrinsic - but if that were ever to change the standard library count_ones() methods will do whatever happens instead so you should use that.

torgoguys 5y ago

>You might be wondering, like I was, if there’s more to this instruction, but that’s all it does! This doesn’t seem very useful, right? I have a hard time understanding how anybody who has done most any non-trivial amount of bit maniplation couldn't think of plenty of uses.

mrobot 5y ago
Why did you write this comment?
- l33t2328 5y ago
  It’s immediately relevant to the very beginning of the article.
  - Alekhine 5y ago
    But taken in the context of the whole article, it adds nothing of any value. The author literally spends the rest of the post describing how it is useful. Saying 'doesn't seem useful, does it?' at the beginning is a rhetorical device. The author is assuming that the reader probably doesn't have experience using bit manipulations for complex problems. I am so tired of HN pedantry.
    - pc86 5y ago
      How else are we supposed to feel intellectually superior to literally everyone if we're not pedantic assholes to each other?
      - tbrake 5y ago
        Put a little more blunt than I would have but there's nothing wrong there. Rarely a submission goes by where the first comments aren't people racing in to argue with the author. There's an adversarial air that exists around dissecting, criticizing, nit-picking etc ideas presented, both here and in the tech world at large. As if one's most valuable contribution to a conversation is assuming the role of smug contrarian. It's frankly tiring and obnoxious. I used to think non-geeks were just bad at communicating with us; that the fault was on their side somehow. But now I think we're just dicks.

rcgorton 5y ago

It is also incredibly useful for doing string scanning - look at strlen/strchr in various libc imp lementations

chrchang523 5y ago
Nitpick: it's the related "count trailing zeros" operation that is useful (in combination with movemask) there, not popcount itself.

dragontamer 5y ago

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 should you use __popc with it. popcount(__activemask()); returns the number of threads executing. lanemask_lt() returns "0b0000000000000001" for the 0th lane. 0b0000000000000011 for the 1st lane. 0b0000000000000111... for the 2nd lane... and 111111111...111 for the last 31st lane. popcount(__activemask() & lanemask_lt()); returns the "active lane count". All together now, we can make a parallel SIMD-stack that can push/pop together in parallel. int head = 0; char buffer[0x1000]; while(fooBar()){ // Dynamic! We don't know who is, or is not active anymore int localPrefix = __popc(__activemask() & __lanemask_lt()); int totalWarpActive = __popc(__activemask()); buffer[head + localPrefix] = generateValueThisThread(); if(localPrefix == 0){ head += totalWarpActive; // Move the head forward, much like a "push" operation in single-thread land // Only one thread should move the head } __syncthreads(); // Thread barrier, make sure everyone is waiting on activeThread#0 before continuing. } ------------ As such, you can dynamically load-balance between GPU threads (!!!) from a shared stack with minimal overheads. If you want to extend this larger than one 32-wide CUDA-warp, you'll need to use __shared __ memory to share the prefix with the rest of the block. It is a bad idea (too much overhead) to extend this much larger than a block, as there's no quick way to communicate outside of your block. Still though, having chunks of up to 1024 threads synchronized through a shared data-structure that only has nanoseconds of overhead is a nifty trick. ----------- EDIT: Oh right, and this concept is now replicated very, very quickly in the dedicated __ballot_sync(...) function (which compiles down to just a few assembly instructions). Playing with the "Exec-mask" is a hugely efficient way to synchronously, and dynamically gather information across your warp. So lots of little tricks have been built around this.

jiggawatts 5y ago
Occasionally I am humbled to realise that even in IT there are vast fields of knowledge that are so far removed from my ordinary knowledge as to appear almost like magic. 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...

st_goliath 5y ago

Some years back, I got myself a copy of Andrew Hodges "Alan Turing - The Enigma", a biography and IMO generally a good read, but also with some gems regarding very early computing history in it. Specifically, after WWII, Turing worked on the ACE 1 (later reduced to Pilot ACE) project to build an electronic computer, which didn't really progress due to management and bureaucracy overhead. He eventually went to Manchester, once they got their Manchester Mark 1 off the ground, which they tried to commercialize as "Ferranti Mark 1" (https://en.wikipedia.org/wiki/Ferranti_Mark_1 https://en.wikipedia.org/wiki/Ferranti_Mark_1). While employed for the University, Turing IIRC continued to work as an external consultant for whatever became of G.C. & C.S. on the side. According to the book, he convinced them to buy such a machine (presumably for crypt-analysis?) and, on the Manchester side of things, insisted on some modifications to be made, including a "horizontal adder", so it could count the number of bits set in a word with a single instruction, i.e. a popcount instruction. This would pre-date the IBM Stretch mentioned in the article.

adrian_b 5y ago

It is possible that the "population count" instruction has been included in the instruction sets of most American supercomputers at the request of NSA, which was an important customer for them. Nevertheless, the first computer having this instruction was a British computer, the Ferranti Mark I (February 1951). The name used by Ferranti Mark I for this instruction was "sideways add". Also notable was that Ferranti Mark I had the equivalent of LZCNT (count leading zeroes) too. Both instructions are very useful and they are standard now for modern instruction sets, but they were omitted in most computers after Ferranti Mark I, except in expensive supercomputers.

adrian_b 5y ago
Moreover, Ferranti Mark I included a hardware random number generator, another feature useful for cryptography, which was reintroduced only recently in modern CPUs.
- iib 5y ago
  Hardware random number generators do have some security issues though. Linux devs were opposed to solely relying on them, because they can be compromised by the vendor [1]. So they are at best used in algorithms that they can not compromise (still in [1], but lower, in the comments). [1] https://web.archive.org/web/20180611180213/https://plus.google.com/117091380454742934025/posts/SDcoemc9V3J https://web.archive.org/web/20180611180213/https://plus.goog...
  - adrian_b 5y ago
    The security issues are not with hardware random number generators in general, but with those that are included inside complex devices like monolithic CPUs or TPMs, so that the owners of those devices cannot verify that the RNG's really do what they are claimed to do. Discrete hardware RNG's, like that of the Ferranti Mark I, are perfectly secure. For a modern device, the best way to implement a hardware RNG is to just include an ADC (analog-digital converter) input. Then you may connect externally on the PCB some noisy analog amplifier, e.g. one which has a noisy resistor or diode at its input. Digitizing the noise with the ADC will provide the random numbers and the ADC input can be isolated and tested separately at any time, so the user can verify that there is no hidden functionality. Most microcontrollers have ADC inputs, so it is easy to add a secure hardware RNG for them. The same could be done for a personal computer by making a noisy amplifier that can be plugged in the microphone input, or by making a USB device with a microcontroller.

ludamad 5y ago

My first thought "How else do you quickly count pieces on a bitboard?". Definitely chess programming caused me to never second guess the usefulness of `popcount`

dwheeler 5y ago

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 1-bit fields, then each 4-bit field to the count of 2 2-bit fields, etc., like this: x = (x & 0x55555555) + ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f); x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff); x = (x & 0x0000ffff) + (x >> 16); assuming x is 32 bits. I think this approach is a classic divide-and-conquer solution.

amalcon 5y ago
A neat one for large, sparse integers is: for(i=0; !x; ++i) { x = (x-1)&x } return i; Which runs only a number of iterations equal to the number of 1 bits. This works because (x-1) actually just flips the rightmost 1 bit and all zeroes to its right, then the & zeroes all of those. It's not that fast unless your integer is really sparse (since it has a branch), but I've always liked the bit hack.
- pbsd 5y ago
  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;
  - throw5away 5y ago
    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.
    - jffry 5y ago
      But I can certainly imagine there could be problem domains where most of some collection of integers being manipulated are expected to be sparse or dense.

tptacek 5y ago

The consensus on the 1992 thread (including a really great comment from 'Animats) seems to be that `popcount` was generally not added to architectures at NSA's request --- that people familiar with those archs knew the actual reason `popcount` wound up in the ISA, and it preceded NSA purchases. https://groups.google.com/g/comp.arch/c/UXEi7G6WHuU/m/Z2z7fC7Xhr8J https://groups.google.com/g/comp.arch/c/UXEi7G6WHuU/m/Z2z7fC...

Animats 5y ago
The striking thing is that the IBM System/360 didn't have it. Nor does the System/370. Those were the standard mainframes for a generation. IBM Z-series machines do have population count, finally.

notacoward 5y ago

Back in the mid-2000s I worked at a company that made their own (MIPS-based) chips. NSA was one of our customers - supposedly the "defense" who could be considered the good side of NSA compared to the 10x larger "offense" but still. As we were planning for our second generation, they offered quite a bit of money if we'd implement a "sheep and goats" instruction. It would take two operands: an input and a mask. The masked-in bits of the input (the "sheep") would be packed toward the MSB of the output, while the masked-out bits (the "goats") would be packed toward the LSB. We had a lot of people on staff with serious chops in all sorts of math including cryptography, but none of them could identify an algorithm that would benefit from having such an instruction (as distinct from more conventional range-based bitfield instructions). Since the company went under shortly afterward, it remained a mystery. I still wonder about it.

less_less 5y ago
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 remember if this is true if they're both packed in forward order. But it would be nice for some hardware crypto designs, like DES or more recently GIFT. PEXT has at least two additional use cases I know of: manipulating bit indices for databases, and binary (GF2) matrix manipulation. I've used it in a (non-crypto) project to select a subset of columns from a binary matrix, to convert it to systematic form. This subroutine also used popcount. What I really wanted in that project was another "NSA instruction": bit matrix multiply. Cray supercomputers can multiply two 64x64 binary matrices in one instruction, though I have no idea how many cycles it takes. With AVX2, the best I could do is 6 instructions plus precomputation for 8x8 x 8x32, which is 1/128'th the work.
- someguydave 5y ago
  indeed, Cray famously said "If you were plowing a field, which would you rather use: two strong oxen or 1024 chickens?" Unfortunately we only have 1024 chickens in modern computers.

FridayoLeary 5y ago

A bit off- topic but i want to know; is binary code (01etc) still used today in programming/coding? And for what applications?

fortyrod 5y ago
Maybe not for general-purpose computing. I've used it for on-the-fly code generation (hacking display rotation into the Windows 3x BitBlt engine) and programming special-purpose media accelerators. In both cases you end up creating a bunch of convenience #defines or macros that generate the bits, which immediately takes you back into tiny language territory rather than pure machine code. The relative ease of creating new programmable hardware in FPGAs is another place this might occur.
ncmncm 5y ago
This seems like a strange question. All computing today uses binary code. We often write things in other bases for convenience, but at the hardware level, it is nothing but ones and zeroes. But maybe you are asking about uses of independent bits. A maximally efficient representation for a set with a fixed universe of members uses each bit position in a large-enough integer type to represent presence or absence of a possible member. Then, AND and OR operations correspond to set intersection and union operations. C++ provides std::bitset for this use. Useful such sets include days in the week or month, and letters in the alphabet. The article mentions chess, where you might have a 64-bit word to represent the positions of (say) all the pawns on the board. Fairly simple bitwise operations identify all the positions those pawns threaten. Modern symmetric cryptographic primitives often use principally bitwise operations, including shifts.

drichel 5y ago

Counting bits was the bottleneck in the genomic scan I co-authored (Kanoungi et al. 2020). popcnt resulted in insane perfomance gains comared to all other methods. However, we re-discovered the fact that some Intel CPUs, including the Nehalem mentioned in the article, have a bug that severly affects popcnt's performance, see for example here: https://github.com/komrad36/LATCH/issues/3#issuecomment-267132818 https://github.com/komrad36/LATCH/issues/3#issuecomment-2671...

carapace 5y ago

(I just want to add that this is the best thread on HN i've read in a while. Y'all bringing a little nerdy tear to my eye. <3 )

pklausler 5y ago

Surely the Cray BMM (bit matrix multiplication) instructions have a better claim to that nickname.

ncmncm 5y ago

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 in any chip I know of. Since B is a huge extension, we can expect it will be routinely omitted even after it's ratified, and compilers will need special prodding to produce any such instructions. It should have been in the base instruction set. We probably can blame its lack on the academic origins of the design. CS professors probably think of it as a thing not needed to implement Lisp, therefore not worth class time. (Some people say, "Oh, but you can trap and emulate it", which adds insult to injury. Trapping and emulating eliminates all the value the instruction offers.)

nullc 5y ago
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 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.
- ncmncm 5y ago
  The habit of assessing the importance of operations according only as how frequently they appear in static object files, or even as how frequently they are executed, yields a badly distorted picture. 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.