Bit popcount для большого буфера с процессором Core 2 (SSSE3)

Я ищу самый быстрый способ popcount для большого буфера 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:

c x86 optimization assembly hammingweight
person Matt Joiner    schedule 12.09.2010    source источник
comment
@aaa carp: Пожалуйста, предоставьте пример кода, используя это в качестве ответа! Ссылки на канонические описания popcnt и способов его использования на GCC также являются хорошей идеей.   -  person Matt Joiner    schedule 12.09.2010
comment
@Matt, вы обнаружите, что это упоминается здесь secure.wikimedia.org/wikipedia/en/wiki/ SSE4   -  person Jens Gustedt    schedule 12.09.2010
comment
@Jens Gustedt: я знаю об инструкции (хотя она не поддерживается моим процессором), но не знаю о ее использовании в GCC.   -  person Matt Joiner    schedule 12.09.2010
comment
@Matt: если вы используете gcc, я бы в любом случае не беспокоился о реализации этого на ассемблере. Я бы доверился ребятам, использовал __builtin_popcountll и скомпилировал с -march=native. Но у меня нет этой инструкции и на моей машине, поэтому я не могу подтвердить, что это делается правильно: на моей машине это все еще приводит к вызову функции.   -  person Jens Gustedt    schedule 12.09.2010
comment
Почему? Самый первый хит Google для popcount, по-видимому, был недавней страницей Барта Мэсси (автора XCB), документирующего его поиск лучшего алгоритма popcount, который включает не только алгоритмы, которые он пробовал, но также его код и результаты бенчмаркинга.   -  person llasram    schedule 12.09.2010
comment
ЦП, который вы показали выше, в любом случае не имеет инструкции popcnt (для наличия этой инструкции существует специальный флаг функции, который отображается как popcnt в строке flags в /proc/cpuinfo).   -  person Matthew Slattery    schedule 12.09.2010
comment
@Matthew Slattery: Да, я уже указал на это, я ожидал sse4 для инструкции POPCNT.   -  person Matt Joiner    schedule 12.09.2010
comment
@llasram: Да, я уже посмотрел и пропустил их, они не оптимизированы для больших буферов.   -  person Matt Joiner    schedule 12.09.2010
comment
@Matt: Может быть, я что-то упускаю, но что (кроме потенциально SIMD-инструкций) может привести к тому, что наиболее эффективный алгоритм для отдельных слов окажется не самым эффективным для больших буферов?   -  person llasram    schedule 12.09.2010
comment
@llasram: Некоторые примеры: 24 слова, связанные с моим вопросом, могут работать с фрагментами по 96 байт без единой ветки. Ускорение операций с отдельными словами — это хорошо, но для большого массива по-прежнему требуется O(n) с неявной проверкой границ и т. д. Другим является развертывание, алгоритмы, оптимизированные для больших буферов, могут использовать это с огромным эффектом. Часто сочетание нетривиальной последовательности инструкций может выполнить подсчет всплывающих окон (или какую-либо другую задачу) за гораздо меньшее количество циклов, чем работа со словами по отдельности. В другом алгоритме, который я нашел, удалось использовать инструкцию MULT для сокращения циклов.   -  person Matt Joiner    schedule 12.09.2010
comment
Существуют ли какие-либо требования к атомарности/многопоточному доступу?   -  person rwong    schedule 13.09.2010
comment
@Matt: Я ожидаю, что POPCNT будет реализован за очень небольшое количество циклов, и в этом случае его, вероятно, сложно превзойти, особенно если вы развернете цикл, содержащий POPCNT 16x или что-то подобное. Если у вас нет POPCNT, может применяться хитрый ассемблерный код.   -  person Ira Baxter    schedule 14.09.2010
comment
[Извините за удаление такого старого вопроса] Хотя такие эксперименты всегда забавны, а иногда даже полезны, я хотел бы отметить, что (без разумной, очевидной причины) я только что скомпилировал и запустил набор тестов на своем умеренно- последний (Skylake) рабочий стол. Неудивительно, что самое простое, самое прямолинейное, наиболее читаемое решение, использующее встроенную компилятор, работает более чем в 4 раза быстрее, чем лучшая оптимизированная (и совершенно нечитаемая) версия.   -  person Damon    schedule 13.11.2018

Ответы (4)


arrow_upward
5
arrow_downward

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

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

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

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

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

person Ira Baxter    schedule 13.09.2010
comment
Можете ли вы предоставить ссылки на руководство AMD и инструкции SIMD, которые вы бы использовали? - person Matt Joiner; 13.09.2010
comment
@Matt: К сожалению, я испортил ссылку на руководство по оптимизации AMD, исправлено. - person Ira Baxter; 13.09.2010
comment
@Matt: Что касается инструкций SIMD: закодированные примеры состоят в основном из скалярных машинных инструкций LOAD, AND, SHIFT, ADD и не имеют ветвей. Инструкции x86 SIMD легко найти эквиваленты; единственная реальная проблема заключается в том, чтобы убедиться, что операнды выровнены по границам 128 или 256 бит, в зависимости от того, какой набор SIMD вы используете. Вы сказали, что для вас это не проблема :-} - person Ira Baxter; 13.09.2010
comment
@Matt: Вы заставили меня поиграть с этим ... все перечисленные здесь решения вычисляют popcnt для одного слова. Очевидно, вы можете развернуть цикл, чтобы сделать более одного слова, и вы можете использовать SIMD. Что может быть не столь очевидным, так это то, что можно вычислить popcnt для нескольких слов одновременно примерно за половину инструкций, необходимых для выполнения одного, амортизированных (я набросал доказательство существования на полях SO :-}, но это слишком слишком громоздкий, чтобы поместиться в этот комментарий. Это прекрасно сработает с вашим 512-байтовым буфером для обработки. Насколько сильно вы хотите получить самый быстрый ответ? - person Ira Baxter; 13.09.2010
comment
@ Ира Бакстер: я рад, что кто-то понимает, что есть разница. Я очень хочу увидеть ответы, которые могут превзойти то, что у меня есть в настоящее время, или привлекательно обменять производительность на простоту и необходимые функции чипсета. - person Matt Joiner; 13.09.2010
comment
@Matt: вы не получите простоты, если хотите высокой производительности; вы получите запутанный фрагмент кода, в котором используется множество малоизвестных фактов. Хотите показать то, что у вас уже есть? - person Ira Baxter; 13.09.2010

arrow_upward
2
arrow_downward

Если у вас был popcnt:

http://kent-vandervelden.blogspot.com/2009/10/counting-bits-population-count-and.html

http://software.intel.com/sites/products/documentation/studio/composer/en-us/2011/compiler_c/intref_cls/common/intref_sse42_ATA.htm

person Anycorn    schedule 12.09.2010

arrow_upward
2
arrow_downward

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

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

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

person Matt Joiner    schedule 21.02.2011
comment
Также обратите внимание, что в SSE4 есть инструкция POPCNT. - person Paul R; 16.03.2011
comment
@Paul R: Да, об этом упоминалось. Я ограничил решения SSSE3 или ниже в вопросе, также было обнаружено, что POPCNT, хотя и очень быстрый и удобный, не быстрее, чем некоторые векторизованные решения. - person Matt Joiner; 16.03.2011
comment
Это неправильно. POPCNT это самый быстрый способ сделать это. Эталонные показатели и подробное объяснение здесь. - person dan; 03.11.2014
comment
Этот ответ можно значительно улучшить, показав фактический код, а не завися от внешних сайтов. Как бы то ни было, ответ может быть признан недействительным из-за изменений в ресурсах, находящихся вне вашего контроля. - person Toby Speight; 02.02.2017
comment
@dan: AVX2 превосходит скаляр popcnt на современном Intel (Haswell и более поздние версии). Но только с 256-битными векторами: AVX1/SSSE3 не быстрее, IIRC. Райзен интересен; у него есть 4 64-битных popcnt за такт, поэтому, вероятно, лучше всего он работает со скаляром. AVX512 vpternlogd обеспечивает дополнительные оптимизации: большое (0,1) умножение матриц с использованием побитового AND и popcount вместо фактических умножений int или float?, в частности github.com/WojciechMula/sse-popcount/blob /master/ делает 30x vpternlogd + 1 vector popcnt для 16x векторов ZMM (16x 512 бит). - person Peter Cordes; 28.04.2018

arrow_upward
1
arrow_downward

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

person Paul R    schedule 12.09.2010
comment
Я не знаю, как это реализовано в подпрограммах, на которые вы ссылаетесь, но, безусловно, инструкция SSE4.1 POPCNT работает только с регистрами общего назначения, а не с регистрами XMM. - person PhiS; 13.09.2010
comment
@PhiS: действительно - я не предлагаю использовать SSE 4.1 POPCNT - в Hacker's Delight есть несколько эффективных подпрограмм для 32-битного popcnt в C, которые можно использовать в качестве основы для реализации SSE 4 x 32-битного popcnt. Затем вы перебираете свой блок данных, по 128 бит за раз, генерируя 4 x 32-битных частичных подсчета населения, которые затем можно суммировать в конце, чтобы получить общее количество населения. - person Paul R; 13.09.2010
comment
На самом деле некоторые из лучших решений, которые я нашел, использовали векторные операции для 128-битного подсчета. - person Matt Joiner; 21.02.2011