Comments 22
В общем-то, чем больше машинных инструкций имеет вычислительное устройство, тем лучше пользователю этого устройства.
Однако редкий реальный продукт (даже числомолотилка) будет действительно интенсивно использовать popcnt.
По сути, хороший алгоритм позволяет заменить эту инструкцию очень небольшим количеством базовых инструкций.
Выигрыш в несколько тактов при подсчёте единиц — хорошо. Если на 10 инструкций приходится один вызов popcnt, то его замена базовыми инструкциями снизит производительность очень значительно.
А вот если один popcnt на 100 инструкций — то уже всего 10%.
И требовать наличия особенной инструкции, особенно когда у тебя в коде подсчёт выполняется два с половиной раза, не очень-то разумно.
В одном случае (вторая из ссылок выше) людям поломали драйвер.
Другой пример — в Quantum Break было требование по наличию popcnt, и Remedy с честными глазами заявляли «Нет, нам это действительно нужно для рендера. Не перекомпилим». А по факту замена двух байт в библиотеке рендера на NOPы делало игру полностью работоспособной без popcnt. И притом с хорошей производительностью.
Поэтому выигрывая несколько тактов на редких инструкциях, не стоит забывать о совместимости.
ЗЫ
В gcc не правильная реализация этой функции, т.е. интринстика, надо чтобы было dword ...(dword) а не byte ...(dword), из-за этого компилятор вставляет совершенно лишнею команду преобразования movzx.
S : set of 1..8;
занимало байт и значениеS :=[1,8];
представлялось единичным младшим и старшим битами, остальные нули. С помощью popcount легко и быстро посчитать мощность такого множества.С использованием как раз все понятно, но почему она называется не bitcount, например?
Видимо потому что считает не сами биты а только количество единиц в данном массиве бит (те что pops out?). Интерпретации названия в документации к команде не припомню. Также беглый гуглеж выдал что-то про population count, что тоже может быть притянуто.
Кстати, в Java она как раз таки называется bitCount.
Мы как-то сравнивали разные подходы в разрезе типовой задачи на собеседовании "посчитать количество бит". Сильно отличается от процессора к процессору, на x64 интелах лучше всех векторизовался вот этот подход, но я не уверен что он будет быстрее современных же popcnt. Ссылку на все битхаки уже приводили ниже.
v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
А кстати да, я нашёл свой тестовый код. Компилятор достаточно умный чтобы свернуть натуральный подсчёт битов в popcnt. Результаты с AVX (magic) действительно быстрее:
Собирается через
$ gcc -O3 -mavx bitcount.c
Number of bits (natural): 3100008771 in 160 ms
Number of bits (lookup) : 3100008771 in 297 ms
Number of bits (magic) : 3100008771 in 134 ms
Пробуйте добавлять свои эксперименты, узнаем кто самый быстрый :) Кстати на АРМ ситуация в корне другая, так как нет AVX.
Писался на перерыве на коленке, так что не придираться.
#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
первая строка:
(посмотрите на пары бит: 0b00 — это 0, 0b01 — 1 бит, 0b10 — 1 бит, 0b11 — это 2 бита) или если переводить в двоичные числа 0b00->0b00, 0b01->0b01, 0b10->0b01, 0b11->0b10. 0x5 в битах — это 0b0101, так что после первой строки у вас уже не биты числа — а массив сумм пар бит;
вторая строка:
v & 0b0011......0011 + (v & 1100...1100) >> 2
т.е. суммируем пары бит между собой, и теперь у нас массив сумм бит по четыре бита;
третья строка:
сначала v + ( v & 0b11110000....1111000 ) >> 4 — получаем из массива бит по 4бита, массив по сумм по 8 бит (обозначим его как s), а потом умножение на 0x1010101 — это на самом деле сумма умножений
s* 0x01000000 + s * 0x00010000 +… + s* 0x00000001 или если учитывать, что при переполнении старшие биты отбрасываются — это будет эквивалентно сумме сдвигов
s << 24 + s << 16 + s << 8 + s — так что в старшем байте будет сумма их всех, и сдвигом вправо на 24 вы получаете ответ.
cnt=0;
while (x>0) {
x = (x-1) & x;
cnt++;
}
- простая github.com/AlexeyAB/darknet/blob/1c71f001531a5df0637903117c6568725d7a66b3/src/gemm.c#L2100-L2131
- немного оптимизированная с AVX2: github.com/AlexeyAB/darknet/blob/1c71f001531a5df0637903117c6568725d7a66b3/src/gemm.c#L1202-L1317
На Low-power devices работает до 30 раз быстрее, чем с Float-32-bit.
Высокая точность достигается с применением обучения с online-SVR.
Перемножение бинарных матриц на GPU используя Tensor Cores и без них с popcount: https://github.com/AlexeyAB/darknet/blob/53160fa6662ea7e8c4095588db56cac7b339b917/src/im2col_kernels.cu#L1225-L1419
Конкретно в этой строке popcount: https://github.com/AlexeyAB/darknet/blob/53160fa6662ea7e8c4095588db56cac7b339b917/src/im2col_kernels.cu#L1358
Как используется странная инструкция popcount в современных процессорах