Как используется странная инструкция popcount в современных процессорах

Писался на перерыве на коленке, так что не придираться.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>

#define ARR_SIZE (200 * 1000 * 1000)
#define LOOKUP_TABLE_SIZE 256
#define CLOCKS_PER_MS (CLOCKS_PER_SEC / 1000)

static uint8_t _bits_lookup_table[LOOKUP_TABLE_SIZE];

void initLookupTable() {
    _bits_lookup_table[0] = 0;
    for (int i = 1; i < LOOKUP_TABLE_SIZE; i++) {
    _bits_lookup_table[i] = _bits_lookup_table[i / 2] + (i & 1);
    }
}

uint32_t countBitsLookup(uint32_t *arr, uint32_t size) {
    uint32_t counter = 0;
    for (uint32_t i = 0; i < size; i++) {
        uint8_t *bytearr = (uint8_t*)(arr++);

        counter += _bits_lookup_table[*bytearr++];
        counter += _bits_lookup_table[*bytearr++];
        counter += _bits_lookup_table[*bytearr++];
        counter += _bits_lookup_table[*bytearr];
    }
    return counter;
}

uint32_t countBitsNatural(uint32_t *arr, uint32_t size) {
    uint32_t counter = 0;
    for (uint32_t i = 0; i < size; i++) {
    for (uint32_t val = arr[i]; val > 0; val &= val - 1) {
        counter++;
    }
    }
    return counter;
}

uint32_t countBitsMagic(uint32_t *arr, uint32_t size) {
    uint32_t counter = 0;
    for (uint32_t i = 0; i < size; i++) {
    uint32_t val = arr[i];
        val = val - ((val >> 1) & 0x55555555);                      // reuse input as temporary
        val = (val & 0x33333333) + ((val >> 2) & 0x33333333);       // temp
        counter += ((val + (val >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;// count
    }
    return counter;
}

uint32_t *randomArray(uint32_t size) {
    uint32_t *arr = (uint32_t*) malloc(size * sizeof(uint32_t));
    for (uint32_t i = 0; i < size; i++) {
    arr[i] = rand();
    }
    return arr;
}

int main(void) {
    srand(clock());
    initLookupTable();
    uint32_t *array = randomArray(ARR_SIZE);

    clock_t ts = clock();

    uint64_t bits_1 = countBitsNatural(array, ARR_SIZE);
    ts = clock() - ts;
    printf("Number of bits (natural): %zu in %zu ms\n", bits_1, ts / CLOCKS_PER_MS);

    ts = clock();
    uint64_t bits_2 = countBitsLookup(array, ARR_SIZE);
    ts = clock() - ts;
    printf("Number of bits (lookup) : %zu in %zu ms\n", bits_2, ts / CLOCKS_PER_MS);

    ts = clock();
    uint64_t bits_3 = countBitsMagic(array, ARR_SIZE);
    ts = clock() - ts;
    printf("Number of bits (magic)  : %zu in %zu ms\n", bits_3, ts / CLOCKS_PER_MS);
}

Видно как раз мощную векторизацию в случае подсчёта формулой из битхаков.

  401440:       c5 f9 72 d1 01          vpsrld $0x1,%xmm1,%xmm0
  401445:       c5 f9 db c5             vpand  %xmm5,%xmm0,%xmm0
  401449:       c5 f1 fa c8             vpsubd %xmm0,%xmm1,%xmm1
  40144d:       c5 f9 72 d1 02          vpsrld $0x2,%xmm1,%xmm0
  401452:       c5 f1 db cb             vpand  %xmm3,%xmm1,%xmm1
  401456:       c5 f9 db c3             vpand  %xmm3,%xmm0,%xmm0
  40145a:       c5 f9 fe c1             vpaddd %xmm1,%xmm0,%xmm0
  40145e:       c5 f1 72 d0 04          vpsrld $0x4,%xmm0,%xmm1
  401463:       c5 f1 fe c8             vpaddd %xmm0,%xmm1,%xmm1
  401467:       c5 f1 db cc             vpand  %xmm4,%xmm1,%xmm1
  40146b:       c5 f9 72 f1 08          vpslld $0x8,%xmm1,%xmm0
  401470:       c5 f9 fe c1             vpaddd %xmm1,%xmm0,%xmm0
  401474:       c5 f1 72 f0 10          vpslld $0x10,%xmm0,%xmm1
  401479:       c5 f9 fe c1             vpaddd %xmm1,%xmm0,%xmm0
  40147d:       c5 f9 72 d0 18          vpsrld $0x18,%xmm0,%xmm0
  401482:       c5 e9 fe d0             vpaddd %xmm0,%xmm2,%xmm2

А это как компилятор оптимизировал подсчёт бит в цикле:

00000000004013b0 <countBitsNatural>:
  4013b0:       85 f6                   test   %esi,%esi
  4013b2:       74 2a                   je     4013de <countBitsNatural+0x2e>
  4013b4:       8d 46 ff                lea    -0x1(%rsi),%eax
  4013b7:       45 31 c0                xor    %r8d,%r8d
  4013ba:       48 8d 4c 87 04          lea    0x4(%rdi,%rax,4),%rcx
  4013bf:       90                      nop
  4013c0:       8b 17                   mov    (%rdi),%edx
  4013c2:       31 c0                   xor    %eax,%eax
  4013c4:       f3 0f b8 c2             popcnt %edx,%eax
  4013c8:       44 01 c0                add    %r8d,%eax
  4013cb:       85 d2                   test   %edx,%edx
  4013cd:       44 0f 45 c0             cmovne %eax,%r8d
  4013d1:       48 83 c7 04             add    $0x4,%rdi
  4013d5:       48 39 f9                cmp    %rdi,%rcx
  4013d8:       75 e6                   jne    4013c0 <countBitsNatural+0x10>
  4013da:       44 89 c0                mov    %r8d,%eax
  4013dd:       c3                      retq
  4013de:       45 31 c0                xor    %r8d,%r8d
  4013e1:       44 89 c0                mov    %r8d,%eax
  4013e4:       c3                      retq
  4013e5:       66 66 2e 0f 1f 84 00    data16 nopw %cs:0x0(%rax,%rax,1)
  4013ec:       00 00 00 00