libpopcnt

libpopcnt

libpopcnt.h é uma biblioteca C/C++ somente de cabeçalho para contar o número de 1 bits (contagem de população de bits) em um array o mais rápido possível usando instruções especializadas de CPU, ou seja, POPCNT, AVX2, AVX512, NEON, SVE. libpopcnt.h foi testado com sucesso usando os compiladores GCC, Clang e 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 não requer nenhum sinalizador especial do compilador como -mavx2 ! Para obter o melhor desempenho, recomendamos apenas compilar com otimizações habilitadas, por exemplo -O3 ou -O2 .

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

Arquiteturas de CPU

libpopcnt.h possui algoritmos popcount acelerados por hardware para as seguintes arquiteturas de CPU:

x86	POPCNT , AVX2 , AVX512
x86-64	POPCNT , AVX2 , AVX512
BRAÇO	NEON , SVE
PPC64	POPCNTD

Para outras arquiteturas de CPU, um algoritmo popcount inteiro rápido é usado.

Como funciona

Em CPUs x86, libpopcnt.h primeiro consulta os conjuntos de instruções suportados pela sua CPU usando a instrução CPUID (isso é feito apenas uma vez). Então libpopcnt.h escolhe o algoritmo de contagem de população de bits mais rápido suportado pela sua CPU:

• Se a CPU suportar AVX512 o algoritmo AVX512 VPOPCNT será usado.
• Caso contrário, se a CPU suportar AVX2 o algoritmo AVX2 Harley Seal será usado.
• Caso contrário, se a CPU suportar POPCNT o algoritmo POPCNT será usado.
• Para CPUs sem instrução POPCNT é usado um algoritmo inteiro portátil.

Observe que libpopcnt.h funciona em todas as CPUs (x86, ARM, PPC, WebAssembly, ...). É portátil por padrão e a aceleração de hardware só é habilitada se a CPU suportar. libpopcnt.h também é seguro para threads.

Levamos o desempenho a sério, se você compilar usando, por exemplo, -march=native em uma CPU x86 com suporte AVX512, todas as verificações CPUID em tempo de execução serão removidas!

ARM SVE (extensão de vetor escalável)

ARM SVE é um novo conjunto de instruções vetoriais para CPUs ARM que foi lançado pela primeira vez em 2020. ARM SVE suporta um comprimento de vetor variável de 128 a 2.048 bits. Conseqüentemente, os algoritmos ARM SVE podem ser muito mais rápidos do que os algoritmos ARM NEON, que são limitados a um comprimento de vetor de 128 bits.

O novo algoritmo ARM SVE popcount da libpopcnt é até 3x mais rápido que seu algoritmo ARM NEON popcount (em CPUs AWS Graviton3). Infelizmente, o despacho em tempo de execução para ARM SVE ainda não é bem suportado pelos compiladores GCC e Clang e libcs. Portanto, por padrão, apenas o algoritmo ARM NEON popcount (portátil) é habilitado ao usar libpopcnt em CPUs ARM.

Para habilitar o algoritmo ARM SVE popcount da libpopcnt você precisa compilar seu programa usando a opção ARM SVE do seu compilador, por exemplo:

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

Desenvolvimento

cmake .
make -j
make test

Os comandos acima também constroem o programa benchmark que é útil para benchmarking libpopcnt.h . Abaixo está um exemplo de uso executado em uma 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

Agradecimentos

Alguns dos algoritmos usados ​​em libpopcnt.h são descritos no artigo Faster Population Counts using AVX2 Instructions de Daniel Lemire, Nathan Kurz e Wojciech Mula (23 de novembro de 2016). O algoritmo AVX2 Harley Seal popcount usado em libpopcnt.h foi copiado do repositório GitHub sse-popcount de Wojciech Muła.