الصفحة الرئيسية>المتعلقة بالبرمجة>كود مصدر C#
تنزيل

libpopcnt

libpopcnt.h هي مكتبة C/C++ للرأس فقط لحساب عدد 1 بت (عدد البتات) في مصفوفة بأسرع ما يمكن باستخدام تعليمات وحدة المعالجة المركزية المتخصصة، مثل POPCNT، AVX2، AVX512، NEON، SVE. تم اختبار libpopcnt.h بنجاح باستخدام المترجمين الخليجيين، Clang، وMSVC.

واجهة برمجة تطبيقات 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 );

كيفية تجميع

لا يتطلب libpopcnt.h أي إشارات مترجم خاصة مثل -mavx2 ! للحصول على أفضل أداء، نوصي فقط بالتجميع مع تمكين التحسينات، على سبيل المثال -O3 أو -O2 . 

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

بنيات وحدة المعالجة المركزية

يحتوي libpopcnt.h على خوارزميات حسابية سريعة للأجهزة لبنيات وحدة المعالجة المركزية التالية:

x86 POPCNT ، AVX2 ، AVX512
x86-64 POPCNT ، AVX2 ، AVX512
ذراع NEON ، SVE
قدرة شرائية64 POPCNTD

بالنسبة لبنيات وحدة المعالجة المركزية الأخرى، يتم استخدام خوارزمية عدد صحيح سريع.

كيف يعمل

على وحدات المعالجة المركزية x86، يقوم libpopcnt.h أولاً بالاستعلام عن مجموعات التعليمات المدعومة لوحدة المعالجة المركزية لديك باستخدام تعليمات CPUID (يتم ذلك مرة واحدة فقط). بعد ذلك، يختار libpopcnt.h أسرع خوارزمية لعدد البتات التي تدعمها وحدة المعالجة المركزية لديك:

  • إذا كانت وحدة المعالجة المركزية تدعم AVX512 فسيتم استخدام خوارزمية AVX512 VPOPCNT .
  • بخلاف ذلك، إذا كانت وحدة المعالجة المركزية تدعم AVX2 فسيتم استخدام خوارزمية AVX2 Harley Seal .
  • وإلا، إذا كانت وحدة المعالجة المركزية تدعم POPCNT فسيتم استخدام خوارزمية POPCNT .
  • بالنسبة لوحدات المعالجة المركزية التي لا تحتوي على تعليمات POPCNT ، يتم استخدام خوارزمية عدد صحيح محمول.

لاحظ أن libpopcnt.h يعمل على كافة وحدات المعالجة المركزية (x86، ARM، PPC، WebAssembly، ...). إنه محمول بشكل افتراضي ولا يتم تمكين تسريع الأجهزة إلا إذا كانت وحدة المعالجة المركزية تدعمه. libpopcnt.h كما أنه آمن للخيط.

نحن نأخذ الأداء على محمل الجد، إذا قمت بالتجميع باستخدام، على سبيل المثال، -march=native على وحدة المعالجة المركزية x86 مع دعم AVX512، فستتم إزالة كافة عمليات التحقق CPUID في وقت التشغيل!

ARM SVE (امتداد متجه قابل للتحجيم)

ARM SVE عبارة عن مجموعة تعليمات متجهة جديدة لوحدات المعالجة المركزية ARM تم إصدارها لأول مرة في عام 2020. يدعم ARM SVE طول متجه متغير من 128 إلى 2048 بت. ومن ثم يمكن أن تكون خوارزميات ARM SVE أسرع بكثير من خوارزميات ARM NEON التي تقتصر على طول متجه يبلغ 128 بت.

تعد خوارزمية popcount ARM SVE الجديدة من libpopcnt أسرع بما يصل إلى 3 مرات من خوارزمية ARM NEON popcount الخاصة بها (على وحدات المعالجة المركزية AWS Graviton3). لسوء الحظ، لا يتم حتى الآن دعم إرسال وقت التشغيل إلى ARM SVE بشكل جيد من قبل المترجمين الخليجيين و Clang و libc. لذلك، بشكل افتراضي، يتم تمكين خوارزمية ARM NEON popcount (المحمولة) فقط عند استخدام libpopcnt على وحدات المعالجة المركزية ARM.

لتمكين خوارزمية 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 . فيما يلي مثال استخدام يتم تشغيله على وحدة المعالجة المركزية 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 موصوفة في الورقة البحثية "التعداد السكاني الأسرع باستخدام تعليمات AVX2" بقلم دانييل ليمير وناثان كورز وفويتشخ مولا (23 نوفمبر 2016). تم نسخ خوارزمية AVX2 Harley Seal popcount المستخدمة في libpopcnt.h من Wojciech Muła's sse-popcount GitHub repo.

يوسع
معلومات إضافية
نوصي لك
أخبار ذات صلة الكل