Ответ 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(akasal) со счетом в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 и отскакивает назад).