Hacker News Reader

Comment by adrian_b | Hacker News Reader

> 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”.

View on HN

Indeed, 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):

> 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.

And in 1955 you had Arithmetic Operations in Digital Computers. https://archive.org/details/arithmetic_operations_in_digital...

In case you are curious, here is the algorithm from that 1957 text book (2nd edition): 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

> this instruction was named "sideways add"

An early instance of what's now more commonly called a "horizontal" operation in the context of SIMD.

which 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.

There 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.

With 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);
  }

> at the request of Alan Turing

Well, I can imagine there might actually have been a connection to cryptography then. Not NSA related though.

Reply on news.ycombinator.com