Считайте биты 1 на целое число так же быстро, как GCC __builtin__popcount(int)

Question

Я пишу алгоритм (взят из "языка программирования C"), который очень быстро считает число в 1 бит:

int countBit1Fast(int n)
{
    int c = 0;
    for (; n; ++c)
        n &= n - 1;
    return c;
}

Но друг сказал мне, что __builtin__popcount(int) это намного быстрее, но менее переносимо. Я попробовал и был в разы быстрее! Почему это так быстро? Я хочу считать биты как можно быстрее, но без привязки к конкретному компилятору.

РЕДАКТИРОВАТЬ: я могу использовать его на PIC-микроконтроллерах и, возможно, на процессорах не-Intel, поэтому мне нужна максимальная переносимость.

Answer 1

Я пишу алгоритм (взят из "языка программирования C"), который очень быстро считает число в 1 бит:

Я не понимаю, почему кто-то охарактеризовал бы ваш подход как "очень быстрый". Это немного умно, и это должно быть в среднем быстрее, чем наивные альтернативы. Это также не зависит от ширины представления int, что является плюсом. Я заметил, что он имеет неопределенное поведение для отрицательных аргументов, но это общая тема для побитовых операторов и функций.

Давайте проанализируем, предположив неотрицательный аргумент:

int c = 0;
for (; n; ++c)
    n &= n - 1;

• Сколько итераций цикла выполняется?

  1 для каждого 1 бита в двоичном представлении значения, независимо от того, где в значении находится каждый бит

• Сколько работы выполняется за одну итерацию

  • один шаг c
  • одно сравнение n против нуля (плюс еще один из них при выходе из цикла)
  • один декремент n на 1
  • один поразрядный 'и'

  Это игнорирует операции чтения и сохранения, которые, скорее всего, можно сделать бесплатными или особенно дешевыми, если хранить операнды в регистрах. Если мы возьмем равную стоимость для каждого из них, то это четыре операции за итерацию. Для случайных 32-разрядных целых чисел будет в среднем 16 итераций, что в среднем составит 65 операций. (В лучшем случае это всего лишь одна операция, а в худшем - 129, что не лучше, чем наивная реализация).

__builtin__popcount()с другой стороны, использует одну инструкцию независимо от того, какие данные вводятся на платформах, которые ее поддерживают, как, например, у вас. Однако даже для тех, у кого нет специального назначения, это можно сделать быстрее (в среднем).

@dbush представил один такой механизм, который имеет преимущества, аналогичные тому, который вы представляете. В частности, он не зависит от предварительно выбранной целочисленной ширины, и, хотя он зависит от того, где в представлении находятся 1 биты, он работает быстрее для некоторых аргументов (меньших), чем другие. Если я считаю правильно, то это будет в среднем около 20 операций на случайных 32-битных входах: по пять в каждой из четырех итераций цикла (только 0,4% случайных входов потребуют менее четырех итераций). Я считаю одно чтение таблицы за одну итерацию, которое, как я полагаю, может обслуживаться из кэша, но, вероятно, все еще не так быстро, как арифметическая операция со значениями, уже хранящимися в регистрах.

Тот, который является строго вычислительным, будет:

int countBit1Fast(uint32_t n) {
    n = (n & 0x55555555u) + ((n >> 1) & 0x55555555u);
    n = (n & 0x33333333u) + ((n >> 2) & 0x33333333u);
    n = (n & 0x0f0f0f0fu) + ((n >> 4) & 0x0f0f0f0fu);
    n = (n & 0x00ff00ffu) + ((n >> 8) & 0x00ff00ffu);
    n = (n & 0x0000ffffu) + ((n >>16) & 0x0000ffffu);
    return n;
}

Это довольно легко сосчитать: пять сложений, пять сдвигов и десять побитовых операций 'и' и 5 загрузок констант, что в сумме дает 25 операций для каждого входа (и оно увеличивается до 30 для 64-битных входов, хотя эти теперь 64-битные операции вместо 32-битных). Эта версия, однако, по своей природе зависит от конкретного размера входного типа данных.

Answer 2

Как уже упоминали другие, __buildin__popcount() быстрый, потому что он использует одну инструкцию x86.

Если вы хотите что-то более быстрое, чем то, что у вас есть, которое не использует ничего конкретного процессора или компилятора, вы можете создать таблицу поиска с 256 записями:

int bitcount[] = {
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

Затем используйте это, чтобы получить количество бит каждого байта:

int countBit1Fast(int n) 
{
    int i, count = 0;
    unsigned char *ptr = (unsigned char *)n;
    for (i=0;i<sizeof(int);i++) {
        count += bitcount[ptr[i]];
    }
    return count;
}

Answer 3

__buildin__popcount() это так быстро, потому что это расширение gcc, которое использует встроенную аппаратную инструкцию. Если вы хотите обменять переносимость архитектуры на переносимость компилятора, посмотрите на такие же быстрые встроенные функции Intel, а именно:

_mm_popcnt_u64()

или же

_mm_popcnt_u32()

Затем вы должны включить <mmintrin.h> заголовочный файл, чтобы использовать эти встроенные функции, однако они будут работать с компиляторами не-gcc. Вам также может потребоваться предоставить целевую архитектуру, чтобы функции были встроены (что строго необходимо), используя что-то вроде -march=native,

Answer 4

Как уже упоминалось, на x86_64 у вас есть инструкция процессора popcount, которая полностью превзойдет любую программную реализацию.

При отсутствии инструкции CPU popcount, какой метод будет самым быстрым, зависит от размера слова, скорости поиска (которая может зависеть от поведения кэша CPU) и эффективности суперскалярной конвейерной обработки.

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

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

Этот алгоритм занимает 4×log₂(num_bits))-1 шагов, что означает, что он сравнительно плохо работает для небольших целых чисел, но улучшается для больших:

Первоначально вы начинаете с каждого бита в своем собственном прогоне; затем вы берете пары наборов и складываете их вместе, так что каждый из них представляет собой число от 0 до 2 включительно, что удобно помещается в 2-битное целое число без знака:

      x = (x >> 1 & 0x55555555555555555555555555555555)
   +(x      & 0x55555555555555555555555555555555);

Теперь каждая пара битов содержит число от 0 до 2, указывающее, сколько битов раньше было установлено в этой паре. Последующие шаги довольно просты: объединить соседние прогоны в новые прогоны, ширина которых в два раза больше:

      x = (x >> 2 & 0x33333333333333333333333333333333)
   +(x      & 0x33333333333333333333333333333333);

Теперь каждая серия из 4 битов содержит число от 0 до 4. Поскольку эти числа умещаются в 3 бита, старший бит каждой серии всегда будет равен 0, и его не нужно включать в маску.

      x = (x >> 4 & 0x07070707070707070707070707070707)
   +(x      & 0x07070707070707070707070707070707);

Теперь каждая серия из 8 битов содержит число от 0 до 8. Поскольку эти числа помещаются в 4 бита, верхние 12 бит каждой серии всегда будут равны 0, и их не нужно включать в маску.

      x = (x >> 8 & 0x000f000f000f000f000f000f000f000f)
   +(x      & 0x000f000f000f000f000f000f000f000f);

Теперь каждая серия из 16 битов содержит число от 0 до 16. Поскольку эти числа помещаются в 5 бит, верхние 27 бит каждой серии всегда будут равны 0, и их не нужно включать в маску.

      x = (x >>16 & 0x0000001f0000001f0000001f0000001f)
   +(x      & 0x0000001f0000001f0000001f0000001f);

Теперь каждая серия из 32 битов содержит число от 0 до 32. Поскольку эти числа умещаются в 6 бит, верхние 58 бит каждой серии всегда будут равны 0, и их не нужно включать в маску.

      x = (x >>32 & 0x000000000000003f000000000000003f)
   +(x      & 0x000000000000003f000000000000003f);

Теперь каждая серия из 64 битов содержит число от 0 до 64. Поскольку эти числа умещаются в 7 бит, старший 121 бит каждой серии всегда будет равен 0, и их не нужно включать в маску.

      x = (x >>64 & 0x0000000000000000000000000000007f)
   +(x      & 0x0000000000000000000000000000007f);

В общем, для шага, предварительный расчет

      w0 = 1<<i;      /* number of bits per run for THIS cycle */
w1 = 1<<i+1;    /* number of bits per run for NEXT cycle */
r1 = w1-1;      /* mask for a number from 0 .. w0 inclusive */

/* Create a pattern of bits with a 1 every w1 bits: */
m1 = 1 << w1;
m3 = UINTMAX / (m1 - 1);

m4 = m3 * r1;

shift[i] = w0;
mask[i] = m4;

/* for the variant below */
m0 = 1 << w0;
s_mult[i] = m0 - 1;

а затем для каждого шага используйте:

      x = (x >> shift[i] & mask[i])
   +(x             & mask[i]);

В зависимости от того, насколько быстро ваш ЦП может выполнять умножение, это может лучше использовать конвейерную обработку:

      x -=  x >> 1 & 0x55555555555555555555555555555555;
x -= (x >> 2 & 0x33333333333333333333333333333333) * 3;
x -= (x >> 4 & 0x07070707070707070707070707070707) * 0xf;
x -= (x >> 8 & 0x000f000f000f000f000f000f000f000f) * 0xff;
x -= (x >>16 & 0x0000001f0000001f0000001f0000001f) * 0xffff;
x -= (x >>32 & 0x000000000000003f000000000000003f) * 0xffffffff;
x -= (x >>64 & 0x0000000000000000000000000000007f) * 0xffffffffffffffff;

y -= (x >> shift[i] & mask[i]) * s_mult[i];