libpopcnt

libpopcnt

libpopcnt.h是一個僅包含頭檔的 C/C++ 函式庫，用於使用專用 CPU 指令（即 POPCNT、AVX2、AVX512、NEON、SVE）盡快計算陣列中 1 位元的數量（位元總數計數）。 libpopcnt.h已使用 GCC、Clang 和 MSVC 編譯器成功測試。

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

如何編譯

libpopcnt.h不需要任何特殊的編譯器標誌，例如-mavx2 ！為了獲得最佳效能，我們僅建議在啟用最佳化的情況下進行編譯，例如-O3或-O2 。

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

CPU架構

libpopcnt.h具有適用於下列 CPU 架構的硬體加速 popcount 演算法：

x86	POPCNT , AVX2 , AVX512
x86-64	POPCNT , AVX2 , AVX512
手臂	NEON
PPC64	POPCNTD

對於其他 CPU 架構，使用快速整數 popcount 演算法。

它是如何運作的

在 x86 CPU 上， libpopcnt.h首先使用CPUID指令查詢 CPU 支援的指令集（僅執行一次）。然後libpopcnt.h選擇您的 CPU 支援的最快位元填充計數演算法：

• 如果 CPU 支援AVX512則使用AVX512 VPOPCNT演算法。
• 否則，如果 CPU 支援AVX2則使用AVX2 Harley Seal演算法。
• 否則，如果 CPU 支援POPCNT則使用POPCNT演算法。
• 對於沒有POPCNT指令的 CPU，使用可移植整數演算法。

請注意， libpopcnt.h適用於所有 CPU（x86、ARM、PPC、WebAssembly...）。預設情況下它是可移植的，並且僅在 CPU 支援時才啟用硬體加速。 libpopcnt.h它也是線程安全的。

我們非常重視效能，如果您在支援 AVX512 的 x86 CPU 上使用例如-march=native進行編譯，那麼所有執行時間CPUID檢查都會被刪除！

ARM SVE（可擴展向量擴充）

ARM SVE 是適用於 ARM CPU 的新向量指令集，於 2020 年首次發布。因此，ARM SVE 演算法比 ARM NEON 演算法快得多，後者向量長度僅限於 128 位元。

libpopcnt 的新 ARM SVE popcount 演算法比其 ARM NEON popcount 演算法（在 AWS Graviton3 CPU 上）快 3 倍。不幸的是，GCC 和 Clang 編譯器以及 libc 尚未很好地支援向 ARM SVE 的執行時間調度。因此，在 ARM CPU 上使用 libpopcnt 時，預設僅啟用（可移植）ARM NEON popcount 演算法。

要啟用 libpopcnt 的 ARM SVE popcount 演算法，您需要使用編譯器的 ARM SVE 選項來編譯程序，例如：

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

發展

cmake .
make -j
make test

上述命令還建立了benchmark程序，該程序對於基準測試libpopcnt.h很有用。以下是在 2023 年起的 AMD EPYC 9R14 CPU 上運行的使用範例：

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

致謝

Daniel Lemire、Nathan Kurz 和 Wojciech Mula 的論文《使用 AVX2 指令進行更快的人口計數》（2016 年 11 月 23 日）中描述了libpopcnt.h中使用的一些演算法。 libpopcnt.h中使用的 AVX2 Harley Seal popcount 演算法已從 Wojciech Muła 的 sse-popcount GitHub 儲存庫複製。