The NSA Instruction (2019) • Hacker News Board

Re: The NSA Instruction (2019)

#41

Post by someguydave » Fri, Jun 11, 2021, 4:01 PM UTC

less_less wrote: post #39

notacoward wrote: post #35

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

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…

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.

Re: The NSA Instruction (2019)

#42

Post by FridayoLeary » Fri, Jun 11, 2021, 4:10 PM UTC

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

Re: The NSA Instruction (2019)

#43

Post by fortyrod » Fri, Jun 11, 2021, 4:20 PM UTC

FridayoLeary wrote: post #42

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

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.

Re: The NSA Instruction (2019)

#44

Post by drichel » Fri, Jun 11, 2021, 4:25 PM UTC

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

Re: The NSA Instruction (2019)

#45

Post by notacoward » Fri, Jun 11, 2021, 4:27 PM UTC

pbsd wrote: post #38

notacoward wrote: post #35

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

That sounds like a decent primitive to accelerate arbitrary bit permutations in software. It's known as GRP in, e.g., [1]. [1] http://palms.ee.princeton.edu/PALMSopen/shi00bit.pdf

Very interesting. This was published in 2000, and the people we worked with were near Princeton, so this result - the specific utility of such an instruction, if not the semantics themselves - might very well be something that was known to some relevant people but not yet widely enough for any of our people to recognize it. Thanks!

Re: The NSA Instruction (2019)

#46

Post by secondcoming » Fri, Jun 11, 2021, 5:15 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

Both clang and gcc have __builtin_popcnt variants.

Re: The NSA Instruction (2019)

#47

Post by dragontamer » Fri, Jun 11, 2021, 5:43 PM UTC

dwheeler wrote: post #30

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…

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

Re: The NSA Instruction (2019)

#48

Post by CalChris » Fri, Jun 11, 2021, 5:49 PM UTC

someguydave wrote: post #41

less_less wrote: post #39

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…

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.

Yes, but those chickens now are as powerful as Cray's oxen were then.

Re: The NSA Instruction (2019)

#49

Post by na85 » Fri, Jun 11, 2021, 5:58 PM UTC

pc86 wrote: post #29

Alekhine wrote: post #27

Earlier quoted context omitted.

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?

Careful, pointing out smug asshole commenters is against the contribution guidelines.

Re: The NSA Instruction (2019)

#50

Post by torgoguys » Fri, Jun 11, 2021, 6:01 PM UTC

mrobot wrote: post #17

torgoguys wrote: post #14

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

Why did you write this comment?

Simply because I found what I quoted from the article to be a weird comment. What I mean is that there probably isn't very much overlap in the two-circle Venn diagram of 1) people who already are low-level enough to care about native CPU instructions and 2) those who can't think of good uses for a population count.

I'm wasn't trying to be a jerk to the author. I just found it strange and would be happy to find out that I'm an idiot and forgot about ____ programmers who fall into that category. My comment was inviting such comments. (After all, if the author meant what they wrote there, apparently they fall into that camp...)