libpopcnt
libpopcnt-3.1
libpopcnt.h est une bibliothèque C / C ++ d'en-tête uniquement pour compter le nombre de 1 bits (nombre de populations de bit) dans un tableau le plus rapidement possible en utilisant des instructions CPU spécialisées, c'est-à-dire 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é EG -O3 ou -O2 .
cc -O3 program.c
c++ -O3 program.cpp libpopcnt.h a des algorithmes de popcount accélérés en matériel pour les architectures de CPU suivantes:
| x86 | POPCNT , AVX2 , AVX512 |
| x86-64 | POPCNT , AVX2 , AVX512 |
| BRAS | NEON , SVE |
| PPC64 | POPCNTD |
Pour d'autres architectures de processeur, un algorithme popcount entier rapide est utilisé.
Sur x86 CPU, libpopcnt.h interroge d'abord les ensembles d'instructions pris en charge de votre CPU en utilisant l'instruction CPUID (ce n'est fait qu'une seule fois). Ensuite, libpopcnt.h choisit l'algorithme de nombre de populations les plus rapides soutenu par votre processeur:
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 processeurs (x86, bras, ppc, webassembly, ...). Il est portable par défaut et l'accélération matérielle n'est activée que si le CPU le prend en charge. libpopcnt.h Il est également enfile.
Nous prenons les performances au sérieux, si vous compilez en utilisant eg -march=native sur un CPU x86 avec support AVX512, tous les vérifications CPUID d'exécution sont supprimées!
ARM SVE est un nouvel ensemble d'instructions vectoriel pour les processeurs ARM qui ont été publiés 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 de SVE ARM peuvent être beaucoup plus rapides que les algorithmes néon de bras qui sont limités à la longueur du vecteur de 128 bits.
Le nouvel algorithme de popcount de SVE de LibPopcnt est jusqu'à 3x plus rapide que son algorithme de popcount de bras sur le bras (sur des processeurs AWS Graviton3). Malheureusement, la répartition de l'exécution à Arm SVE n'est pas encore bien soutenue par les compilateurs GCC et CLANG et LIBC. Par conséquent, par défaut, seul l'algorithme PopCount (portable) ARM Neon est activé lors de l'utilisation de CPU libpopcnt sur ARM.
Pour activer l'algorithme PopCount de SVE de LibPopcnt, vous devez compiler votre programme en utilisant l'option 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 à partir 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 le nombre de comptes de population plus rapides en utilisant les instructions AVX2 de Daniel Lemire, Nathan Kurz et Wojciech Mula (23 novembre 2016). L'algorithme de popcount Avx2 Harley Seal utilisé dans libpopcnt.h a été copié à partir du référentiel Github SSE-PopCount de Wojciech Muła.
