6 ms·
The moral is that POPCNT is critical to zillions of massive optimizations, and omitting it from base instruction sets, as has been done over and over and then l
by moloch-hai 4y ago
The moral is that POPCNT is critical to zillions of massive optimizations, and omitting it from base instruction sets, as has been done over and over and then later corrected, each time at great expense, is extremely foolish. The latest offender was RISC-V, but the overwhelming majority of x86 code is still compiled to a target version lacking it.
- adrian_b 4y agoIt is good to remember that the instruction POPCNT was introduced for the first time in the instruction set of a computer by Alan Turing, already in 1949, in Ferranti Mark I (as "sideways add"). Unfortunately few other computers have included it before Cray 1, which made it well known, under the current name.
- pklausler 4y agoWe had it on the CDC 6600 in 1963 as 'Bi NXj' if I remember rightly.
- js2 4y agoSideways add makes a bit of sense for the name of this operation. But I can't figure out why Cray named it "population count." It just seems odd to refer to the set bits as part of a population that you're counting.
- DannyBee 4y agoWell, actually, in this case, no, POPCNT is unnecessary here, since you don't actually have to count anything. you only need to know if the bitmask changed when you added a new character ;) But otherwise, yes. I spent quite a while optimizing GCC's bitmap operations years ago, including implementing some new sparse bitmap types, and the sparse bitmap types i implemented ended up dependent on the speed of popcnt and friends, so yes.
- nebulous1 4y agoit's not sufficient that the newest character in the window is unique? the older characters need to be unique too.
- DannyBee 4y agoI posted how to do it in another comment on the thread.
- rep_lodsb 4y agoInput: "abccdef" Your algorithm will report a match at "bccd" since the "a" wasn't removed from the bitmask.
- DannyBee 4y agoYes, you are correct you would have to xor them back out
- actionfromafar 4y agoI swear I have seen this conversation before. A glitch?
- DannyBee 4y agoNo - he responded on both parts of the thread where i commented. I started to respond here as well, then updated it to redirect to the other comment so we don't end up with two long threads.
- nerpderp82 4y agoIf you XOR them together, you get back to the original conversation.
- nebulous1 4y agoIf you're using OR (unlike the OP) how are you removing the left side of the window? And still, even if the newest character is unique, previous characters might not be
- syrrim 4y agoIn practice if you want the popcount of anything larger than a couple registers you'll want to use vector instructions anyways though. There are a lot of operations that will speed up certain applications if made into their own instruction, not all of them need to be.
- gpderetta 4y agolegend say that popcnt was the "NSA" instruction, was heavily used for cryptographic analysis and that was kept out of common instruction sets for a long time to give NSA an advantage. It is probably just a legend though.
- kjs3 4y agoThe usefulness of popcnt, et al, in cryptography was known at least as far back as Alan Turing. It wasn't 'kept out of' ISAs, if for no other reason than not all computer manufacturers were (are) American, so the NSA wouldn't have had much leverage to keep, say, Ferranti or Hitachi from including it in their computers. The legend you're probably misremembering is the one where the NSA approached Seymor Cray at CDC while he was designing the 6600 super and 'suggested' that if he included a popcnt instruction in the ISA, the NSA would certainly look favorably on purchasing some. He did and they did (quite a few). This story is also possibly apocryphal.
- _a_a_a_ 4y ago> The usefulness of popcnt, et al, in cryptography was known at least as far back as Alan Turing Ok. Why?????????????? @gpderetta is correct at least in quoting hacker's delight where it was also said to be rumoured the NSA wanted popcount but it was unclear to HD's author why they wanted it.
- moloch-hai 4y agoI think it is generally taken as useful in, specifically, cryptanalysis, presumably for estimating Hamming distance.
- rep_lodsb 4y agoIIRC the Colossus machine built during WW2 was basically counting the number of bits resulting from doing various boolean operations on the input. It was used to crack the Lorenz cipher, which XORed the plaintext with a pseudo-random keystream (generated using mechanical rotors!). Cryptography has advanced since then - and I'm not an expert - but there may still be statistical weaknesses that could be found by counting bits?
- snvzz 4y ago>RISC-V Doesn't B have a POPCNT? B is mandatory in RVA22.
- cbm-vic-20 4y agoThese are the cpop and cpopw instructions. https://github.com/riscv/riscv-bitmanip/blob/main/bitmanip/insns/cpop.adoc https://github.com/riscv/riscv-bitmanip/blob/main/bitmanip/i...
- moloch-hai 4y agoCan you buy any RISC-V embodiment that implements such an instruction? It seems to be extremely optional.
- Vt71fcAqt7 4y agoB is pretty recent, but Sifive p650 will have it https://www.sifive.com/cores/performance-p650 https://www.sifive.com/cores/performance-p650 Heres another: https://www.andestech.com/en/2022/12/08/andes-technology-unveils-the-andescore-d23-a-feature-rich-low-power-and-highly-secured-entry-level-risc-v-processor/ https://www.andestech.com/en/2022/12/08/andes-technology-unv... I expect all future Linux cores to have it
- snvzz 4y ago>I expect all future Linux cores to have it All RVA22 profile cores will, as RVA22 requires B extension. >Sifive p650 will have it Current versions of U74 also have it. And a U74 with B is already shipping in VisionFive 2.
- snvzz 4y agoIt is part of B extension, so it should be available in the VisionFive2 (now being shipped), which has the newer version of SiFive U74 that has B.
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- dubya 4y agoI never think of POPCNT because it's not a language primitive in any languages I use. I would do it by storing the product of the counts; divide by the outgoing count before decrementing, multiply by the incoming count after incrementing. If the product is one they're all unique. Scaling should be comparable to POPCNT.