หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>ซอร์สโค้ด C#
ดาวน์โหลด

libpopcnt

libpopcnt.h เป็นไลบรารี C/C++ แบบส่วนหัวเท่านั้นสำหรับการนับจำนวน 1 บิต (จำนวนจำนวนบิต) ในอาร์เรย์โดยเร็วที่สุดโดยใช้คำสั่ง CPU เฉพาะ เช่น POPCNT, AVX2, AVX512, NEON, SVE 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

สถาปัตยกรรมซีพียู

libpopcnt.h มีอัลกอริทึม Popcount ที่เร่งด้วยฮาร์ดแวร์สำหรับสถาปัตยกรรม CPU ต่อไปนี้:

x86 POPCNT , AVX2 , AVX512
x86-64 POPCNT , AVX2 , AVX512
แขน NEON , SVE
ป.ป.ช.64 POPCNTD

สำหรับสถาปัตยกรรม CPU อื่นๆ จะใช้อัลกอริธึม popcount จำนวนเต็มเร็ว

มันทำงานอย่างไร

บนซีพียู x86 ก่อนอื่น libpopcnt.h จะสอบถามชุดคำสั่งที่รองรับของ CPU โดยใช้คำสั่ง CPUID (ทำได้เพียงครั้งเดียว) จากนั้น libpopcnt.h จะเลือกอัลกอริธึมการนับจำนวนบิตที่เร็วที่สุดที่ CPU ของคุณรองรับ:

  • หาก CPU รองรับ AVX512 จะใช้อัลกอริธึม AVX512 VPOPCNT
  • มิฉะนั้นหาก CPU รองรับ AVX2 จะใช้อัลกอริธึม AVX2 Harley Seal
  • มิฉะนั้นหาก CPU รองรับ POPCNT อัลกอริธึม POPCNT ก็จะถูกนำมาใช้
  • สำหรับ CPU ที่ไม่มีคำสั่ง POPCNT จะใช้อัลกอริธึมจำนวนเต็มแบบพกพา

โปรดทราบว่า libpopcnt.h ใช้งานได้กับ CPU ทั้งหมด (x86, ARM, PPC, WebAssembly, ... ) โดยค่าเริ่มต้นสามารถพกพาได้ และการเร่งความเร็วด้วยฮาร์ดแวร์จะเปิดใช้งานเฉพาะเมื่อ CPU รองรับเท่านั้น libpopcnt.h มันยังปลอดภัยต่อเธรดด้วย

เราให้ความสำคัญกับประสิทธิภาพอย่างจริงจัง หากคุณคอมไพล์โดยใช้ เช่น -march=native บน CPU x86 ที่รองรับ AVX512 การตรวจสอบ CPUID รันไทม์ทั้งหมดจะถูกลบออก!

ARM SVE (ส่วนขยายเวกเตอร์ที่ปรับขนาดได้)

ARM SVE คือชุดคำสั่งเวกเตอร์ใหม่สำหรับ ARM CPU ที่เปิดตัวครั้งแรกในปี 2020 ARM SVE รองรับความยาวเวกเตอร์ที่แปรผันได้ตั้งแต่ 128 ถึง 2048 บิต ดังนั้นอัลกอริธึม ARM SVE จึงเร็วกว่าอัลกอริธึม ARM NEON มากซึ่งจำกัดความยาวเวกเตอร์ไว้ที่ 128 บิต

อัลกอริธึมการนับป๊อปอัพ ARM SVE ใหม่ของ libpopcnt นั้นเร็วกว่าอัลกอริธึมการนับป๊อปอัพ ARM NEON ถึง 3 เท่า (บน CPU AWS Graviton3) น่าเสียดายที่การส่งรันไทม์ไปยัง ARM SVE ยังไม่ได้รับการสนับสนุนอย่างดีจากคอมไพเลอร์ GCC และ Clang และ libc ดังนั้นตามค่าเริ่มต้นเฉพาะอัลกอริธึม ARM NEON popcount (พกพา) เท่านั้นที่เปิดใช้งานเมื่อใช้ libpopcnt บน ARM CPU

หากต้องการเปิดใช้งานอัลกอริธึม ARM SVE popcount ของ libpopcnt คุณต้องคอมไพล์โปรแกรมของคุณโดยใช้ตัวเลือก 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 ด้านล่างนี้คือตัวอย่างการใช้งานที่ทำงานบน CPU AMD EPYC 9R14 ตั้งแต่ปี 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

รับทราบ

อัลกอริธึมบางส่วนที่ใช้ใน libpopcnt.h ได้รับการอธิบายไว้ในเอกสาร Faster Population Counts โดยใช้ AVX2 Instructions โดย Daniel Lemire, Nathan Kurz และ Wojciech Mula (23 พ.ย. 2559) อัลกอริธึม AVX2 Harley Seal popcount ที่ใช้ใน libpopcnt.h ได้รับการคัดลอกมาจาก repo sse-popcount GitHub ของ Wojciech Muła

ขยาย
ข้อมูลเพิ่มเติม
แนะนำสำหรับคุณ
ข้อมูลที่เกี่ยวข้อง ทั้งหมด