Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The NSA Instruction (2019)

vaibhavsagar.com

Post reply on HN
Print view View original

61–70 of 98 posts

Re: The NSA Instruction (2019)

#61

Post by Animats »

tptacek wrote: post #32

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

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.

Re: The NSA Instruction (2019)

#63

Post by implements »

oefrha wrote: post #3

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.

Re: The NSA Instruction (2019)

#64

Post by lowbloodsugar »

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.

If you had to digest a million grains, which would you rather use?

Re: The NSA Instruction (2019)

#65

Post by lowbloodsugar »

flavius29663 wrote: post #51
CalChris wrote: post #48

Earlier quoted context omitted.

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

so, do you want 2 modern oxen or 1024 modern chickens?

These days, all the oxen are made up of chickens. The biggest one is 7,630,848 chickens.

https://www.top500.org/lists/top500/2020/11/

Re: The NSA Instruction (2019)

#66

Post by lurquer »

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?

That’s not the way ‘literally’ should be used.

Re: The NSA Instruction (2019)

#67

Post by devit »

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's equivalent to !0 << popcount(!(x & mask)) (where left shift must saturate and not truncate the shift count, otherwise you need to special case x = 0) and seems much less useful than popcount.

Re: The NSA Instruction (2019)

#68

Post by Bayart »

thomasmg wrote: post #59
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…

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…

The paper, if anyone wants to save some clicks : https://arxiv.org/abs/1706.00990

Re: The NSA Instruction (2019)

#69

Post by mjevans »

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…

The 'and goats' part leads me to conceptualizing the instruction more like:

Bit Scrambler / Chutes - shuffle bits around in a way that divides a stream.

This might also be useful in pre-filters for compression (entropy reduction) if you knew the content of the message. E.G. for ASCII text the upper 2-3 bits of each letter could be ranked to the side for better compression and a reduction of message size.

As others have pointed out, modern CPUs ended up with 'half' that instruction, so I wonder if there were any other reasons for the full instruction.

Re: The NSA Instruction (2019)

#70

Post by throw5away »

pbsd wrote: post #40
amalcon wrote: post #34

Earlier quoted context omitted.

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.

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.
Post reply on HN