Битовый подсчет для большого буфера, с процессором Core 2 (SSSE3) - PullRequest
Новая
       39

Битовый подсчет для большого буфера, с процессором Core 2 (SSSE3)

12 голосов
/ 12 сентября 2010

Я ищу самый быстрый способ поп-подсчета на большом буфере 512 или более байтов. Я могу гарантировать любое требуемое выравнивание, а размер буфера всегда равен степени 2. Буфер соответствует распределению блоков, поэтому обычно биты либо все установлены, ни установлены, либо большей частью установлены в «левом» положении буфера, с случайные отверстия.

Некоторые решения, которые я рассмотрел:

Меня интересует самое быстрое решение, оно должно работать на 32-битном чипсете x86, принадлежащем Core2 или более поздней версии. SSE и SIMD представляют большой интерес. Я буду тестировать на следующем четырехъядерном процессоре: 

matt@stanley:~/anacrolix/public/stackoverflow$ 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 ]

4 голосов
/ 13 сентября 2010

См. 32-разрядную версию в Руководстве по оптимизации программного обеспечения AMD , стр. 195, где приведена одна реализация. Это дает вам ассемблерный код для x86 напрямую.

См. Вариант в Стэнфордские хитрые хаки Стэнфордская версия выглядит для меня как лучшая. Это выглядит очень легко кодировать как x86 asm.

Ни одна из этих инструкций не используется.

Их можно обобщить до 64-битных версий.

В 32- или 64-разрядных версиях вы можете рассмотреть вариант SIMD. SSE2 выполнит 4 двойных слова или два четырехсловных слова (в любом случае 128 бит) однажды. Что вы хотите сделать, это реализовать поп-счет для 32 или 64 бита в каждом из 2 или 4 доступных регистров. В итоге вы получите 2 или 4 набора поп-учетных записей в регистрах XMM. когда вы сделали; последний шаг - сохранить и добавить эти поп-счет вместе, чтобы получить окончательный ответ. Гадание, Я ожидаю, что вы делаете это немного лучше, делая 4 параллельных 32 битовые поп-аккаунты вместо двух параллельных 64-битных поп-аккаунтов поскольку последний, вероятно, примет 1 или 2 дополнительные инструкции в каждой итерации, и легко добавить 4, 32-битные значения вместе конец.

2 голосов
/ 21 февраля 2011

Я обрисовываю лучшие функции C / сборки, которые я нашел для количества населения / веса Хэмминга больших буферов ниже.

Самая быстрая функция сборки - ssse3_popcount3, описанная здесь . Для этого требуется SSSE3 , доступный на Intel Core 2 и более поздних версиях, и наборы микросхем AMD, поступающие в 2011 году. Он использует инструкции SIMD для поп-подсчета в 16-байтовые блоки и развертывает 4 итерации цикла за раз.

Самая быстрая функция C - popcount_24words, описанная здесь . Он использует алгоритм нарезки битов. Примечательно, что я обнаружил, что clang действительно может генерировать соответствующие инструкции по сборке векторов, что дает впечатляющий прирост производительности. Помимо этого, алгоритм все еще очень быстр.

2 голосов
/ 12 сентября 2010
1 голос
/ 12 сентября 2010

Я бы предложил реализовать одну из оптимизированных 32-битных подпрограмм popcnt из Восторг Хакера , но сделать это для 4 x 32-битных целочисленных элементов в векторе SSE. Затем вы можете обрабатывать 128 бит на итерацию, что должно дать вам примерно 4-кратную пропускную способность по сравнению с оптимизированной 32-битной скалярной подпрограммой.

...