libpopcnt

libpopcnt

libpopcnt.h ist eine reine Header-C/C++-Bibliothek zum schnellstmöglichen Zählen der Anzahl von 1-Bits (Bitpopulationsanzahl) in einem Array mithilfe spezieller CPU-Anweisungen, z. B. POPCNT, AVX2, AVX512, NEON, SVE. libpopcnt.h wurde erfolgreich mit den Compilern GCC, Clang und MSVC getestet.

C/C++-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 );

So kompilieren Sie

libpopcnt.h erfordert keine speziellen Compiler-Flags wie -mavx2 ! Um die beste Leistung zu erzielen, empfehlen wir nur die Kompilierung mit aktivierten Optimierungen, z. B. -O3 oder -O2 .

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

CPU-Architekturen

libpopcnt.h verfügt über hardwarebeschleunigte Popcount-Algorithmen für die folgenden CPU-Architekturen:

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

Für andere CPU-Architekturen wird ein schneller Integer-Popcount-Algorithmus verwendet.

Wie es funktioniert

Auf x86-CPUs fragt libpopcnt.h zunächst die unterstützten Befehlssätze Ihrer CPU mithilfe der CPUID Anweisung ab (dies erfolgt nur einmal). Dann wählt libpopcnt.h den schnellsten Bitpopulationszählalgorithmus, der von Ihrer CPU unterstützt wird:

• Wenn die CPU AVX512 unterstützt, wird der AVX512 VPOPCNT -Algorithmus verwendet.
• Andernfalls wird, wenn die CPU AVX2 unterstützt, der AVX2 Harley Seal -Algorithmus verwendet.
• Andernfalls wird der POPCNT -Algorithmus verwendet, wenn die CPU POPCNT unterstützt.
• Für CPUs ohne POPCNT -Anweisung wird ein portabler Integer-Algorithmus verwendet.

Beachten Sie, dass libpopcnt.h auf allen CPUs funktioniert (x86, ARM, PPC, WebAssembly, ...). Es ist standardmäßig portabel und die Hardwarebeschleunigung ist nur aktiviert, wenn die CPU dies unterstützt. libpopcnt.h ist außerdem threadsicher.

Wir nehmen die Leistung ernst. Wenn Sie beispielsweise mit -march=native auf einer x86-CPU mit AVX512-Unterstützung kompilieren, werden alle CPUID Prüfungen zur Laufzeit entfernt!

ARM SVE (Skalierbare Vektorerweiterung)

ARM SVE ist ein neuer Vektorbefehlssatz für ARM-CPUs, der erstmals im Jahr 2020 veröffentlicht wurde. ARM SVE unterstützt eine variable Vektorlänge von 128 bis 2048 Bit. Daher können ARM-SVE-Algorithmen viel schneller sein als ARM-NEON-Algorithmen, die auf eine Vektorlänge von 128 Bit begrenzt sind.

Der neue ARM SVE Popcount-Algorithmus von libpopcnt ist bis zu dreimal schneller als sein ARM NEON Popcount-Algorithmus (auf AWS Graviton3-CPUs). Leider wird die Laufzeitverteilung an ARM SVE von den GCC- und Clang-Compilern und libcs ​​noch nicht gut unterstützt. Daher ist standardmäßig nur der (tragbare) ARM NEON Popcount-Algorithmus aktiviert, wenn libpopcnt auf ARM-CPUs verwendet wird.

Um den ARM SVE-Popcount-Algorithmus von libpopcnt zu aktivieren, müssen Sie Ihr Programm mit der ARM SVE-Option Ihres Compilers kompilieren, z. B.:

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

Entwicklung

cmake .
make -j
make test

Die oben genannten Befehle erstellen auch das benchmark Programm, das für das Benchmarking libpopcnt.h nützlich ist. Unten finden Sie ein Anwendungsbeispiel, das auf einer AMD EPYC 9R14-CPU aus dem Jahr 2023 ausgeführt wird:

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

Danksagungen

Einige der in libpopcnt.h verwendeten Algorithmen werden im Artikel Faster Population Counts using AVX2 Instructions von Daniel Lemire, Nathan Kurz und Wojciech Mula (23. November 2016) beschrieben. Der in libpopcnt.h verwendete AVX2 Harley Seal Popcount-Algorithmus wurde aus Wojciech Mułas sse-popcount GitHub-Repo kopiert.