15 ms·

Popcount CPU instruction

• vchak1 7y ago
  Popcount is also very valuable in search (bitmap) indexes, for example roaring bitmap by Lemire uses it quite a bit.
  • eesmith 7y ago
    Though, interestingly, if AVX2 is available then Lemire's CRoaring package uses a Harley-Seal popcount implementation, at https://github.com/RoaringBitmap/CRoaring/blob/master/include/roaring/bitset_util.h#L286 https://github.com/RoaringBitmap/CRoaring/blob/master/includ... , rather than the POPCNT64 instruction. Because it's faster - https://arxiv.org/abs/1611.07612 https://arxiv.org/abs/1611.07612 .
    • robocat 7y ago
      From the arxiv pdf: "We disabled Turbo Boost and set the processor to run at its highest clock speed" for their comparison. Doesn't their setup bias towards the AVX2 solution?
      • dalke 7y ago
        For what it's worth, I've tested my AVX2 copy of their code on a couple of different machines, and found it faster than my POPCNT-based implementation. (See my comments elsewhere here.) Here's my laptop numbers for my benchmark: 2048 Tanimoto (RDKit Morgan radius=2) 1000 queries chemfp search using threshold Tanimoto arena, index, single threaded (popcnt_128_128) threshold T=0.4 popcnt 19.33 ms/query (T2: 19.81 ms check: 189655.09 run-time: 39.2 s) (allow specialized) chemfp search using threshold Tanimoto arena, index, single threaded (avx2_256) threshold T=0.4 avx2 12.63 ms/query (T2: 14.04 ms check: 189655.09 run-time: 26.7 s) (allow specialized) That's 19.33 ms/query on 2048-bit (256 byte) bitstrings using POPCNT unrolled to two loops of 128 bytes each, and 12.63 ms/query using AVX2 specialized for 256 bytes. My testing showed there was no advantage for a fully unrolled POPCNT implementation. One thing to know is that there is only one execution port for POPCNT on my Intel processor. An AMD processor with 4 execution ports (Ryzen, I think?) may be faster. I don't have that processor, and my limited understanding of the gcc-generated assembly suggests it isn't optimized for that case.
        • robocat 7y ago
          > An AMD processor with 4 execution ports (Ryzen, I think?) may be faster. FYI m0zg agreed: "AMD can retire 4 (!) popcounts per cycle per core, if your code is able to feed it": https://news.ycombinator.com/item?id=20916023 https://news.ycombinator.com/item?id=20916023
      • nkurz 7y ago
        I'm one of the authors on the paper. This is a good point. I think the answer is "it might". In practice (as 'dalke' points out) the AVX2 approach still ends up faster on common Intel hardware with Turbo enabled, but there might be cases where it doesn't, and the measured degree of difference certainly might change with Turbo on or off. Complicating things, some but not all AVX2 operations benefit from Turbo frequencies as well. It depends on other things on the exact mix of instructions. The technical term is "license", and regardless of the setting of Turbo you processor chooses a frequency depending on the license that the instruction mix allows. Daniel has a blog post (co-written with Travis) on how this affects AVX512, but it also affects AVX2: https://lemire.me/blog/2018/09/07/avx-512-when-and-how-to-use-these-new-instructions/ https://lemire.me/blog/2018/09/07/avx-512-when-and-how-to-us.... The specifics are not well documented, and Travis probably has the best understanding of the exact behavior of anyone I know. Anyway, we turn Turbo off and try to run the processor at a constant frequency because it makes some of our other measurements more reliable, but yes, when making claims that a SIMD solution is faster than a scalar solution, we should probably be testing whether the conclusion holds even when we turn Turbo back on. I think it's still best practice to do most measurements with it off, but I'll try to remember to do an extra test with it turned of if comes up in future papers.
        • robocat 7y ago
          Thanks for your answer - great blog link - most relevant: "Intel made more aggressive use of AVX512 instructions in earlier versions of the icc compiler, but has since removed most use unless the user asks for it with a special command line option.". For other readers, short summary copied from the link with very light editing: * There are heavy and light AVX instructions. "Heavy" instructions roughly are those involving floating point operations or integer multiplications operating on 512 bits. * Intel cores can run in one of three modes: license 0 (L0) [normal], license 1 (L1) is slower, and license 2 (L2) is the slowest. To get into license 2, you need sustained use of heavy 512-bit instructions, where sustained means approximately one such instruction every cycle. * The processor does not immediately move to a higher license when encountering heavy instructions: it will first execute these instructions with reduced performance (say 4x slower) and only when there are many of them will the processor change its frequency. Otherwise, any other 512-bit instructions will move the core to L1. * Downclocking is per core and for a short time after you have used particular instructions (e.g., ~2ms). * The downclocking of a core is based on: the current license level of that core, and also the total number of active cores on the same CPU socket (irrespective of the license level of the other cores). The constraints and suggested workarounds are complex. Also the word choice "license" by Intel is bizarre (since it implies the throttling is to reduce performance for business reasons rather than technical reasons?).
• kardos 7y ago
  The fact that GCC and Clang can identify a manual implementation of count-bits-set and substitute it with an invocation of popcount is fascinating. What other idioms of similar or higher complexity can these compilers recognize and convert to instructions?
  • vinkelhake 7y ago
    Byte (endian) swapping is another one. GCC and Clang can recognize (some) implementations of that and replace with single instruction version (like bswap).
    • account42 7y ago
      On the other hand until relatively recently they have been bad at recognizing loads/stores of larger integers implemented using byte loads and shifts and then optimizing that into larger loads (for architectures where unaligned loads are allowed). Doing it this way allows you to completely delegate any little/big/weird endian concerns to the compiler.
  • woodruffw 7y ago
    > What other idioms of similar or higher complexity can these compilers recognize and convert to instructions? Both GCC and clang (really LLVM) will try to autovectorize your loops, replacing operations on individual words with SIMD instructions (provided the compilation target supports them). Similarly, both should replace `popcnt`-style functions (e.g., count-leading-zeros) with their instruction equivalents, provided the implementation is idiomatic enough. The overarching challenge is that users who don't know about instructions like `popcnt` and `clz` are also less likely to write implementations that are easy to detect and swap.
    • vnorilo 7y ago
      I don't recall seeing bit counting in the LLVM idiom recognition, but it's been years since I pored over it. Could you maybe Godbolt an example where this substitution happens? I'd be happy to be wrong in this case :)
• pacaro 7y ago
  I used to use "implement popcount" as an interview question (for c programmers), I'm not super convinced that it was a good question, although it definitely tells you quite quickly how comfortable a candidate is with bit manipulation. There are three or four reasonable ways to implement it in c, including one weird trick, but which is most efficient tends to be very CPU dependent (at the time I worked on a project that targeted four or five esoteric CPUs so I had the luxury of being able to verify this)
  • ajxs 7y ago
    Can you share the different ways it was done? Everything in your post sounds quite interesting.
    • dalke 7y ago
      I can. About 10 years ago I put together a series of blog posts on the topic. It's even referenced from the linked-to article. Most of the algorithms are described at http://www.dalkescientific.com/writings/diary/archive/2008/07/03/hakmem_and_other_popcounts.html http://www.dalkescientific.com/writings/diary/archive/2008/0... . http://dalkescientific.com/writings/diary/archive/2011/11/02/faster_popcount_update.html http://dalkescientific.com/writings/diary/archive/2011/11/02... has a link to http://dalkescientific.com/writings/diary/popcnt.cpp http://dalkescientific.com/writings/diary/popcnt.cpp containing implementations in a benchmark. That code only goes up to the POPCNT instruction. Faster implementations use AVX2 instruction set to implement the Harley-Seal algorithm, and there's VPOPCNTDQ in AVX 512 which does 512 bits at a time. Table of my preprint at https://chemrxiv.org/articles/The_Chemfp_Project/7877846 https://chemrxiv.org/articles/The_Chemfp_Project/7877846 shows the comparison of the most reasonable algorithms (for my definition of 'reasonable') on relatively modern hardware. For my case, the AVX2 implementation, fully optimized, is 11x faster than a lookup table and 30% faster than AVX2. Note that my case handles (typically) multiword popcounts containing 512-2048 bits. Some of the implementations sum the popcount of each word, a few of them use techniques to work on multiple words at a time. (For example, the Gillies-Miller method for "sideways addition" - an old term for popcount - dates from the 1950s. https://archive.org/details/programsforelect00wilk/page/190 https://archive.org/details/programsforelect00wilk/page/190 . )
• classichasclass 7y ago
  Power ISA has it too. I'm hard pressed to think of a modern architecture that doesn't have it.
  • CalChris 7y ago
    RISC-V delegates pcnt to the “B” Standard Extension for Bit Manipulation, and the status of B version 0.90 is Open, meaning it hasn't been finalized. So realistically, RISC-V doesn't have the pcnt instruction. Versions supporting B will have it but that will be at some point in the future.
  • saagarjha 7y ago
    I don’t think ARM does, but there might be some NEON thing that you can use to do something equivalent.
    • vaibhavsagar 7y ago
      ARM NEON includes it as VCNT: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dui0489h/CIHCFDBJ.html http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc....
      • saagarjha 7y ago
        Huh, it looks like that only works on 1-byte values? That’s an interesting choice.
        • m0zg 7y ago
          Worse, it's a fertile ground for "interesting" bugs, because VADDV (which sum-reduces the result) reduces into an 8 bit uint. So if you e.g. accumulate two or more quadword VCNTs into a uint8x16_t and then VADDV it, you could end up with something other than the actual overall bit count (because 2 quadwords can have _256_ bits set). Same with accumulating 8 or more VADDVs, except now individual bytes could wrap around if you don't widen in between.
    • 7y ago
• dboreham 7y ago
  Yikes I remember reading that thread on usenet. John Nagle, Rob Warnock and Roger Shepherd. Good times. Roger oddly didn't mention the story about guys in black suits and mirrored sunglasses showing up as the reason the T414 lacked popcount but the T800 added it.
• oconnor663 7y ago
  If you're building a binary tree incrementally, comparing the length of your stack of partially completed subtrees to the popcnt of the number of leaves so far tells you how many subtrees you need to merge :)
• monday_ 7y ago
  One way popcount is useful not mentioned in the OP is in the graph analysis. For example, you can use the following std::bitset<N>* graph = new std::bitset<N> [N]; to store the adjacency matrix for a graph with up to N vertices in N^2 bits of memory. The nice thing is that std::bitset::count uses popcount to compute the number of bits set to one. This makes some graph operations extremely fast even for a pretty large N. For example, graph[i].count() will produce a degree of a vertex and (graph[i] & graph[j]).count() will produce a number of vertices adjacent to both i and j.
  • snovv_crash 7y ago
    Careful, std::bitset.count() doesn't use popcnt on msvc, only gcc and clang.
    • monday_ 7y ago
      Thanks for the warning. Fortunately, I'm using it with gcc.
    • ncmncm 7y ago
      Popcount was not supported on the original AMD64 ISA. You have to tell your compiler to generate code for a recent chip before it will generate the instruction.
      • snovv_crash 7y ago
        That still doesn't work. Here is an example with codegen for AVX2, and an intrinsic call to popcnt, that still doesn't use popcnt for std::bitset.count() with a bitset size of 32 bits. Compare it to the GCC generated code. https://godbolt.org/z/27TmQY https://godbolt.org/z/27TmQY
        • ncmncm 7y ago
          I guess you're talking about MSVC. I find it hard to care much what that does. Code where performance matters much is not built with it. But you're right, their std lib not using their own intrinsic is pathetic.
• dclowd9901 7y ago
  We used a “popcount” style operation + bitwise AND to determine how similar two people were by interest. We had a bitmap where each bit represented an interest and 1 meant they had that interest and 0 meant they did not. Bitwise AND filters out the non overlapping interests and popcount to measure the “intensity” of their similarity (to tease out people who had almost every or almost no interests selected matching others like that — bell curve kind of thing).
  • gpderetta 7y ago
    generally, popcnt is useful to implement the Jaccard Distance [1]: J(X,Y) = |X∩Y| / |X∪Y| So, implementing the sets X and Y as bitsets it becomes: [1]: https://en.wikipedia.org/wiki/Jaccard_index https://en.wikipedia.org/wiki/Jaccard_index J(X,Y) = popcnt(X&Y) / popcnt(X|Y)
    • dalke 7y ago
      If anyone needs that to go fast, for fixed-length (up to ~4k bits) try out my code, chemfp at http://chemfp.com/ http://chemfp.com/ . It's designed for cheminformatics, but can work with any data set which can be described by a fixed-length byte string and an identifier.
• geoffhill 7y ago
  I like popcount for converting a 2^N-bit uniformly-distributed random number into a N-bit binomially-distributed one. Each bit of the input simulates a random coin flip.
  • eru 7y ago
    You are a wasting a lot of random bits this way, don't you?
    • adtac 7y ago
      Not if you already have 2^n bits at hand. In fact, if you have 2^n bits of entropy, popcount is probably more efficient than generating n more bits randomly.
    • JoachimSchipper 7y ago
      Sure, but generating random bits is fast with e.g. AES-NI, RdRand or a software implementation of e.g. ChaCha.
• kristianp 7y ago
  The Popcount instruction seems to be a meme on hacker news. You're cool if know about it and cooler if you've used it. That aside, this article is a good one for applications of it.
  • ncmncm 7y ago
    Knowing when to use bitmap representation, ops, and popcount is a kind of superpower. When it is the right thing, it makes your program 10x faster.
    • gmueckl 7y ago
      Thus can be said about almost all CPU instructions. x64 has tons of SIMD intrinics. You can do absolutely crazy stuff with them if you are willing to invest the time.
      • ncmncm 7y ago
        True enough, but bitmaps are very easy to use portably, with just &, |, ~, ^, and ++ operations. The only exotic needed very frequently is popcount, but you get that portably from std::bitset (except, evidently, in MSVC). The compilers are perfectly happy to keep an unsigned and a bitset variable in the same register, so that assigning from one to the other is a no-op.
• ncmncm 7y ago
  It's kind of pathetic that the RISC-V core instruction set lacks popcount. Besides all its immediate uses, it is essential to a fast integer logarithm.
  • eleson 7y ago
    It is part of the Bit Manipulation extension. So is count leading zeros. Unfortunately it is still in draft. The math extensions are not in draft.
    • ncmncm 7y ago
      Being in an extension means you can't count on it being there.
      • dralley 7y ago
        That's a feature (for hardware designers) not a bug. RISC V is not really designed to be a good high performance oriented ISA. They're aimed square at the embedded market.
        • ncmncm 7y ago
          It's a feature for hardware designers working with 250 nm transistors. Modern designers working with modern processes have the problem of discovering what they can throw a million transistors at that will actually make real programs faster. Hint: bitmanips!
• jongalloway2 7y ago
  .NET Core 3 (in preview, due out Sep 23) includes support for popcount as part of the BitOperations class: https://docs.microsoft.com/en-us/dotnet/api/system.numerics.bitoperations https://docs.microsoft.com/en-us/dotnet/api/system.numerics..... There's a recent post describing hardware intrinsics in .NET Core: https://devblogs.microsoft.com/dotnet/hardware-intrinsics-in-net-core/ https://devblogs.microsoft.com/dotnet/hardware-intrinsics-in... There are a lot of potential use cases, but one of the early discussions was around quickly scanning for known HTTP headers. You can see that in use here: https://github.com/aspnet/AspNetCore/blob/caa910ceeba5f2b2c02c47a23ead0ca31caea6f0/src/Servers/Kestrel/shared/KnownHeaders.cs#L646 https://github.com/aspnet/AspNetCore/blob/caa910ceeba5f2b2c0... If you really need help falling asleep, here's the discussion going back to 2015: https://github.com/dotnet/corefx/issues/2209 https://github.com/dotnet/corefx/issues/2209 Disclaimers: Microsoft employee, Nazgûl
  • omgtehlion 7y ago
    Cool! It would be nice to get bitscanforward/reverse too. I created this library long ago to get popcnt on desktop .net: https://github.com/omgtehlion/netintrinsics https://github.com/omgtehlion/netintrinsics Blog post with more details (in Russian): https://m.habr.com/ru/post/239619/ https://m.habr.com/ru/post/239619/ EDIT: found lzcnt/tzcnt on a linked page, thanks! But what about bswap or I'm asking too much? ))
  • non-entity 7y ago
    .NET is getting some really cool stuff lately. Sadly, it'll likely be irrelevant to me for the time to come
  • vaibhavsagar 7y ago
    GHC also includes a `popCount` function that is implemented in terms of the built-in instruction: https://haskell-works.github.io/posts/2018-08-22-pdep-and-pext-bit-manipulation-functions.html#availability-on-ghc https://haskell-works.github.io/posts/2018-08-22-pdep-and-pe...
• winrid 7y ago
  The coolest part of this for me is that compilers can optimize this stuff out and replace it with the machine instructions. I know that optimizing compilers do some amazing things, but detecting this particular case is pretty cool.
  • snailmailman 7y ago
    I highly recommend Matt Godbolt's talk "What has my compiler done for me lately?"[0] and its follow-up[1]. Both are great presentations going into details on some of the crazy optimizations compilers will do. As someone who knows very little about the inner workings of compilers my mind was blown when I saw some them. [0] https://www.youtube.com/watch?v=bSkpMdDe4g4 https://www.youtube.com/watch?v=bSkpMdDe4g4 [1] https://www.youtube.com/watch?v=nAbCKa0FzjQ https://www.youtube.com/watch?v=nAbCKa0FzjQ
    • winrid 7y ago
      Fantastic. Adding to my watch list.
• zzo38computer 7y ago
  MMIX has a "SADD" instruction, which does popcount(x&~y). (You could use this to count trailing zeros with two instructions, each taking only one clock cycle.) I thought JavaScript ought to have a built-in popcount function for the new integer type, but last I checked, it doesn't have. (It would be faster than writing JavaScript code to emulate it.) (I can think of uses for popcount on arbitrary length integers. Of course this won't work with negative numbers (I don't care what it does if the input is negative, although they should define what it does in that case), but for nonnegative numbers would be good to have.) I have also used the __builtin_popcount function in GNU C. I did not know that it can detect an implementation of popcount and replace it; I have just used the built-in function. I also did not know of all of the uses mentioned in the linked document (but I did know of some other uses).
  • zamadatix 7y ago
    WASM has ctz and it's honestly the better place for such a low level instruction. BigInt is getting some of the bitwise ops (https://github.com/tc39/proposal-bigint/blob/master/ADVANCED.md https://github.com/tc39/proposal-bigint/blob/master/ADVANCED...) but just the higher level ones at this time. JavaScript does have clz32 from back before WASM was the new target for compile-system-language-to-browser but not ctz32 and I doubt it'd be added as that's no longer the focus.
• ncmncm 7y ago
  The Bitmanip extension definition document for RISC-V explains a wide variety of what were, for me, unfamiliar but terribly useful bitwise operations. Well worth reading even if you have no particular interest in RISC-V. Many of the instructions detailed have analogs in AVX, NEON, and recent POWER instruction sets. Often these instructions are poorly explained in the official manuals.
• MauranKilom 7y ago
  I've used _BitScanReverse (popcount-ish MSVC intrinsic) with a custom octree indexing scheme, where higher level voxels have more unset bits from the left. Neat stuff.
• tom_mellior 7y ago
  For whatever it's worth, this article is a good example of why HN's (only theoretical, by now) policy of keeping the original headline intact makes sense. I wouldn't have clicked on an article with the title "You Won’t Believe This One Weird CPU Instruction!", and I would not feel regret.
  • MaxBarraclough 7y ago
    > For whatever it's worth, this article is a good example of why HN's (only theoretical, by now) policy of keeping the original headline intact makes sense. Did you mean doesn't make sense?
• m0zg 7y ago
  Be aware though that Intel POPCNT instruction throughput is pretty low by today's standards. When you need to popcount a lot of bits, on Intel it might make sense to do it without the use of POPCNT. This oldie but goodie still holds, on Intel: https://danluu.com/assembly-intrinsics/ https://danluu.com/assembly-intrinsics/ In contrast, AMD can retire 4 (!) popcounts per cycle per core, if your code is able to feed it. There's vectorized popcount in some of the optional AVX512 instruction sets, but for those to make it into consumer CPUs AMD would really have to hurt Intel pretty bad, marketshare-wise. :-)
• hjorthjort 7y ago
  It's also an instruction in WebAssembly, which has a pretty sparse instruction set. There are only 29 integer operations, and this is one of them. There are also "clz" and "ctz" which count leading and trailing zeroes. Other than that all the instructions are run-of-the-mill arithmetic, comparison, bitmasking and shifting.
• majke 7y ago
  There is more! You can be _faster_ than __builtin_popcount()! Wojciech Muła did an excellent SSSE3 implementation: http://0x80.pl/articles/sse-popcount.html http://0x80.pl/articles/sse-popcount.html My understanding is that the set-up time is slower than the POPCNT cpu instruction, but throughput is higher. Useful if you need to count bits not on a register, but on a whole array.
  • dalke 7y ago
    It looks the conclusion is that the POPCNT instruction ("cpu") is faster than any of the SSE implementations. Only AVX2 outperforms POPCNT, and only for large enough bitstrings.
    • majke 7y ago
      On i7: > AVX2 code is faster than the dedicated instruction for input size 512 bytes and larger The difference is indeed tiny. Still - it's very cool the generic AVX2 code can beat the instruction burned in the silicon!
• nabla9 7y ago
  Revisiting POPCOUNT Operations in CPUs/GPUs https://homes.cs.washington.edu/~cdel/papers/spost106s1-paper.pdf https://homes.cs.washington.edu/~cdel/papers/spost106s1-pape...
• guytv 7y ago
  popcount reminds me of my first Map-Reduce program. It seems that I "reduced" by popcounting.
• amelius 7y ago
  Peculiar name. I would have named that "bitsum".
  • dalke 7y ago
    The original name was "sideways addition". There are many other names, including Hamming weight. The Wikipedia entry for Hamming weight says the HP-16C developers agree with you: > Some programmable scientific pocket calculators feature special commands to calculate the number of set bits, e.g. #B on the HP-16C[3][17] and WP 43S,[18][19] #BITS[20][21] or BITSUM[22][23] on HP-16C emulators, and nBITS on the WP 34S.[24][25]
• markh1967 7y ago
  I think the most probable reason for this instruction is for calculating parity bits. This would need to be done fast so it makes sense that there would be a CPU instruction to do most of the work.
  • kps 7y ago
    Parity is much easier than counting. It's so easy that you get it for free in the x86 flags register. (… and because the 8008 was designed to run a terminal.)
    • bogomipz 7y ago
      >"(… and because the 8008 was designed to run a terminal.)" Could you elaborate on this? How does the 8008 being designed to run a terminal relate to the parity and the flags register?
      • kps 7y ago
        Each iteration from the 8080 through x64 have a parity bit in the flags register for backwards compatibility with the previous generation. The 8008 was a microprocessor implementation of the Datapoint 2200 architecture.
        • bogomipz 7y ago
          Excellent, thanks for the insights. Cheers.
      • ryacko 7y ago
        Early protocols didn’t have error correction in the lower layers. The parity flag was equivalent to a CRC instruction nowadays. Presumably if parity was incorrect, that would mean the byte was transmitted incorrectly.
• thom 7y ago
  Popcount comes up in chess engine programming, where boards are regularly represented as a series of bits for each type of piece. The Chess Programming Wiki has a lot of information about both usage and implementation: https://www.chessprogramming.org/Population_Count https://www.chessprogramming.org/Population_Count
• Vizarddesky 7y ago
  Popcount is not at all unusual in ordinary bit-twiddling.
• unhammer 7y ago
  https://haskell-works.github.io/posts/2018-08-22-pdep-and-pext-bit-manipulation-functions.html https://haskell-works.github.io/posts/2018-08-22-pdep-and-pe... from the series https://haskell-works.github.io/ https://haskell-works.github.io/ shows how to use popcnt (and rank-select) in a Haskell CSV parser
• collyw 7y ago
  MySQl includes a native popcount instruction, Postgres didn't when I checked a few years back. I actually needed it at the time.
  • jonatron 7y ago
    It's surprisingly easy to implement a popcount user defined function in C for postgres. It would be a problem for hosted postgres with extension restrictions though.
• twoodfin 7y ago
  The same computer architect who first told me about popcount's desirability to the NSA also believed that the massive simultaneous multithreading first introduced to the HPC world commercially by Tera—now owner of the "Cray" name—was also a big win for the spooks.
• deleted 7y ago
  [deleted]
• itodd 7y ago
  I've used this in an effort to calculate hamming distances of encoded equal length strings of dna.