8 ms·
Popcount CPU instruction (2019)
- WaffleIronMaker 3y agoIf you want to learn more about Hamming Codes from a mathematical perspective, I recommend 3Blue1Brown's YouTube series: > How to send a self-correcting message (Hamming codes) - https://youtu.be/X8jsijhllIA https://youtu.be/X8jsijhllIA > Hamming codes part 2, the elegance of it all - https://youtu.be/b3NxrZOu_CE https://youtu.be/b3NxrZOu_CE Associated with Ben Eater's video, if you want a perspective regarding low level computer hardware: > What is error correction? Hamming codes in hardware - https://youtu.be/h0jloehRKas https://youtu.be/h0jloehRKas
- adrian_b 3y ago> it has in fact been present in CPU architectures since at least 1961 Actually it was present for the first time in an electronic computer already in February 1951 in Ferranti Mark I, which was the first commercially available electronic computer, slightly before Univac I. "Population count" is a name that was first used in Cray-1 (1976). In Ferranti Mark I, this instruction was named "sideways add" and this was one of a few instructions that had been included in its instruction set at the request of Alan Turing, so he is the original author of this "weird" instruction. In CDC 6600 (August 1963), the name of this instruction was “sum of 1’s”.
- Sharlin 3y ago> this instruction was named "sideways add" An early instance of what's now more commonly called a "horizontal" operation in the context of SIMD.
- stabbles 3y agowhich are slow. If you wanna count the number of occurrences of a certain character in a string, you ultimately have to use popcount on an ordinary register, there's no corresponding SIMD instruction (at least in <= AVX2). Something along the lines of: __builtin_popcount(_mm256_movemask_epi8(_mm256_cmpeq_epi8(haystack, needle))); So, if you wanna avoid horizontal reductions, you better sum the result of _mm256_cmpeq_epi8 and effectively keep track of 32 counters of 1 byte integers. Meaning that you have an outer loop over the string, and a fixed-length inner loop of 255 iterations in which you accumulate counts, and after the inner loop a horizontal sum. Then you go from 1 horizontal operation per iteration, to 1 horizontal operations per 255 iterations.
- ack_complete 3y agoThere is actually such an instruction, psadbw (_mm_sad_epu8). It's not any noticeably faster for the scenario you describe since it only affects the outer loop, but it does avoid needing the popcnt instruction since psadbw only requires SSE2.
- 10000truths 3y agoWith AVX512, you can use masking and the vpopcntb instruction to avoid moving values between GPRs and vector registers until the very end: uint64_t count_occurrences(const __m512i* vec_string, size_t num_vecs, char target) { __m512i count_vec = _mm512_set1_epi64(0); __m512i target_vec = _mm512_set1_epi8(target); __m512i increment_vec = _mm512_set1_epi8(1); for(size_t i = 0; i < num_vecs; ++i) { __mmask64 cmp_mask = _mm512_cmpeq_epu8_mask(target_vec, vec_string[i]); count_vec += _mm512_maskz_popcnt_epi8(cmp_mask, increment_vec); } return _mm512_reduce_add_epi64(count_vec); }
- svat 3y agoIndeed, Knuth writes in TAOCP Vol 4A (in section "7.1.3. Bitwise Tricks and Techniques", previously pre-fascicle 1a: https://cs.stanford.edu/~knuth/fasc1a.ps.gz https://cs.stanford.edu/~knuth/fasc1a.ps.gz): > Early machine designers provided fullword bitwise operations in their computers primarily because such instructions could be included in a machine’s repertoire almost for free. Binary logic seemed to be potentially useful, although only a few applications were originally foreseen. […] The Manchester Mark I computer, built at about the same time, included not only bitwise AND, but also OR and XOR. When Alan Turing wrote the first programming manual for the Mark I in 1950, he remarked that bitwise NOT can be obtained by using XOR (denoted ‘≢’) in combination with a row of 1s. R. A. Brooker, who extended Turing’s manual in 1952 when the Mark II computer was being designed, remarked further that OR could be used “to round off a number by forcing 1 into its least significant digit position.” By this time the Mark II, which was to become the prototype of the Ferranti Mercury, had also acquired new instructions for sideways addition and for the position of the most significant 1. The "sideways add" operation (aka population count, sum of binary digits, number of 1s, …) finds mention in all five (so far) volumes of TAOCP, and he even uses a special notation νx for the sum of the bits of x. It has always been of interest (from later in the same volume): > The first textbook on programming, The Preparation of Programs for an Electronic Digital Computer by Wilkes, Wheeler, and Gill, second edition (Reading, Mass.: Addison–Wesley, 1957), 155, 191–193, presented an interesting subroutine for sideways addition due to D. B. Gillies and J. C. P. Miller.
- jon_richards 3y agoAnd in 1955 you had Arithmetic Operations in Digital Computers. https://archive.org/details/arithmetic_operations_in_digital_computers/page/n11/mode/1up https://archive.org/details/arithmetic_operations_in_digital...
- dalke 3y agoIn case you are curious, here is the algorithm from that 1957 text book (2nd edition): https://archive.org/details/programsforelect00wilk/page/190/mode/2up?q=Gillies https://archive.org/details/programsforelect00wilk/page/190/... I never did sit down and figure out the notation. It isn't in the 1951 (1st edition), at https://archive.org/details/preparationofpro0000maur https://archive.org/details/preparationofpro0000maur
- vanderZwan 3y ago> at the request of Alan Turing Well, I can imagine there might actually have been a connection to cryptography then. Not NSA related though.
- jb1991 3y agoTitle checks out. I don’t believe a word of it.
- inetknght 3y ago> 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? It seems very useful. I've used it for several algorithms including DNA analysis and vectorized math.
- nwoli 3y agoIt’s of course useful, the question is it useful enough to warrant its own instruction
- inetknght 3y ago> It’s of course useful, the question is it useful enough to warrant its own instruction I argue: yes absolutely.
- chaboud 3y agoWhether it’s shift, mask, multiply, Kernighan’s method, or something else, it’s going to be multiple instructions and tens or hundreds of cycles to do this in software. pop count instructions take a handful of cycles to run (~10 on ARM, ~3 on Intel?). It’s one of those things that silicon can do very well.
- fear91 3y agoNew Intel/AMD CPU's do a register based popcount in a single clock.
- angiosperm 3y agoUsed to be three cycles. Unfortunately, the original AMD64 back in 200x lacked a popcount, so most software built for PCs even today lacks any instances of the instruction. Means to get the instruction generated are finicky, non-portable, and often result unexpectedly in a function call, instead. E.g., without a "-m" option, Gcc and Clang will turn "__builtin_popcount()" into a function call. Likewise, "std::popcount()" and "std::bitset<>::count()". Always use at least "-mavx".
- spacechild1 3y agoWhat's weird about popcount?
- Agingcoder 3y agoThat was my initial reaction as well. Counting bits arises quite naturally in many places.
- tialaramex 3y agoI'd guess to the "Surely my computer is a 1:1 mapping of the C programming language" people the expectation is that their CPU will have two increment instructions, two decrement instructions, and nothing like popcount. After all, C doesn't have a popcount operator. I have this terrible feeling that somewhere down the line we're going to get a generation of people who assumed the computer is a 1:1 mapping of Python -- a friend who teaches CS for a major university explained that they're going to teach Python as first language for Computer Science undergraduates starting 2024.
- automatic6131 3y agoHaving python as a first programming language isn't a big disadvantage. The core elements of program optimization are still there: making sure you don't accidentally write O(n2) code etc. even if the memory management is opaque, you end up with an idea of values vs references, stacks and heaps just from some surprising edge cases in the language.
- mhh__ 3y agoI'm worried about python being assumed to be the same as every language than every CPU.
- jpc0 3y ago> a friend who teaches CS for a major university explained that they're going to teach Python as first language for Computer Science undergraduates starting 2024 I think this is significantly more common than you think it is. Also python has an extremely rich type system, can be completely duck typed as well, and does effectively everything you would need to know about in a CS degree, at least in the first semester or two, other than manual memory management. Which is significantly easier when you have a firm grasp of other aspects of programming. There are multiple approaches to teaching, starting with python and then moving lower down later isn't necessary a bad move. Who says starting with assembly/C and moving up is a good move?
- deleted 3y ago[deleted]
- fear91 3y agoIt's a very useful instruction. Go uses it extensively in its core runtime and the compiler itself. I assume other languages do too if they care about performance. Examples: 1. Growing a slice. 2. Runtime's heap bitmap. 3. Page allocation. 4. malloc. 5. Register allocation.
- Aardwolf 3y agoWhy was there no standard operator for this in C since the 1970s? You got various bit shifts and bitwise logic operators, so why not this? std::popcount exists in C++ now since C++20, but that took a while if this instruction was in CPU's that long.
- dataflow 3y agoMaybe because it hasn't been in x86 CPUs that long. Like Intel added it in 2009 or so. And there were intrinsics for it so I'm guessing it wasn't a high priority.
- Someone 3y agoBecause almost nobody had a computer that supported it when C was created. That article mentions 3 cpu architectures that have the instruction in the 1970s: 1961: IBM Stretch 1964: CDC 6000 1975: Cray-1 After that, it mentions further support in 2005, with Sparc. Reading https://en.wikipedia.org/wiki/IBM_7030_Stretch https://en.wikipedia.org/wiki/IBM_7030_Stretch, a grand total of 9 IBM Stretch’s were sold. In comparison, the CDC 600 was a wild success, with “100+” sales (https://en.wikipedia.org/wiki/CDC_6600 https://en.wikipedia.org/wiki/CDC_6600) The Cray-1 scores similarly with “over 100” (https://en.wikipedia.org/wiki/Cray-1 https://en.wikipedia.org/wiki/Cray-1) C is from 1972 and started life for the PDP-7 and was soon ported to the PDP-11, of which “around 600,000” were sold (https://en.wikipedia.org/wiki/PDP-11 https://en.wikipedia.org/wiki/PDP-11; I guess most of these will have been sold late in the 1970s and early 1980s, but I think it’s a safe bet they were almost immediately more common than those 3 machines)
- matthews2 3y agoAt least GCC and Clang can recognise most sane implementations of popcount and replace it with an instruction.
- pantalaimon 3y agoWe do have `stdc_popcount()` now with C23
- sigsev_251 3y ago
- ralferoo 3y agoOn the PS3 SPU cores, the best "does everything" instruction was the single "rotate and mask" series of instructions which was the underlying implementation of all rotates, shifts, and bitfield extraction instructions. That architecture is still my favourite years on - every register was vectorised by default, and the instruction was the minimalistic set to achieve a lot of unusual operations that were incredibly useful for graphics or signal processing work. Often you couldn't find an exact instruction to do what you wanted, but if you studied the documentation long enough, you'd find one that generalised it and actually did do what you wanted, as well as gracefully handling loads of other edge cases you hadn't thought of - for instance the various instructions to create shuffle masks so that lots of byte/word/long re-ordering operations could be done with the single shuffle instruction, which could be used to emulate unaligned memory access using aligned-only memory accesses. Not exactly weird, but on the PowerPC side "eieio", is my most favourite name for an instruction on any architecture - without fail, every time I come across it, I start humming Old McDonald!
- Vogtinator 3y agoThere are similar instructions on PowerPC (rlwinm) and bfi/ubfx instructions on ARMv8.
- Everdred2dx 3y agoNot a whole lot of asm experience here- what does it mean for a register to be vectorized?
- nwallin 3y agoSIMD. Instead of having one value in one register, you have several values per register. (usually a small power of 2. SSE is 4 floats per register. AVX512 is 16 floats per register.)
- corysama 3y agoAnd, when you perform an operation on a register, like an add, the operation works on all of the values in that register simultaneously in a single instruction.
- jagrsw 3y agoHamming distance (and popcnt) is also used in gradient descent scenarios. Eg. here's part of fuzzing engine code, where it tries to produce an input which matches some form of variable check inside the fuzzed code: https://github.com/google/honggfuzz/blob/1f09e3bfb0785d9b31132ce84ec42f6293d49d9e/libhfuzz/instrument.c#L368 https://github.com/google/honggfuzz/blob/1f09e3bfb0785d9b311... register uint8_t v = ((sizeof(Arg1) * 8) - __builtin_popcount(Arg1 ^ Arg2)); uint8_t prev = ATOMIC_GET(globalCovFeedback->bbMapCmp[pos]); if (prev < v) { ...
- dbcurtis 3y agoAh yes, pop count. Back in my days as a CPU logic designer on refrigerated, walk-in, scientific mainframes, I was working on a vector processor that was intended to be a competitor to Cray-1, but sank due to poor marketing and a collapse in oil prospecting... but I digress. A few of us on the team had come from previous CPUs at other companies, and argued with the architecture committee that we should have a vector pop count instruction in order to get some interest from No Such Agency. Shot down, of course. When serial No. 1 was in initial benchmarking, two guys named Frank and George with No Last Names, who lived somewhere near Fort Mead, said they would buy at least one if we added vector pop count.
- bruce343434 3y agoI've read this story before but can't remember where
- dbcurtis 3y agoI suspect it played out multiple times at different companies.
- angiosperm 3y agoPopcount eventually gets added to every architecture that lacks it, always at great expense. You would think people would have learned by now. And, no, not typically just because the spooks want it.
- NotYourLawyer 3y agoWhy, then?
- angiosperm 3y agoBecause there are numerous order-of-magnitude optimizations it enables, that are useful far beyond cryptanalysis. People mention spooks because the spooks have often had access to enough money to force the issue.
- angiosperm 3y agoI still don't know of any RISC-V implementation that supports the POPC (and related) instructions. Would like to be pointed at any. It is generally a bad idea to field an instruction-set architecture that turns common, brilliant optimizations into gross pessimizations.
- camel-cdr 3y agoThe bit manipulation [0] extension has been ratified for a while now and is part of the RVA22 application extension profile [1]. You can already buy SOCs that support it, e.g. vision five 2 and star64. Interestingly the risc-v vector extension [2] has it's own popcount instructions for vector registers/register masks. This is needed, because the scalable architecture doesn't guarantee that a vector mask can fit into a 64 bit register, so vector masks are stored in a single LMUL=1 register. This works really well, because with LMUL=8 and SEW=8 you get 100% utilization of the single LMUL=1 vector register. Another interesting thing is that the vector crypto extension will likely introduce a element wise popcount instruction [3]. [0] https://github.com/riscv/riscv-bitmanip https://github.com/riscv/riscv-bitmanip [1] https://github.com/riscv/riscv-profiles https://github.com/riscv/riscv-profiles [2] https://github.com/riscv/riscv-v-spec https://github.com/riscv/riscv-v-spec [3] https://github.com/riscv/riscv-crypto/blob/master/doc/vector/insns/vcpop.adoc https://github.com/riscv/riscv-crypto/blob/master/doc/vector...
- angiosperm 3y agoThank you. It has generally been hard to discover exactly which extensions any given implementation supports, with usually most of any comprehensive documentation in Chinese. I hope for that to change.
- snvzz 3y agojh7110, the SoC used in the first large-scale run SBC, has popcnt as part of the related bit manipulation extensions. This is important, as it means that the first generation board to reach hordes of developers and enthusiasts is popcnt-capable.
- 3y ago
- fegu 3y agoHaskell added a function popCount in https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Bits.html https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-... some years ago to allow easy use of this operation where present.
- zzo38computer 3y agoBit population count is useful for many things. MMIX has SADD ("sideways add", which is also a bit population count), and also has MOR ("multiple OR") and MXOR ("multiple XOR"), which are also useful (for many purposes, including endianness conversion (even PDP-endian), reversing the bits in a byte, hashing, and others) but I had not seen on other instruction sets. In GNU C, you can use the function __builtin_popcount to make bit population count.
- cpach 3y agoIf you want an example where popcount is very useful, check out this challenge from Cryptopals: https://cryptopals.com/sets/1/challenges/6 https://cryptopals.com/sets/1/challenges/6
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- ks2048 3y agoI recently used popcount for an audio-fingerprinting project [0] to compute the difference in binary "audio fingerprints". With AVX2 and 4 cores, my desktop managed 448 billion bit-diff calcs per second! [0] https://kenschutte.com/phingerprint/ https://kenschutte.com/phingerprint/
- SushiHippie 3y agoReading the title I thought it was about debians popularity contest "popcon" https://popcon.debian.org/ https://popcon.debian.org/
- agubelu 3y agoTo add to some of the uses of popcount, it is also used in chess engines. Since a chess board has 64 squares, many engines use 64 bit unsigned integers to represent the whole board, mapping each square to a bit, which are called bitboards. Then, each combination of piece type and color is given its own bitboard, for example, a bitboard to represent the positions of white rooks. The squares attacked by a piece can similarly be represented by a bitboard. This in turn allows for the use of something called magic bitboards, which are essentially compressed lookup tables for the squares to which a rook or a bishop can move for every possible disposition of the board. Having all these possibilities precomputed speeds up move generation significantly. Popcount is used, for example, to know the amount of pieces of a certain type on the board, the number of squares to which a piece can move, or the amount of pieces attacking a given square.
- mmastrac 3y agoI would love to ask Gregory R. Travis what he did with it... The 6600 certainly had population count; I used it. Note that it was about the SLOWEST instruction in the whole instruction set. I'll have to dig out the COMPASS manuals when I get home and find out just HOW slow. Parity was never added to the 6000 line, that came with the 7000 line. Why did I use it? Well, I could tell you but I'd have to kill you
- tmoertel 3y agoAnother use of popcount: generating binomial random variates corresponding to n coin flips in early games. Rather than looping n times, flipping coins and counting heads, you generated a new random number, masked off the bottom n bits, and hit ’em with popcount.
- kragen 3y agoi used popcount for visual art purposes in http://canonical.org/~kragen/sw/dev3/trama.html http://canonical.org/~kragen/sw/dev3/trama.html, both because it's extremely cheap to compute and i was interested in patterns that were extremely cheap to compute, and because it figures prominently in the simplest definition of the hadamard-walsh matrix: popcount(row bitand col) bitand 1, which in the stack language of that program is xy& epilepsy warning, although the page doesn't flash much initially when loaded, it will probably flash a lot if you start playing with it
- scosman 3y agoI've used popcnt in prod in last 10 years. We were looking for similar images in large sets, using a perceptual hash (64 bits, at least 60 bits being same considered a match). Tried a few different solutions. Fancy vector databases. Clustering algos to reduce search space. A really neat custom O(n) algo that searched the set of possible solutions instead of the intersection of n^2 possible matches. The old fashioned N^2 solution ended up being fastest, simplest, and could handle quite large Ns, when the core of the loop was optimized with popcnt (well xor -> popcnt). Computers are fast.
- bionhoward 3y agoAt the risk of veering into crackpot territory, this operation is extremely profound and shows up in an absurd number of places. For example, imagine you like the number three, so you want to make a three letter alphabet (ternary, which has the optimal radix economy amongst integers) — the simplest way to do it is to connect the 3rd row of Pascal’s triangle (1, 2, 1) to the popcount of two bits. And lo, you have trits! Coincidentally, this maps 4D onto 3D in such a way that there are two different spins to the number one: 01 or 10. Hmmm…where have we seen “spin” before? It’s interesting to entertain the possibility that simple properties of the simplest possible strings of the simplest possible languages could explain all kinds of physical phenomena. And why wouldn’t they? Also, HAMTs are incredible, so if the only thing you could do with popcount was make HAMTs, it would already be incredible. Such a seemingly silly and mundane thing, how many hands are raised, how many coins flipped heads, how many voted for this or that candidate, I guess it’s just a tally function, but damn if I didn’t find myself astounded by the usefulness of popcount earlier this year. Not surprising to see it on hacker news. Great article, and timely. Now, will someone please tell me how popcount is involved in neural coding? Maybe it’s literally everywhere, even inside our own minds. Neurons vote for the presence of features, tally the votes, you can simplify your data substantially by not giving a bleep about whose hands are raised and instead only care about how many of them you can see. That’s also why the second law of thermodynamics is, as Arieh titled his book, plain common sense. The more coins you flip, the more ways you can flip the same popcount total (a dim event), even though there might be many different combinations of heads and tails in various possible coin flip sequences (specific event). So, yeah. Cheers to this one!
- grodes 3y agosimd and branchless
- junon 3y agoIt says that the popcount instruction is not very useful but I've needed in quite a lot in my time doing embedded, encoding/decoding or some special algorithms for storage in e.g. game engines.