5

Figuring out how many bits in a group of bits are set to 1, known as computing "population count", Hamming weight, or "bit summation", among others, has various applications.

It is also fairly cheap to implement in hardware to be executed as fast as a fixed point addition if not faster.

Likely for these reasons, CDC 6600 (1964) had CXi (47) described as Count the number of 1's in Xk to Xi specifically included in its quite short list of instructions, although IBM STRETCH (1961) had that capability first as a by-product of all logical operations.

Then, in the list of processors with the "popcount" instruction there are large gaps. Since CDCs and Crays, and until very late 1990s, only SPARC (designed in mid-1980s) had the POPC instruction.

Not a single IBM processor (not counting the aforementioned IBM STRETCH where there was no need for a separate instruction), not a single DEC processor (the instruction first appeared in an Alpha CPU when it was already Compaq's), not a single Motorola processor, not a single Intel or AMD processor until late 2000s, ...

As a result, innumerably many a software engineer had to implement the functionality of POPCOUNT by hand with various degrees of efficiency (even GCC introduced __builtin_popcount only in mid-2000s), and to endure silly interview questions about its efficient implementations.

What was going on? The wiki page doesn't discuss that aspect, but the many-decades long omission is so glaring that there had to be some musings on the subject by people "in the know".

I'm not asking people to speculate here; I'm asking for references to existing material about the lack of POPCOUNT in most of the CPUs of the last quarter of the XX century.

  • 2
    C++ compiler writers have been free to optimize std::bitset::count() using popcnt or equivalent since bitset was invented (1994?). When they actually started doing so requires more research. See: stackoverflow.com/a/45189920/966071 – snips-n-snails Sep 10 '17 at 2:25
  • 3
    Probably because ADD and SUB has more applications?. I can remember only a few occasions of wanting such an instruction in the last 20 years. – tofro Sep 10 '17 at 8:09
  • 2
    @tofro - I'm going to guess that you don't spend much time writing operating systems. This faciliity is extremely useful for memory management. If you have a word that contains one bit for whether each of a group of memory pages is currently allocated or not, POPCOUNT will tell you whether it's useful to examine that word in order to attempt to allocate a block of a given size. Since this is a very important operation, I'd say it's worth including in an ISA for this reason only. – Jules Sep 10 '17 at 11:25
  • 1
    @Jules Your guess is wrong. OSs (or rather, system libraries) are rarely written in assembler anyhow today - That went out of style 25 years ago. You wouldn't even be able to benefit from any such assembler instruction in a decently modern OS that's written in C or C++. – tofro Sep 10 '17 at 11:40
  • 5
    @Jules "any bit set" or "no bit set" are interesting checks. Bit count is nothing I commonly needed. If there were a need for such an operator, I'd guess any of the high-level languages would have come up with a concept for a hamming-weight operator during the last 30 years, at least. They haven't (I'm not talking about builtin_popcount here - That's not in the high-level language). Note I'm not saying it's useless - It's just not as important as other instructions. And it's also, at least for low bit count CPUs, extremely easy and fast to implement using a LUT. – tofro Sep 10 '17 at 12:25
5

I would guess the answer is very simple and obvious:

CPU makers don't just implement what they want, what "looks nice in a spec" or "what's easily done". They are driven by the market and implement what programmers need and ask for. In case a certain instruction would make a clear distinction in the market or create a unique selling point for a new CPU, they would certainly have implemented it. There is and has definitely been enough peer pressure in the market to justify.

But apparently it wasn't and they didn't.

  • 1
    What, then, did the programmers need it for in the 60s, then stopped for several decades, and now need again? – Leo B. Sep 10 '17 at 20:13
  • 2
    Cryptography definitely is an area today. The sixties, I don't know-maybe it turned out it wasn't needed at all and thus abandoned – tofro Sep 10 '17 at 20:27
  • 1
    @LeoB.: popcnt is very useful with SIMD. e.g. to count matches, do a packed-compare into a bitmask (e.g. x86 pcmpeqb xmm0, xmm1 / pmovmskb eax, xmm0), and popcnt the bitmask. In a SIMD loop that processes a variable amount of data each iteration, pointer += popcnt(something) is often useful to step through an input or output array. e.g. see my answer on filtering an array into a new array ("left packing") using AVX2 + BMI2 – Peter Cordes Dec 15 '17 at 4:24
5

The closest thing I've found to an article explaining the history of the POPCOUNT instruction is a cryptography forum discussion. That discussion claims that population count was added to machines at the NSA's request for cryptanalysis. See also The NSA Instruction which discusses various systems with POPCOUNT.

The book "Hacker's Delight" claims that "According to computer folklore, the population count function is important to the National Security Agency" (page 96).

Serveral sources state that IBM STRETCH supported population count as a by-product of all logical operations. This is technically true but misleading - STRETCH implemented a population count register (All Ones Count / AOC) that would count the ones resulting from a logical operation. So while it didn't have an explicit population count instruction, it had hardware to compute the population count into a register. (See page 10 of the IBM 7030 manual.)

IBM built HARVEST as an extension of STRETCH for the NSA. This machine added a streaming bit count instruction (SCSI) (see HARVEST system manual page H2.40) among other features.

To answer the original question, there are lots of rumors that POPCOUNT appeared in instruction sets when the NSA wanted it, but unsurprisingly there is no authoritative article on this.

  • That doesn't seem like an answer. The question is, why there was no POPCOUNT instruction in most of the CPUs despite its usefullness, whether NSA wants it or not, and ease of implementation. – Leo B. Jan 5 at 6:41
  • 1
    @LeoB - its usefulness does not seem to be a settled conclusion, and that's presumably why it has not shown up in "most CPUs". All that there seems to exist is the folklore that says that cryptanalysis finds it useful, but no substantiation of that. Anecdotes prove nothing, of course, but in a long programming career generally of a system-software implementation nature, including a fair amount of allocation-tracking bitmappery, I don't recall ever once needing to count bits beyond 'all zero or not all zero'. – another-dave Jan 5 at 13:37
  • @another-dave Many kinds of discrete optimization algorithms may benefit from the POPCOUNT instruction, from chess to electronic design. – Leo B. Jan 5 at 17:05
  • 1
    Just having some potential users of an instruction isn't enough to warrant adding it to a processor. For example, MIPS had the rule that a proposed new instruction had to provide a 1% performance gain over a range of applications or it would be rejected. – Ken Shirriff Jan 5 at 17:43
  • 1
    During the 1980s and 1990s we were aware of the population count and leading-zero count instructions in the Seymour Cray designs - but, within Cray Research, never had confirmation as to WHY they were in the instruction set, and a separate functional unit in the hardware. We assumed NSA but that wasn't something that could be confirmed or denied. – Edward Barnard Mar 27 at 0:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.