libpopcnt

libpopcnt

libpopcnt.h 、特殊な CPU 命令 (POPCNT、AVX2、AVX512、NEON、SVE) を使用して配列内の 1 ビットの数 (ビット数カウント) をできるだけ早くカウントするためのヘッダーのみの C/C++ ライブラリです。 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 アーキテクチャ用のハードウェア アクセラレーションによるポップカウント アルゴリズムが含まれています。

x86	POPCNT 、 AVX2 、 AVX512
x86-64	POPCNT 、 AVX2 、 AVX512
アーム	NEON 、 SVE
PPC64	POPCNTD

他の CPU アーキテクチャの場合は、高速整数ポップカウント アルゴリズムが使用されます。

仕組み

x86 CPU では、 libpopcnt.h最初にCPUID命令を使用して CPU のサポートされている命令セットをクエリします (これは 1 回だけ実行されます)。次に、 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 は、2020 年に初めてリリースされた ARM CPU 用の新しいベクトル命令セットです。ARM SVE は、128 ～ 2048 ビットの可変ベクトル長をサポートします。したがって、ARM SVE アルゴリズムは、ベクトル長が 128 ビットに制限されている ARM NEON アルゴリズムよりもはるかに高速になります。

libpopcnt の新しい ARM SVE ポップカウント アルゴリズムは、ARM NEON ポップカウント アルゴリズム (AWS Graviton3 CPU 上) より最大 3 倍高速です。残念ながら、ARM SVE へのランタイム ディスパッチは、GCC、Clang コンパイラ、および libc ではまだ十分にサポートされていません。したがって、ARM CPU で libpopcnt を使用する場合、デフォルトでは (ポータブル) ARM NEON ポップカウント アルゴリズムのみが有効になります。

libpopcnt の ARM SVE ポップカウント アルゴリズムを有効にするには、コンパイラの ARM SVE オプションを使用してプログラムをコンパイルする必要があります。例:

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

発達

cmake .
make -j
make test

上記のコマンドは、 libpopcnt.hベンチマークに役立つbenchmarkプログラムも構築します。以下は、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

謝辞

libpopcnt.hで使用されるアルゴリズムの一部は、Daniel Lemire、Nathan Kurz、Wojciech Mula による論文「Faster Population Counts using AVX2 命令」 (2016 年 11 月 23 日) で説明されています。 libpopcnt.hで使用される AVX2 Harley Seal ポップカウント アルゴリズムは、Wojciech Muła の sse-popcount GitHub リポジトリからコピーされました。