The NSA Instruction (2019) • Hacker News Board

Re: The NSA Instruction (2019)

#21

Post by st_goliath » Fri, Jun 11, 2021, 1:17 PM UTC

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).

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.

Re: The NSA Instruction (2019)

#22

Post by [deleted] » Fri, Jun 11, 2021, 1:32 PM UTC

bsmith0 wrote: post #8

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

[deleted]

Re: The NSA Instruction (2019)

#23

Post by adrian_b » Fri, Jun 11, 2021, 1:34 PM UTC

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.

Re: The NSA Instruction (2019)

#24

Post by vardump » Fri, Jun 11, 2021, 1:39 PM UTC

nickysielicki wrote: post #13

bsmith0 wrote: post #11

Earlier quoted context omitted.

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-... 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.

Flipping the order works, except if the LSB on x is set. 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).

While it seems to be true gcc and clang don't recognize this pattern even when implemented correctly, your program becomes an infinite loop if the highest bit is set (negative), because 'i' will never become 0.

Example with int8_t:

  int8_t i = -127; // 0b10000001
  i >>= 1; // 0b11000000
  i >>= 1; // 0b11100000
  i >>= 1; // 0b11110000
  i >>= 1; // 0b11111000
  i >>= 1; // 0b11111100
  i >>= 1; // 0b11111110
  i >>= 1; // 0b11111111
  i >>= 1; // 0b11111111 ad infinitum

One needs to be careful when using >> (shift right) with signed integers.

So your program is not equivalent to popcount.

Re: The NSA Instruction (2019)

#25

Post by adrian_b » Fri, Jun 11, 2021, 1:42 PM UTC

adrian_b wrote: post #23

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 Mar…

Moreover, Ferranti Mark I included a hardware random number generator, another feature useful for cryptography, which was reintroduced only recently in modern CPUs.

Re: The NSA Instruction (2019)

#26

Post by st_goliath » Fri, Jun 11, 2021, 1:51 PM UTC

adrian_b wrote: post #23

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 Mar…

I commented on that earlier, including that it probably also has a cryptanalysis background: https://news.ycombinator.com/item?id=27472900

But yes, it definitely pre-dates the 1961 IBM machine in the article.

Re: The NSA Instruction (2019)

#27

Post by Alekhine » Fri, Jun 11, 2021, 1:54 PM UTC

l33t2328 wrote: post #18

mrobot wrote: post #17

Earlier quoted context omitted.

Why did you write this comment?

It’s immediately relevant to the very beginning of the article.

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.

Re: The NSA Instruction (2019)

#28

Post by ludamad » Fri, Jun 11, 2021, 2:07 PM UTC

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`

Re: The NSA Instruction (2019)

#29

Post by pc86 » Fri, Jun 11, 2021, 2:11 PM UTC

Alekhine wrote: post #27

l33t2328 wrote: post #18

Earlier quoted context omitted.

It’s immediately relevant to the very beginning of the article.

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.

How else are we supposed to feel intellectually superior to literally everyone if we're not pedantic assholes to each other?

Re: The NSA Instruction (2019)

#30

Post by dwheeler » Fri, Jun 11, 2021, 2:36 PM UTC

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.