libpopcnt

libpopcnt

libpopcnt.h adalah pustaka C/C++ khusus header untuk menghitung jumlah 1 bit (jumlah populasi bit) dalam array secepat mungkin menggunakan instruksi CPU khusus yaitu POPCNT, AVX2, AVX512, NEON, SVE. libpopcnt.h telah berhasil diuji menggunakan kompiler GCC, Clang dan MSVC.

API C/C++

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

Bagaimana cara mengkompilasi

libpopcnt.h tidak memerlukan flag kompiler khusus seperti -mavx2 ! Untuk mendapatkan kinerja terbaik kami hanya menyarankan untuk mengkompilasi dengan optimasi diaktifkan misalnya -O3 atau -O2 .

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

Arsitektur CPU

libpopcnt.h memiliki algoritma popcount yang dipercepat perangkat keras untuk arsitektur CPU berikut:

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

Untuk arsitektur CPU lainnya, algoritma popcount bilangan bulat cepat digunakan.

Bagaimana cara kerjanya

Pada CPU x86, libpopcnt.h terlebih dahulu menanyakan set instruksi yang didukung CPU Anda menggunakan instruksi CPUID (ini hanya dilakukan sekali). Kemudian libpopcnt.h memilih algoritma penghitungan populasi bit tercepat yang didukung oleh CPU Anda:

• Jika CPU mendukung AVX512 maka algoritma AVX512 VPOPCNT digunakan.
• Lain jika CPU mendukung AVX2 algoritma AVX2 Harley Seal digunakan.
• Lain jika CPU mendukung POPCNT algoritma POPCNT digunakan.
• Untuk CPU tanpa instruksi POPCNT algoritma integer portabel digunakan.

Perhatikan bahwa libpopcnt.h berfungsi di semua CPU (x86, ARM, PPC, WebAssembly, ...). Ini portabel secara default dan akselerasi perangkat keras hanya diaktifkan jika CPU mendukungnya. libpopcnt.h juga aman untuk thread.

Kami menangani kinerja dengan serius, jika Anda mengkompilasi menggunakan misalnya -march=native pada CPU x86 dengan dukungan AVX512 maka semua pemeriksaan CPUID runtime akan dihapus!

ARM SVE (Ekstensi Vektor yang Dapat Diskalakan)

ARM SVE adalah set instruksi vektor baru untuk CPU ARM yang pertama kali dirilis pada tahun 2020. ARM SVE mendukung panjang vektor variabel dari 128 hingga 2048 bit. Oleh karena itu algoritma ARM SVE bisa lebih cepat daripada algoritma ARM NEON yang dibatasi pada panjang vektor 128 bit.

Algoritme popcount ARM SVE baru libpopcnt 3x lebih cepat dibandingkan algoritma popcount ARM NEON (pada CPU AWS Graviton3). Sayangnya pengiriman runtime ke ARM SVE belum didukung dengan baik oleh kompiler GCC dan Clang serta libc. Oleh karena itu, secara default hanya algoritma popcount ARM NEON (portabel) yang diaktifkan saat menggunakan libpopcnt pada CPU ARM.

Untuk mengaktifkan algoritma popcount ARM SVE libpopcnt, Anda perlu mengkompilasi program Anda menggunakan opsi ARM SVE kompiler Anda, misalnya:

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

Perkembangan

cmake .
make -j
make test

Perintah di atas juga membangun program benchmark yang berguna untuk melakukan benchmarking libpopcnt.h . Di bawah ini adalah contoh penggunaan yang dijalankan pada CPU AMD EPYC 9R14 mulai tahun 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

Ucapan Terima Kasih

Beberapa algoritma yang digunakan di libpopcnt.h dijelaskan dalam makalah Penghitungan Populasi Lebih Cepat menggunakan Instruksi AVX2 oleh Daniel Lemire, Nathan Kurz dan Wojciech Mula (23 Nov 2016). Algoritme popcount AVX2 Harley Seal yang digunakan di libpopcnt.h telah disalin dari repo GitHub sse-popcount Wojciech Muła.