Как быстро посчитать биты в отдельные бункеры в серии целых чисел на Sandy Bridge?
Обновление: пожалуйста, прочитайте код, это НЕ о подсчете битов в одном
Можно ли улучшить производительность следующего кода с помощью какого-нибудь умного ассемблера?
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 переменная имеет почти случайные биты (близкие к половине нулей и половинным)
9 ответов
Может быть, вы можете сделать 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 раза. Мне было бы интересно узнать результат, если вы решите попробовать.
Посмотрите на Бит Тиддлинг Хаки
- Подсчет битов установлен
- Подсчет бит установлен, наивный способ
- Подсчет битов, установленных таблицей поиска
- Подсчет бит установлен, путь Брайана Кернигана
- Подсчет битов, установленных в 12, 24 или 32-битных словах с использованием 64-битных инструкций
- Подсчет бит установлен параллельно
- Количество установленных битов (ранг) от старшего значащего бита до заданной позиции
- Выберите позицию бита (из самого старшего бита) с заданным количеством (рангом)
Изменить как для "накопления сегмента битовой позиции" (bit_counter[]) У меня такое чувство, что это может быть хорошим аргументом для маскировки + valarrays. Хотя это было бы неплохо - кодирование + тестирование + профилирование. Дайте мне знать, если вы действительно заинтересованы.
В эти дни вы могли бы очень близко приблизиться к поведению valarray, используя привязанные кортежи (TR1, boost или C++11); У меня есть ощущение, что будет проще читать и медленнее компилировать.
По-видимому, это можно сделать быстро с помощью "вертикальных счетчиков". Со страницы ныне несуществующей страницы "Битовые уловки" ( архив) от @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-битном слове.