Битовый подсчет для большого буфера, с процессором Core 2 (SSSE3)
Я ищу самый быстрый способ поп-подсчета на большой буфер 512 или более байтов. Я могу гарантировать любое требуемое выравнивание, и размер буфера всегда равен степени 2. Буфер соответствует распределению блоков, поэтому обычно биты либо все установлены, ни установлены, либо большей частью установлены в пользу "левого" буфера, с случайные дыры.
Некоторые решения, которые я рассмотрел:
- ССЗ
__builtin_popcount - Bitslice
popcount_24words - Подсчет бит установлен, путь Брайана Кернигана
Меня интересует самое быстрое решение, оно должно работать на 32-битном чипсете x86, принадлежащем Core2 или более поздней версии. SSE и SIMD представляют большой интерес. Я буду тестировать на следующем четырехъядерном процессоре:
matt@stanley:~/anacrolix/public/stackru$ cat /proc/cpuinfo
processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 15
model name : Intel(R) Core(TM)2 Quad CPU Q6600 @ 2.40GHz
stepping : 11
cpu MHz : 1600.000
cache size : 4096 KB
physical id : 0
siblings : 4
core id : 0
cpu cores : 4
apicid : 0
initial apicid : 0
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 10
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm constant_tsc arch_perfmon pebs bts aperfmperf pni dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm lahf_lm tpr_shadow vnmi flexpriority
bogomips : 4800.21
clflush size : 64
cache_alignment : 64
address sizes : 36 bits physical, 48 bits virtual
power management:
4 ответа
Ниже я опишу лучшие функции C/ сборки, которые я нашел для подсчета населения / веса Хэмминга для больших буферов.
Самая быстрая функция сборки ssse3_popcount3, описанный здесь. Для него требуется SSSE3, доступный на Intel Core 2 и более поздних версиях, и наборы микросхем AMD, поступающие в 2011 году. Он использует инструкции SIMD для поп-подсчета в 16-байтовые блоки и развертывает 4 итерации цикла за раз.
Самая быстрая функция C popcount_24words, описанный здесь. Он использует алгоритм нарезки битов. Примечательно, что я обнаружил, что clang может генерировать соответствующие инструкции по сборке векторов, что дает впечатляющий прирост производительности. Помимо этого, алгоритм все еще чрезвычайно быстр.
См. 32-битную версию в руководстве по оптимизации программного обеспечения AMD, стр. 195, чтобы узнать об одной реализации. Это дает вам ассемблерный код для x86 напрямую.
Посмотрите вариант в Стэнфордских хитростях. Стэнфордская версия выглядит для меня как лучшая. Это выглядит очень просто для кодирования как x86 asm.
Ни один из них не использует инструкции ветвления.
Они могут быть обобщены до 64-битных версий.
С 32- или 64-битными версиями вы можете рассмотреть вариант SIMD. SSE2 будет делать 4 двойных слова или два четырехсловных слова (в любом случае 128 бит) одновременно. То, что вы хотите сделать, это реализовать поп-счет для 32 или 64 бит в каждом из 2 или 4 доступных регистров. Вы получите 2 или 4 набора поп-учетных записей в регистрах XMM, когда закончите; последний шаг - сохранить и добавить эти поп-учетные записи вместе, чтобы получить окончательный ответ. Предполагаю, что я ожидаю, что вы сделаете это немного лучше, если будете использовать 4 параллельных 32-битных popcounts, а не 2 параллельных 64-bit popcounts, поскольку последний, вероятно, будет принимать 1 или 2 дополнительные инструкции в каждой итерации, и его легко добавить 4, 32 bit Ценности вместе конец.
Я хотел бы предложить реализовать одну из оптимизированных 32-битных подпрограмм popcnt из Delight Хакера, но сделать это для 4 x 32-битных целочисленных элементов в векторе SSE. Затем вы можете обрабатывать 128 бит на итерацию, что должно обеспечить пропускную способность примерно в 4 раза по сравнению с оптимизированной 32-битной скалярной процедурой.