Как быстро посчитать биты в отдельные бины в ряду целых чисел на Sandy Bridge?

Может быть, вы можете сделать 8 сразу, взяв 8 бит, разнесенных на 8, и сохранив 8 uint64 для подсчета. Это всего лишь 1 байт на один счетчик, поэтому вы можете накопить только 255 вызовов count, прежде чем вам придется распаковывать эти uint64.

Вы можете попробовать сделать это с SSE, увеличивая 4 элемента за итерацию.

Предупреждение: за непроверенным кодом следует...

#include <stdint.h>
#include <emmintrin.h>

uint32_t bit_counter[64] __attribute__ ((aligned(16)));
                     // make sure bit_counter array is 16 byte aligned for SSE

void Count_SSE(uint64 bits)
{
    const __m128i inc_table[16] = {
        _mm_set_epi32(0, 0, 0, 0),
        _mm_set_epi32(0, 0, 0, 1),
        _mm_set_epi32(0, 0, 1, 0),
        _mm_set_epi32(0, 0, 1, 1),
        _mm_set_epi32(0, 1, 0, 0),
        _mm_set_epi32(0, 1, 0, 1),
        _mm_set_epi32(0, 1, 1, 0),
        _mm_set_epi32(0, 1, 1, 1),
        _mm_set_epi32(1, 0, 0, 0),
        _mm_set_epi32(1, 0, 0, 1),
        _mm_set_epi32(1, 0, 1, 0),
        _mm_set_epi32(1, 0, 1, 1),
        _mm_set_epi32(1, 1, 0, 0),
        _mm_set_epi32(1, 1, 0, 1),
        _mm_set_epi32(1, 1, 1, 0),
        _mm_set_epi32(1, 1, 1, 1)
    };

    for (int i = 0; i < 64; i += 4)
    {
        __m128i vbit_counter = _mm_load_si128(&bit_counter[i]);
                                          // load 4 ints from bit_counter
        int index = (bits >> i) & 15;     // get next 4 bits
        __m128i vinc = inc_table[index];  // look up 4 increments from LUT
        vbit_counter = _mm_add_epi32(vbit_counter, vinc);
                                          // increment 4 elements of bit_counter
        _mm_store_si128(&bit_counter[i], vbit_counter);
    }                                     // store 4 updated ints
}

Как это работает: по сути, все, что мы здесь делаем, это векторизация исходного цикла, так что мы обрабатываем 4 бита на итерацию цикла вместо 1. Таким образом, теперь у нас есть 16 итераций цикла вместо 64. Для каждой итерации мы загружаем 4 бита из bits, затем использовать их в качестве индекса в LUT, который содержит все возможные комбинации 4 приращений для текущих 4 бит. Затем мы добавляем эти 4 приращения к текущим 4 элементам bit_counter.

Количество загрузок, хранилищ и добавлений уменьшено в 4 раза, но это будет несколько компенсировано загрузкой LUT и прочими служебными операциями. Тем не менее, вы все еще можете увидеть 2-кратное ускорение. Мне было бы интересно узнать результат, если вы решите попробовать.

Ознакомьтесь с лайфхаками.

• Counting bits set
  • Counting bits set, naive way
  • Биты подсчета, установленные таблицей поиска
  • Набор битов счета, способ Брайана Кернигана
  • Подсчет битов, установленных в 12-, 24- или 32-битных словах, с использованием 64-битных инструкций
  • Параллельный набор битов подсчета
  • Подсчитывать набор битов (ранг) от самого старшего бита до заданной позиции
  • Выберите позицию бита (от самого старшего бита) с заданным количеством (рангом)< /а>

Видимо это можно сделать быстро с "вертикальными счетчиками". С ныне несуществующей страницы о битовых трюках (архив) от @steike:

Рассмотрим обычный массив целых чисел, где мы читаем биты по горизонтали:

       msb<-->lsb
  x[0]  00000010  = 2
  x[1]  00000001  = 1
  x[2]  00000101  = 5

Вертикальный счетчик хранит числа, как следует из названия, вертикально; то есть k-битный счетчик хранится в k словах, по одному биту в каждом слове.

  x[0]  00000110   lsb ↑
  x[1]  00000001       |
  x[2]  00000100       |
  x[3]  00000000       |
  x[4]  00000000   msb ↓
             512

С числами, хранящимися таким образом, мы можем использовать побитовые операции для одновременного увеличения любого их подмножества.

Мы создаем битовую карту с 1 битом в позициях, соответствующих счетчикам, которые мы хотим увеличить, и проходим по массиву, начиная с LSB, обновляя биты по мере продвижения. «Переносы» из одного сложения становятся входными данными для следующего элемента массива.

  input  sum

--------------------------------------------------------------------------------
   A B   C S
   0 0   0 0
   0 1   0 1      sum    = a ^ b
   1 0   0 1      carry  = a & b
   1 1   1 1

  carry = input;
  long *p = buffer;
  while (carry) {
    a = *p; b = carry;
    *p++ = a ^ b;
    carry = a & b;
  }

Для 64-битных слов цикл будет выполняться в среднем 6-7 раз — количество итераций определяется самой длинной цепочкой переносов.

Вы можете развернуть свою функцию следующим образом. Это, вероятно, быстрее, чем то, что может сделать ваш компилятор!

//   rax as 64 bit input
   xor  rcx, rcx                //clear addent

   add  rax, rax                //Copy 63th bit to carry flag
   adc  dword ptr [@bit_counter + 63 * 4], ecx    //Add carry bit to counter[64]

   add  rax, rax                //Copy 62th bit to carry flag
   adc  dword ptr [@bit_counter + 62 * 4], ecx    //Add carry bit to counter[63]

   add  rax, rax                //Copy 62th bit to carry flag
   adc  dword ptr [@bit_counter + 61 * 4], ecx    //Add carry bit to counter[62]
//   ...
   add  rax, rax                //Copy 1th bit to carry flag
   adc  dword ptr [@bit_counter + 1 * 4], ecx     //Add carry bit to counter[1]

   add  rax, rax                //Copy 0th bit to carry flag
   adc  dword ptr [@bit_counter], ecx             //Add carry bit to counter[0]

ИЗМЕНИТЬ:

Вы также можете попробовать с двойным приращением:

//   rax as 64 bit input
   xor  rcx, rcx                //clear addent
//
   add  rax, rax                //Copy 63th bit to carry flag
   rcl  rcx, 33                 //Mov carry to 32th bit as 0bit of second uint
   add  rax, rax                //Copy 62th bit to carry flag
   adc  qword ptr [@bit_counter + 62 * 8], rcx  //Add rcx to 63th and 62th counters

   add  rax, rax                //Copy 61th bit to carry flag
   rcl  rcx, 33                 //Mov carry to 32th bit as 0bit of second uint
   add  rax, rax                //Copy 60th bit to carry flag
   adc  qword ptr [@bit_counter + 60 * 8], rcx  //Add rcx to 61th and 60th counters
//...

Вы можете использовать набор счетчиков, каждый разного размера. Сначала накапливаем 3 значения в 2-битных счетчиках, затем распаковываем их и обновляем 4-битные счетчики. Когда 15 значений будут готовы, распакуйте их в счетчики размером в байт, а после 255 значений обновите bit_counter[].

Вся эта работа может выполняться параллельно в 128-битных регистрах SSE. На современных процессорах требуется только одна инструкция, чтобы распаковать 1 бит в 2. Просто умножьте исходное четверное слово на себя с помощью инструкции PCLMULQDQ. Это будет чередовать исходные биты с нулями. Тот же прием может помочь распаковать 2 бита в 4. А распаковать 4 и 8 бит можно с помощью тасовки, распаковки и простых логических операций.

Средняя производительность вроде неплохая, но цена 120 байт за дополнительные счетчики и довольно много ассемблерного кода.

Нет никакого способа ответить на это в целом; все зависит от компилятора и базовой архитектуры. Единственный реальный способ узнать это — попробовать разные решения и измерить. (На некоторых машинах, например, смены могут быть очень дорогими. На других нет.) Для начала я бы использовал что-то вроде:

uint64_t mask = 1;
int index = 0;
while ( mask != 0 ) {
    if ( (bits & mask) != 0 ) {
        ++ bit_counter[index];
    }
    ++ index;
    mask <<= 1;
}

Полное развертывание цикла, скорее всего, улучшит производительность. В зависимости от архитектуры замена if на:

bit_counter[index] += ((bits & mask) != 0);

может быть лучше. Или того хуже... это невозможно знать заранее. Также возможно, что на некоторых машинах систематический переход к младшему разряду и маскировка, как вы делаете, были бы лучшими.

Некоторые оптимизации также будут зависеть от того, как выглядят типичные данные. Если в большинстве слов установлены только один или два бита, вы можете выиграть, проверяя байт за раз или четыре бита за раз и полностью пропуская те, которые полностью равны нулю.

Если вы подсчитаете, как часто каждый откусывает (16 возможностей) при каждом смещении (16 возможностей), вы можете легко суммировать результаты. И эти 256 сумм легко сохраняются:

unsigned long nibble_count[16][16]; // E.g. 0x000700B0 corresponds to [4][7] and [2][B]
unsigned long bitcount[64];

void CountNibbles(uint64 bits) {
  // Count nibbles
  for (int i = 0; i != 16; ++i) {
     nibble_count[i][bits&0xf]++;
     bits >>= 4;
  }
}
void SumNibbles() {
  for (int i = 0; i != 16; ++i) {
    for (int nibble = 0; nibble != 16; ++nibble) {
        for(int bitpos = 0; bitpos != 3; ++bitpos) {
           if (nibble & (1<<bitpos)) {
              bitcount[i*4 + bitpos] += nibble_count[i][nibble];
           }
        }
     }
   }
}

Это довольно быстро:

void count(uint_fast64_t bits){
    uint_fast64_t i64=ffs64(bits);
    while(i64){
        bit_counter[i64-1]++;
        bits=bits & 0xFFFFFFFFFFFFFFFF << i64;
        i64=ffs64(bits);
    }
}

Вам нужна быстрая реализация ffs для 64-битной версии. Для большинства компиляторов и процессоров это одна инструкция. Цикл выполняется один раз для каждого бита в слове, поэтому bits=0 будет очень быстрым, а 64-битные биты 1 будут медленнее.

Я протестировал это под 64-битной Ubuntu с GCC, и он выводит те же данные, что и ваши:

void Count(uint64 bits) {
  bit_counter[0] += (bits >> 0) & 1;
  bit_counter[1] += (bits >> 1) & 1;
  // ..
  bit_counter[63] += (bits >> 63) & 1;
}

Скорость зависит от количества 1 битов в 64-битном слове.