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가 지원하는 명령어 세트를 쿼리합니다(이 작업은 한 번만 수행됨). 그런 다음 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 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

위의 명령은 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(2016년 11월 23일)의 AVX2 지침을 사용한 Faster Population Counts 논문에 설명되어 있습니다. libpopcnt.h 에 사용된 AVX2 Harley Seal popcount 알고리즘은 Wojciech Muła의 sse-popcount GitHub 저장소에서 복사되었습니다.