Are there any articles elucidating the history of the POPCOUNT instruction?

Question

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.

Answer 1

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.

Update: I asked the architect of the SPARC processor about the population count (POPC) instruction. He said that for the original SPARC chip, they didn't consider it at all. After SPARC came out, the NSA tried to convince him to add POPC, but he thought it was a terrible idea for a RISC processor. In particular, he didn't want to take the chance of slowing down the clock for the additional circuitry and considered POPC straightforward to implement with a short instruction sequence. Despite the NSA's efforts, he kept the POPC instruction out of SPARC. However, SPARC v9 had a new architect who gave in to the NSA and added the POPC instruction. He goes into more detail in his oral history for the Computer History Museum here.

Answer 2

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.

Answer 3

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.

It's always a bit hard to find documentation about why things have not been done. But maybe a few points to think about

• Machines with a Popcount were already a minority early on.

• Popcount only makes sense for a narrow class of problems.

• Having a Popcount instruction makes only sense if the problem to be solved already needs the upper end of power available.

• At the absolute upper end, there were always machines having it (Cray).

• Every new class (mini, micro) started out as a most simple implementation, only providing the bare minimum.

• The vast majority of applications (for those) do not need Popcount.

• Minis never really reached the upper end of performance, making such specialized instructions worthwhile.

• It wasn't until the late 1980s that massive parallel microprocessor systems were considered for high performance computing.

• While some, like SPARC, defined it, only their upper end implementations really had it.

• Likewise Intel implemented it for the (~2000) Itanium, dedicated to high end computing, while letting another decade pass before adding it to x86.

• It wasn't until that time (late 2000s) that generic mainstream microprocessor architecture (x86) was really considered viable for high end computing.

• By the 2000s microprocessors were quite mature (read bloated), making the addition of additional instructions quite cheap, thus allowing the inclusion of rarely needed ones as well.

• Even today, the majority of CPUs used (and designed) do live quite well without.

On a more basic, but equally important level:

• Popcount is a fairly simple integer instruction

• Popcount can (on most CPU) easy be synthesised by a few, fast instructions.

• Performance gain is thus rather small

• It's way more efficient to first add instructions with more potential gain

Bottom line: No real need, and easy to implement using basic instructions at the same time

At that point it's also worth to remember, that many things look very different in hindsight.

---

To avoid lengthy arguments about how complicated a Popcount implementation is, let's look at a most primitive 6502 (*1). Here two basic instruction of 7 cycles total are needed per byte whose bits are to be counted.

        CLC
        LDY  FACC
        LDA  PCTAB,Y
        LDY  FACC+1
        ADC  PCTAB,Y
        ...

PCTAB   DB   0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,...

On an 8086, it can easy be done with string instruction handling even lengthy sequences of up to 65535 bit close to full bus speed:

        MOV   AH,0
        MOV   DX,0
CNTLP:
        LODSB
        XLAT  PCTAB
        ADD   DX,AX
        LOOP  

On a /360, the basic counting can be done with a single TR instruction, while 'reuse' of packed decimal instructions and another TR will speed up the adding substantial.

---

*1 - Ofc, only in sense of complex instructions - otherwise it always will be the second best CPU, right after /360, ever.

Answer 4

This paper by Simon Lavington on Manchester University computers says that the Ferranti Mark I, the commercialization of the Manchester Mark I, incorporated a "sideways add" instruction at the request of Manchester mathematicians for "their number-theory problems".