Каков эффективный способ подсчета бит в позиции или ниже?

Ответ 1

Этот С++ получает g++, чтобы испускать очень хороший x86 ASM (учебник компилятора godbolt). Я ожидаю, что он будет эффективно компилироваться и на других 64-битных архитектурах (если для использования std::bitset::count используется HW popcount, в противном случае это будет медленная часть):

#include <bitset>

int popcount_subset(std::bitset<64> A, int pos) {
  int high_bits_to_eliminate = 63 - pos;
  A <<= (high_bits_to_eliminate & 63);  // puts A[pos] at A[63].

  return (A[63]? ~0ULL : 0) & A.count();  // most efficient way: great code with gcc and clang
  // see the godbolt link for some #ifdefs with other ways to do the check, like
    // return A[BSET_SIZE-1] ? A.count() : 0;
}

Это, вероятно, не оптимально на 32-битных архитектурах, поэтому сравните другие альтернативы, если вам нужно создать 32-битную сборку.

Это будет работать для других размеров битов, если вы что-то делаете с жестко закодированным 63 s и изменяете маску & 63 для счетчика сдвига в более общий диапазон-чек. Для оптимальной работы с битрейтами странного размера создайте функцию шаблона со специализацией для size <= register width целевой машины. В этом случае извлеките биттет в тип unsigned соответствующей ширины и переместитесь в верхнюю часть регистра вместо вершины битового набора.

Вы ожидаете, что это также приведет к созданию идеального кода для bitset<32>, но это не совсем так. gcc/clang все еще используют 64-битные регистры на x86-64.

Для больших битов, перемещение всего объекта будет медленнее, чем просто заполнение слов ниже того, которое содержит pos, и используя это на этом слове. (Это означает, что векторизованный popcount действительно сияет на x86, если вы можете предполагать SSSE3, но не аппаратную поддержку popcnt insn, или для 32-битных целей. AVX2 256bit pshufb - это самый быстрый способ делать массовые popcounts, но без AVX2 я думаю 64bit popcnt довольно близок к 128-битной реализации pshufb. См. Комментарии для большего обсуждения.)

Если у вас есть массив из 64-битных элементов и вы хотите считать бит ниже определенной позиции в каждом отдельно, то вам определенно следует использовать SIMD. Части сдвига этого алгоритма векторизовать, а не только часть popcnt. Используйте psadbw против регистра с нулевым нулем в байты с горизонтальной суммой в 64-битных фрагментах после pshufb -объекта, который производит подсчет бит в каждом байте отдельно. SSE/AVX не имеет 64-битного арифметического сдвига вправо, но вы можете использовать другой метод для смешивания на высоком бите каждого элемента.

Как я придумал это:

Инструкции asm, которые вы хотите получить для вывода компилятора, будут:

• удалить ненужные биты из 64-битного значения
• проверьте самый высокий из запрошенных битов.
• введите его.
• возвращает 0 или popcount, в зависимости от результата теста. (У ветвящихся или ветвящихся реализаций есть преимущества. Если ветвь предсказуема, ветвящаяся реализация имеет тенденцию быть медленнее.)

Очевидным способом сделать 1 является создание маски ((1<<(pos+1)) -1) и &. Более эффективным способом является сдвиг влево на 63-pos, оставляя бит, который вы хотите упаковать в верхней части регистра.

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

Выполнение popcount - это много обсуждаемая проблема, но на самом деле это более сложная часть головоломки. На x86 для этого есть чрезвычайно эффективная аппаратная поддержка, но только на достаточно недавнем оборудовании. На процессорах Intel инструкция popcnt доступна только в Nehalem и новее. Я забыл, когда AMD добавила поддержку.

Чтобы использовать его безопасно, вам нужно либо выполнить диспетчеризацию процессора с резервным, что не использует popcnt. Или создайте отдельные исполняемые файлы, которые не зависят от некоторых функций ЦП.

popcount без инструкции popcnt может быть выполнен несколькими способами. Один использует SSSE3 pshufb для реализации 4-битного LUT. Это наиболее эффективно при использовании в целом массиве, а не в одном 64b за раз. Скалярные битаки могут быть лучше всего здесь и не потребуют SSSE3 (и поэтому будут совместимы с древними процессорами AMD, которые имеют 64-битный, но не pshufb.)

Bitbroadcast:

(A[63]? ~0ULL : 0) просит компилятор транслировать бит с высоким битом во все остальные позиции битов, что позволяет использовать его как маску AND для нуля (или нет) результата popcount. Обратите внимание, что даже для больших размеров битов он все еще маскирует вывод popcnt, а не самого битового набора, поэтому ~0ULL в порядке. Я использовал ULL, чтобы убедиться, что он никогда не просил компилятор транслировать бит только на низкий 32b регистра (с UL в Windows, например).

Эта трансляция может быть выполнена с арифметическим сдвигом вправо на 63, который сдвигает копии большого бита.

clang сгенерировал этот код из исходной версии. После некоторого подталкивания Гленна к различным реализациям для 4, я понял, что могу привести gcc к оптимальному решению clang, написав источник больше как ASM, который я хочу. Очевидный ((int64_t)something) >> 63 для более прямого запроса арифметического сдвига вправо не будет строго переносимым, потому что подписанные правые сдвиги реализованы как арифметические или логические. В стандарте не предусмотрен какой-либо переносной арифметический оператор сдвига вправо. (Это не undefined поведение.) В любом случае, к счастью, компиляторы достаточно умен: gcc видит лучший способ, как только вы дадите ему достаточно подсказка.

Этот источник делает отличный код на x86-64 и ARM64 с gcc и clang. Оба просто используют арифметический сдвиг вправо на входе в popcnt (поэтому сдвиг может выполняться параллельно с popcnt). Он также отлично компилируется на 32-битной x86 с gcc, потому что маскирование происходит только с 32-битной переменной (после добавления нескольких popcnt-результатов). Это остальная часть функции, которая отвратительна на 32-битной (когда битсет больше регистра).

Оригинальная версия тернарного оператора с gcc

Скомпилирован с gcc 5.3.0 -O3 -march=nehalem -mtune=haswell (более старый gcc, например 4.9.2, также все еще испускает это):

; the original ternary-operator version.  See below for the optimal version we can coax gcc into emitting.
popcount_subset(std::bitset<64ul>, int):
    ; input bitset in rdi, input count in esi (SysV ABI)
    mov     ecx, esi    ; x86 variable-count shift requires the count in cl
    xor     edx, edx    ; edx=0 
    xor     eax, eax    ; gcc workaround for popcnt false dependency on the old value of dest, on Intel
    not     ecx         ; two complement bithack for 63-pos (in the low bits of the register)
    sal     rdi, cl     ; rdi << ((63-pos) & 63);  same insn as shl (arithmetic == logical left shift)
    popcnt  rdx, rdi
    test    rdi, rdi    ; sets SF if the high bit is set.
    cmovs   rax, rdx    ; conditional-move on the sign flag
    ret

См. Как доказать, что оператор C -x, ~ x + 1 и ~ (x-1) дают те же результаты? для фона по использованию gcc из -x == ~x + 1 двухдополнительных тождеств. (И Какие 2 целых операции дополнения можно использовать без обнуления высоких бит на входах, если требуется только небольшая часть результата?, которая тангенциально упоминает, что shl маскирует счетчик сдвига, поэтому нам нужно только 6 бит ecx удерживать 63 - pos. В основном связывая это, потому что я написал его недавно, и любой, кто все еще читает этот абзац, может показаться ему интересным.)

Некоторые из этих инструкций исчезнут при вставке. (например, gcc будет генерировать счетчик в ecx в первую очередь.)

С использованием метода Гленна вместо идеи тройного оператора (включенной USE_mul), gcc делает

    shr     rdi, 63
    imul    eax, edi

в конце вместо xor/test/cmovs.

Haswell перфорированный анализ, используя данные микроархива из Agner Fog (версия Multiply):

• mov r,r: 1 спящий домен uop, 0 латентность, без исполнительного блока
• xor -zeroing: 1 спящий домен uop, без исполнительного устройства
• not: 1 uop для p0/p1/p5/p6, 1c латентность, 1 на производительность 0,25c
• shl (aka sal) со счетом в cl: 3 uops для p0/p6: 2c latency, 1 на 2c пропускную способность. (Данные Agner Fog указывают на то, что IvyBridge занимает всего два раза для этого, как ни странно.)
• popcnt: 1 uop для задержки p1, 3c, 1 на пропускную способность 1 c.
• shr r,imm: 1 uop для p0/p6, 1c латентность. 1 на производительность 0,5 c.
• imul r,r: 1uop для задержки p1, 3c.
• не считая ret

Итоговые:

• 9 fops-domain uops, может выдавать в 2.25 циклах (теоретически, эффекты кеш-линии uop обычно слабо выделяют внешний интерфейс).
• 4 uops (shifts) для p0/p6. 2 uops для p1. 1 any-ALU-port uop. Может выполняться по одному на 2 с (насыщая порты сдвига), поэтому внешний интерфейс является наихудшим узким местом.

Задержка: критический путь с момента готовности битового набора, когда результат: shl (2) → popcnt (3) → imul (3). Всего 8 циклов. Или 9c, когда pos готов, потому что not является дополнительной задержкой в ​​1 секунду для него.

Оптимальная bitbroadcast версия заменяет shr на sar (тот же самый perf), и imul с and (задержка 1c вместо 3c работает на любом порту). Таким образом, единственное первичное изменение уменьшает задержку критического пути до 6 циклов. Пропускная способность по-прежнему является узким местом на интерфейсе. and возможность работать на любом порту не имеет значения, если вы не смешиваете это с кодом, который является узким местом на порту1 (вместо того, чтобы смотреть на пропускную способность для запуска именно этого кода в узком цикле).

версия cmov (тройной оператор): 11 hop-domain uops (интерфейс: один на 2.75c). исполнительные устройства: все еще узкие места на портах сдвига (p0/p6) на один на 2c. Задержка: 7c от битового набора до результата, 8c из pos в результат. (cmov - 2c латентность, 2 uops для любого из p0/p1/p5/p6.)

Clang имеет несколько разных трюков: "Вместо test/cmovs он генерирует маску либо all-ones, либо all-zeros, используя арифметический сдвиг вправо передают бит знака ко всем позициям регистра. Мне это нравится: использование and вместо cmov более эффективно для Intel. Тем не менее, он по-прежнему имеет зависимость от данных и работает для обеих сторон ветки (что является главным недостатком для cmov в целом). Обновление: с правильным исходным кодом gcc также будет использовать этот метод.

clang 3.7 -O3 -Wall -march=nehalem -mtune=haswell

popcount_subset(std::bitset<64ul>, int):
    mov     ecx, 63
    sub     ecx, esi      ; larger code size, but faster on CPUs without mov-elimination
    shl     rdi, cl       ; rdi << ((63-pos) & 63)
    popcnt  rax, rdi      ; doesn't start a fresh dep chain before this, like gcc does
    sar     rdi, 63       ; broadcast the sign bit
    and     eax, edi      ; eax = 0 or its previous value
    ret

sar / and заменяет xor / test / cmov, а cmov является инструкцией 2-uop для процессоров Intel, так что это действительно хорошо. (Для версии с тернарным оператором).

Кланг по-прежнему использует трюк sar / and вместо фактического imul при использовании версии с несколькими источниками или исходной версией "битбизнес". Таким образом, они помогают gcc, не причиняя вреда clang. (sar/and определенно лучше, чем shr/imul: 2c меньше латентности на критическом пути.) Версия pow_of_two_sub повредит clang (см. первую ссылку godbolt: пропущено из этого ответа, чтобы избежать беспорядка с идеями, которые не качались выход).

mov ecx, 63/sub ecx, esi на самом деле быстрее работает на процессорах без исключения mov для reg, reg move (нулевая латентность и отсутствие порта выполнения, обрабатываемого переименованием регистров). Это включает Intel pre-IvyBridge, но не последние процессоры Intel и AMD.

Метод Clang mov imm/sub помещает только один цикл задержки для pos на критический путь (за пределами задержки на биттете → ) вместо двух для a mov ecx, esi/not ecx на процессорах где mov r,r имеет 1 c задержку.

С BMI2 (Хасуэлл и позже) оптимальная версия ASM может сохранить mov до ecx. Все остальное работает одинаково, потому что shlx маскирует свой входной регистр сдвига числа до размера операнда, как и shl.

Инструкции по сдвигу x86 имеют сумасшедшую семантику CISC, где, если количество сдвигов равно нулю, флаги не затрагиваются. Таким образом, команды shift-count shift имеют (потенциальную) зависимость от старого значения флагов. "Обычный" x86 shl r, cl декодирует до 3 uops на Haswell, но BMI2 shlx r, r, r равен 1. Так что слишком плохо, что gcc все еще испускает sal с помощью -march=haswell вместо использования shlx (который он использует в некоторых других случаях).

// hand-tuned BMI2 version using the NOT trick and the bitbroadcast
popcount_subset(std::bitset<64ul>, int):
    not     esi           ; The low 6 bits hold 63-pos.  gcc two-s complement trick
    xor     eax, eax      ; break false dependency on Intel.  maybe not needed when inlined.
    shlx    rdi, rdi, rsi ; rdi << ((63-pos) & 63)
    popcnt  rax, rdi
    sar     rdi, 63       ; broadcast the sign bit: rdi=0 or -1
    and     eax, edi      ; eax = 0 or its previous value
    ret

Анализ Perf для Intel Haswell: 6 fused-domain uops (интерфейс: один на 1.5c). Единицы выполнения: 2 p0/p6 shift uops. 1 p1 uop. 2 дескриптора с любым портом: (по одному на 1,25 с от общих пределов порт выполнения). Задержка критического пути: shlx (1) → popcnt (3) → and (1) = 5c bitset- > result. (или 6c из pos → результата).

Обратите внимание, что при встраивании человеческий (или интеллектуальный компилятор) может избежать необходимости в xor eax, eax. Он существует только из-за popcnt ложной зависимости от выходного регистра (на Intel), и нам нужен вывод в eax (который вызывающий мог использовать недавно для длинной цепочки отрезков). С -mtune=bdver2 или чем-то, gcc не будет нулевым регистром, который он будет использовать для вывода popcnt.

При встраивании мы можем использовать выходной регистр, который уже должен быть готов как минимум до popcnt source reg, чтобы избежать проблемы. Компиляторы сделают на месте popcnt rdi,rdi, когда источник не понадобится позже, но это не так. Вместо этого мы можем выбрать другой регистр, который уже должен быть готов к источнику. popcnt вход зависит от 63-pos, и мы можем его сжимать, поэтому зависимость popcnt rsi,rdi от rsi не может его задержать. Или, если бы мы имели 63 в регистре, мы могли бы popcnt rsi,rdi/sarx rax, rsi, reg_63/and eax, esi. Или инструкции по перемещению 3-операндов BMI2 также позволят нам не вводить в себя входы, если они понадобятся впоследствии.

Это настолько легкий вес, что накладные расходы цикла и настройка входных операндов/сохранение результатов будут основными факторами. (И 63-pos может оптимизироваться с постоянной времени компиляции или в любую точку, откуда приходит переменная.)

Компилятор Intel забавно стреляет в ногу и не использует тот факт, что A [63] - это бит знака. shl/bt rdi, 63/jc. Он даже настраивает ветки действительно глупо. Он может иметь нулевой eax, а затем перепрыгивать через popcnt или не на основе знака, установленного shl.

Оптимальная реализация ветвления, начиная с выхода ICC13 из -O3 -march=corei7 на godbolt:

   // hand-tuned, not compiler output
        mov       ecx, esi    ; ICC uses neg/add/mov :/
        not       ecx
        xor       eax, eax    ; breaks the false dep, or is the return value in the taken-branch case
        shl       rdi, cl
        jns    .bit_not_set
        popcnt    rax, rdi
.bit_not_set:
        ret

Это в значительной степени оптимально: в случае A[pos] == true есть одна не принятая ветвь. Тем не менее, это не сэкономит очень много на нераспространенном методе.

Если случай A[pos] == false более распространен: перепрыгните через команду ret, в popcnt/ret. (Или после вставки: переход к блоку в конце, который выполняет popcnt и отскакивает назад).

Ответ 2

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

Если вы закончите это, создайте битовую маску с этим битом (и менее значительными), а and - с исходным вводом. Затем используйте функцию члена count(), чтобы получить количество бит, заданное в результате.

Что касается создания маски: вы можете сдвинуть 1 левое N мест, а затем вычесть 1.

Ответ 3

Предполагая, что unsigned long или unsigned long long достаточно велик для хранения 64 бит, вы можете вызвать bits.to_unlong() (или bits.to_ullong()), чтобы получить данные битового набора в виде целого числа, замаскировать биты выше X ((1 << X) - 1) затем подсчитайте эти биты, как указано в ответе на вопрос, на который вы ссылаетесь.

Ответ 4

Легко конвертировать между битом и маской для бит ниже него, поэтому что-то вроде этого должно работать:

int popcnt(bitset<64> bs, int x) {
    // Early out when bit not set
    if (!bs[x]) return 0;
    // Otherwise, make mask from `x`, mask and count bits
    return (bs & bitset<64>((1UL << x) - 1)).count() + 1;
}

Предполагается, что bitset::count реализуется эффективно (используя popcnt внутренности или эффективный откат); это не гарантируется, но люди STL стремятся оптимизировать такие вещи.

Ответ 5

Я отредактировал проблему, которую я видел до того, как будет проверяться, установлено ли число или четное число бит в числе. Это для C, но не слишком сложно массировать его на С++. Суть решения заключается в том, что в цикле while. Попробуйте на бумаге понять, как он выбирает LSB, а затем удаляет его с x. Остальная часть кода прямолинейна. Код работает в O (n), где n - количество установленных бит в x. То, что намного лучше, чем линейное время, которое, как я думал, было возможно только при первом рассмотрении этой проблемы.

#include <stdio.h>

int
count(long x, int pos)
{
    /* if bit at location pos is not set, return 0 */
    if (!((x >> pos) & 1))
    {
        return 0;
    }

    /* prepare x by removing set bits after position pos */
    long tmp = x;
    tmp = tmp >> (pos + 1);
    tmp = tmp << (pos + 1);
    x ^= tmp;

    /* increment count every time the first set bit of x is removed (from the right) */
    int y;
    int count = 0;
    while (x != 0)
    {
        y = x & ~(x - 1);
        x ^= y;
        count++;
    }
    return count;
}

int
main(void)
{
    /* run tests */
    long num = 0b1010111;
    printf("%d\n", count(num, 0)); /* prints: 1 */
    printf("%d\n", count(num, 1)); /* prints: 2 */
    printf("%d\n", count(num, 2)); /* prints: 3 */
    printf("%d\n", count(num, 3)); /* prints: 0 */
    printf("%d\n", count(num, 4)); /* prints: 4 */
    printf("%d\n", count(num, 5)); /* prints: 0 */
    printf("%d\n", count(num, 6)); /* prints: 5 */
}