7 ms·
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 shee
by 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 agoindeed, 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.
- CalChris 5y agoYes, but those chickens now are as powerful as Cray's oxen were then.
- flavius29663 5y agoso, do you want 2 modern oxen or 1024 modern chickens?
- CalChris 5y agoGimme dem modern wide supercalar OOO cached chickens, please. Cray was right back then but he is no longer right now. If he were, the market would say so.
- PhantomGremlin 5y agoCray is still right. Today we know how to put 16 4 GHz CPUs on a single die. If we want, we can hook chips together to build a computer with 16,384 CPUs. But we can't build a single chip running usefully at 16x4 GHz. We can't build a single system running at 16384x4 GHz. If we could build that fast chip or system, all else being equal, the market would choose the single fast CPU over the pile of slow CPUs. Right now "the market can't say so". It's impossible to provide such a system to the market. We're forced to buy computers with so many CPUs because we've pretty much hit the wall in terms of frequency scaling. Intel Pentium 4, circa 2001, ran at about 1.4 GHz. Intel Core i9, circa 2021, runs at about 3.5 GHz, with turbo boost to about 5.2 GHz. That's about a 3x improvement in clock speed in 20 years. We simply can't make CPUs that run faster than that. (I had to use x to represent multiplication, HN formatting gets funny with asterisks).
- djmips 5y agoThanks for the post but you can't in all fairness keep your "Cray is still right" opening statement when you go on to agree that in reality, which is what is important, we have to settle for lots of chickens.
- PhantomGremlin 5y agoThat's a good point. The "strong oxen" Cray was originally talking about are now totally unachievable, compared to settling for lots of chickens.
- lowbloodsugar 5y agoThese 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/ https://www.top500.org/lists/top500/2020/11/
- lowbloodsugar 5y agoIf you had to digest a million grains, which would you rather use?
- Enginerrrd 5y agoIt's out of my depth, but my guess is on sething DES related. Here's a link to some possibly relevant discussion about it. http://www.icodeguru.com/Embedded/Hacker's-Delight/050.htm http://www.icodeguru.com/Embedded/Hacker's-Delight/050.htm
- thomasmg 5y agoSuccinct (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 << n in the value; basically flip the operands. I found this quite fascinating. For details, there is a short paper on this: "A Fast x86 Implementation of Select". I wonder if those succinct data structures are in any way related to what NSA is doing. I think not, but who knows.
- Bayart 5y agoThe paper, if anyone wants to save some clicks : https://arxiv.org/abs/1706.00990 https://arxiv.org/abs/1706.00990
- yvdriess 5y agoI've seen it used for large-scale genomics. Saving a few bits if you're dealing with billions of a thing is very useful. They're also vital for being able to pack as much of a datastructure (e.g. a graph) on a single node. Some graph algorithms, e.g. random walks, are latency bound and scale really badly in a distributed system.
- Sniffnoy 5y agoHeh, so it's an instruction for INTERCAL's "select" (~) operator...