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

Question

Обновление: пожалуйста, прочитайте код, речь не идет о подсчете битов в одном целом

Можно ли улучшить производительность следующего кода с помощью некоторого умного ассемблера?

uint bit_counter[64];

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

Count находится в самом внутреннем цикле моего алгоритма.

Обновление: Архитектура: x86-64, Sandy Bridge, поэтому можно использовать SSE4.2, AVX1 и более ранние технологии, но не AVX2 или BMI1 / 2.

bits переменная имеет почти случайные биты (близкие к половине нулей и половине)

Answer 1

Вы можете попробовать сделать это с 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 раза. Мне было бы интересно узнать результат, если вы решите его попробовать.

Answer 2

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

Answer 3

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

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

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

A вертикальный счетчик хранит числа, как следует из названия, вертикально; то есть счетчик 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 раз - количество итераций определяется цепочкой переносов longest .

Answer 4

Посмотрите на Бит Тиддлинг Хаки

• Установлен счетный бит
  • Считать биты наивным способом
  • Количество битов, установленных в справочной таблице
  • Набор подсчитанных битов, путь Брайана Кернигана
  • Подсчет битов, установленных в 12, 24 или 32-битных словах с использованием 64-битных инструкций
  • Счетные биты установлены параллельно
  • Количество установленных битов (ранг) от старшего значащего бита до заданной позиции
  • Выбор позиции бита (из старшего разряда) с заданным количеством (рангом)

Редактировать Что касается «накопления сегмента битовой позиции» (bit_counter[]), я чувствую, что это может быть хорошим вариантом для Valarrays + Masking. Хотя это было бы неплохо - кодирование + тестирование + профилирование. Дайте мне знать, если вы действительно заинтересованы.

В наши дни вы можете очень близко приблизиться к поведению valarray, используя связанные кортежи (TR1, boost или C ++ 11); У меня есть ощущение, что будет проще читать и медленнее компилировать.

Answer 5

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

//   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]

EDIT:

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

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

Answer 6

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

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

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

Answer 7

Если вы посчитаете, как часто каждый клев (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];
           }
        }
     }
   }
}

Answer 8

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

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

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

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

Answer 9

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

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-битное слово.