libpopcnt

libpopcnt

libpopcnt.h es una biblioteca C/C++ de solo encabezado para contar el número de 1 bits (recuento de población de bits) en una matriz lo más rápido posible utilizando instrucciones de CPU especializadas, es decir, POPCNT, AVX2, AVX512, NEON, SVE. libpopcnt.h se ha probado con éxito utilizando los compiladores GCC, Clang y MSVC.

API C/C++

 #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 );

como compilar

libpopcnt.h no requiere ningún indicador de compilación especial como -mavx2 ! Para obtener el mejor rendimiento, solo recomendamos compilar con las optimizaciones habilitadas, por ejemplo, -O3 o -O2 .

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

arquitecturas de CPU

libpopcnt.h tiene algoritmos de recuento de pops acelerados por hardware para las siguientes arquitecturas de CPU:

x86	POPCNT , AVX2 , AVX512
x86-64	POPCNT , AVX2 , AVX512
BRAZO	NEON , SVE
PPC64	POPCNTD

Para otras arquitecturas de CPU, se utiliza un algoritmo de recuento de números enteros rápido.

como funciona

En CPU x86, libpopcnt.h primero consulta los conjuntos de instrucciones admitidos por su CPU usando la instrucción CPUID (esto se hace solo una vez). Luego libpopcnt.h elige el algoritmo de recuento de población de bits más rápido admitido por su CPU:

• Si la CPU admite AVX512 se utiliza el algoritmo AVX512 VPOPCNT .
• De lo contrario, si la CPU admite AVX2 se utiliza el algoritmo AVX2 Harley Seal .
• De lo contrario, si la CPU admite POPCNT se utiliza el algoritmo POPCNT .
• Para CPU sin instrucción POPCNT se utiliza un algoritmo entero portátil.

Tenga en cuenta que libpopcnt.h funciona en todas las CPU (x86, ARM, PPC, WebAssembly, ...). Es portátil de forma predeterminada y la aceleración de hardware solo está habilitada si la CPU la admite. libpopcnt.h también es seguro para subprocesos.

Nos tomamos el rendimiento en serio; si compila utilizando, por ejemplo, -march=native en una CPU x86 con soporte AVX512, ¡se eliminan todas las comprobaciones CPUID en tiempo de ejecución!

ARM SVE (Extensión vectorial escalable)

ARM SVE es un nuevo conjunto de instrucciones vectoriales para CPU ARM que se lanzó por primera vez en 2020. ARM SVE admite una longitud de vector variable de 128 a 2048 bits. Por lo tanto, los algoritmos ARM SVE pueden ser mucho más rápidos que los algoritmos ARM NEON, que están limitados a una longitud de vector de 128 bits.

El nuevo algoritmo de recuento de pops ARM SVE de libpopcnt es hasta 3 veces más rápido que su algoritmo de recuento de pops ARM NEON (en CPU AWS Graviton3). Desafortunadamente, el envío del tiempo de ejecución a ARM SVE aún no es compatible con los compiladores GCC y Clang y libc. Por lo tanto, de forma predeterminada, solo el algoritmo (portátil) ARM NEON popcount está habilitado cuando se usa libpopcnt en CPU ARM.

Para habilitar el algoritmo popcount ARM SVE de libpopcnt, necesita compilar su programa usando la opción ARM SVE de su compilador, por ejemplo:

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

Desarrollo

cmake .
make -j
make test

Los comandos anteriores también construyen el programa benchmark que es útil para realizar evaluaciones comparativas libpopcnt.h . A continuación se muestra un ejemplo de uso ejecutado en una CPU AMD EPYC 9R14 de 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

Expresiones de gratitud

Algunos de los algoritmos utilizados en libpopcnt.h se describen en el artículo Faster Population Counts usando instrucciones AVX2 de Daniel Lemire, Nathan Kurz y Wojciech Mula (23 de noviembre de 2016). El algoritmo popcount AVX2 Harley Seal utilizado en libpopcnt.h ha sido copiado del repositorio GitHub sse-popcount de Wojciech Muła.