libpopcnt

libpopcnt

libpopcnt.h — это библиотека C/C++, предназначенная только для заголовков, предназначенная для максимально быстрого подсчета количества битов (счета битов) в массиве с использованием специализированных инструкций ЦП, например POPCNT, AVX2, AVX512, NEON, SVE. libpopcnt.h успешно протестирован с использованием компиляторов GCC, Clang и MSVC.

API С/С++

 #include "libpopcnt.h"

/*
 * Count the number of 1 bits in the data array
 * @data: An array
 * @size: Size of data in bytes
 */
uint64_t popcnt ( const void * data , uint64_t size );

Как скомпилировать

libpopcnt.h не требует каких-либо специальных флагов компилятора, таких как -mavx2 ! Для достижения максимальной производительности мы рекомендуем компилировать только с включенными оптимизациями, например -O3 или -O2 .

cc  -O3 program.c
c++ -O3 program.cpp

Архитектуры ЦП

libpopcnt.h содержит алгоритмы popcount с аппаратным ускорением для следующих архитектур ЦП:

х86	POPCNT , AVX2 , AVX512
х86-64	POPCNT , AVX2 , AVX512
РУКА	NEON , SVE
КПП64	POPCNTD

Для других архитектур ЦП используется быстрый алгоритм подсчета целочисленных значений.

Как это работает

На процессорах x86 libpopcnt.h сначала запрашивает поддерживаемые наборы инструкций вашего процессора, используя инструкцию CPUID (это делается только один раз). Затем libpopcnt.h выбирает самый быстрый алгоритм подсчета битов, поддерживаемый вашим процессором:

• Если ЦП поддерживает AVX512 используется алгоритм AVX512 VPOPCNT .
• В противном случае, если ЦП поддерживает AVX2 используется алгоритм AVX2 Harley Seal .
• В противном случае, если ЦП поддерживает POPCNT используется алгоритм POPCNT .
• Для процессоров без инструкции POPCNT используется переносимый целочисленный алгоритм.

Обратите внимание, что libpopcnt.h работает на всех процессорах (x86, ARM, PPC, WebAssembly,...). По умолчанию он портативен, и аппаратное ускорение включается только в том случае, если процессор его поддерживает. libpopcnt.h также является потокобезопасным.

Мы серьезно относимся к производительности: если вы компилируете, например, с использованием -march=native на процессоре x86 с поддержкой AVX512, все проверки CPUID во время выполнения удаляются!

ARM SVE (масштабируемое векторное расширение)

ARM SVE — это новый набор векторных команд для процессоров ARM, который был впервые выпущен в 2020 году. ARM SVE поддерживает переменную длину вектора от 128 до 2048 бит. Следовательно, алгоритмы ARM SVE могут быть намного быстрее, чем алгоритмы ARM NEON, длина вектора которых ограничена 128 битами.

Новый алгоритм подсчета всплывающих окон ARM SVE от libpopcnt работает до 3 раз быстрее, чем алгоритм подсчета всплывающих окон ARM NEON (на процессорах AWS Graviton3). К сожалению, диспетчеризация времени выполнения в ARM SVE пока недостаточно хорошо поддерживается компиляторами GCC и Clang, а также библиотеками libc. Поэтому по умолчанию при использовании libpopcnt на процессорах ARM включен только (портативный) алгоритм popcount ARM NEON.

Чтобы включить алгоритм popcount ARM SVE в libpopcnt, вам необходимо скомпилировать программу, используя опцию ARM SVE вашего компилятора, например:

gcc -O3 -march=armv8-a+sve program.c
g++ -O3 -march=armv8-a+sve program.cpp

Разработка

cmake .
make -j
make test

Приведенные выше команды также создают программу benchmark , которая полезна для тестирования libpopcnt.h . Ниже приведен пример использования на процессоре AMD EPYC 9R14 2023 года выпуска:

 # Usage: ./benchmark [array bytes] [iters]
./benchmark
Iters: 10000000
Array size: 16.00 KB
Algorithm: AVX512
Status: 100%
Seconds: 1.23
133.5 GB/s

Благодарности

Некоторые алгоритмы, используемые в libpopcnt.h описаны в статье Faster Population Counts using AVX2 Instructions Дэниела Лемира, Натана Курца и Войцеха Мулы (23 ноября 2016 г.). Алгоритм подсчета popcount AVX2 Harley Seal, используемый в libpopcnt.h был скопирован из репозитория sse-popcount Войцеха Мулы на GitHub.