libpopcnt
libpopcnt-3.1
libpopcnt.h est une bibliothèque C/C++ uniquement en-tête permettant de compter le nombre de 1 bits (nombre de bits) dans un tableau le plus rapidement possible à l'aide d'instructions CPU spécialisées, par exemple POPCNT, AVX2, AVX512, NEON, SVE. libpopcnt.h a été testé avec succès à l'aide des compilateurs GCC, Clang et MSVC.
#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 ne nécessite aucun indicateur de compilateur spécial comme -mavx2 ! Pour obtenir les meilleures performances, nous recommandons uniquement de compiler avec les optimisations activées, par exemple -O3 ou -O2 .
cc -O3 program.c
c++ -O3 program.cpp libpopcnt.h dispose d'algorithmes de popcount à accélération matérielle pour les architectures de processeur suivantes :
| x86 | POPCNT , AVX2 , AVX512 |
| x86-64 | POPCNT , AVX2 , AVX512 |
| BRAS | NEON , SVE |
| PPC64 | POPCNTD |
Pour les autres architectures de processeur, un algorithme de comptage rapide d'entiers est utilisé.
Sur les processeurs x86, libpopcnt.h interroge d'abord les jeux d'instructions pris en charge par votre processeur à l'aide de l'instruction CPUID (cela n'est effectué qu'une seule fois). Ensuite, libpopcnt.h choisit l'algorithme de comptage de bits le plus rapide pris en charge par votre CPU :
AVX512 l'algorithme AVX512 VPOPCNT est utilisé.AVX2 l'algorithme AVX2 Harley Seal est utilisé.POPCNT l'algorithme POPCNT est utilisé.POPCNT un algorithme entier portable est utilisé. Notez que libpopcnt.h fonctionne sur tous les CPU (x86, ARM, PPC, WebAssembly, ...). Il est portable par défaut et l'accélération matérielle n'est activée que si le processeur la prend en charge. libpopcnt.h est également thread-safe.
Nous prenons les performances au sérieux, si vous compilez en utilisant par exemple -march=native sur un processeur x86 avec prise en charge AVX512, alors toutes les vérifications CPUID d'exécution sont supprimées !
ARM SVE est un nouveau jeu d'instructions vectorielles pour les processeurs ARM qui a été publié pour la première fois en 2020. ARM SVE prend en charge une longueur de vecteur variable de 128 à 2048 bits. Par conséquent, les algorithmes ARM SVE peuvent être beaucoup plus rapides que les algorithmes ARM NEON qui sont limités à une longueur de vecteur de 128 bits.
Le nouvel algorithme de popcount ARM SVE de libpopcnt est jusqu'à 3 fois plus rapide que son algorithme de popcount ARM NEON (sur les processeurs AWS Graviton3). Malheureusement, la distribution du runtime vers ARM SVE n'est pas encore bien prise en charge par les compilateurs GCC et Clang et les libc. Par conséquent, par défaut, seul l'algorithme (portable) ARM NEON popcount est activé lors de l'utilisation de libpopcnt sur les processeurs ARM.
Pour activer l'algorithme popcount ARM SVE de libpopcnt, vous devez compiler votre programme à l'aide de l'option ARM SVE de votre compilateur, par exemple :
gcc -O3 -march=armv8-a+sve program.c
g++ -O3 -march=armv8-a+sve program.cppcmake .
make -j
make test Les commandes ci-dessus construisent également le programme benchmark qui est utile pour l'analyse comparative libpopcnt.h . Vous trouverez ci-dessous un exemple d'utilisation exécuté sur un processeur 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 Certains des algorithmes utilisés dans libpopcnt.h sont décrits dans l'article Faster Population Counts using AVX2 Instructions de Daniel Lemire, Nathan Kurz et Wojciech Mula (23 novembre 2016). L'algorithme popcount AVX2 Harley Seal utilisé dans libpopcnt.h a été copié du dépôt GitHub sse-popcount de Wojciech Muła.
