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 SVE
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 支持从 128 位到 2048 位的可变向量长度。因此，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 存储库复制。