بت popcount bit bufer buffer ، مع CORE 2 CPU (SSSE3)

Question

أنا أبحث عن أسرع طريقة لتشمل العازلة الكبيرة من 512 بايت أو أكثر. يمكنني ضمان أي محاذاة مطلوبة ، وحجم المخزن المؤقت هو دائمًا قوة. ثقوب عرضية.

بعض الحلول التي اعتبرتها هي:

• مجلس التعاون الخليجي __builtin_popcount
• بيتسليس popcount_24words
• مجموعة البتات ، طريق براين كيرنغان

أنا مهتم بأسرع حل ، يجب أن يعمل على مجموعة شرائح 32 بت X86 التي تنتمي إلى Core2 أو أكثر. SSE و SIMD هي ذات أهمية كبيرة. سأختبر على وحدة المعالجة المركزية الرباعية التالية:

matt@stanley:~/anacrolix/public/stackoverflow$ cat /proc/cpuinfo 
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 15
model name      : Intel(R) Core(TM)2 Quad CPU    Q6600  @ 2.40GHz
stepping        : 11
cpu MHz         : 1600.000
cache size      : 4096 KB
physical id     : 0
siblings        : 4
core id         : 0
cpu cores       : 4
apicid          : 0
initial apicid  : 0
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 10
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm constant_tsc arch_perfmon pebs bts aperfmperf pni dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm lahf_lm tpr_shadow vnmi flexpriority
bogomips        : 4800.21
clflush size    : 64
cache_alignment : 64
address sizes   : 36 bits physical, 48 bits virtual
power management:

Answer 1

أوضح أفضل وظائف C/التجميع التي وجدتها عدد السكان/الوزن الهامغ من المخازن المؤقتة الكبيرة أدناه.

أسرع وظيفة تجميع ssse3_popcount3, ، موصوفة هنا. يتطلب SSSE3, ، متوفر على Intel Core 2 وما بعده ، و AMD Chipsets تصل في عام 2011. ويستخدم سيم تعليمات إلى popcount في 16 قطعة بايت و unrolls 4 تكرارات حلقة في وقت واحد.

أسرع وظيفة C popcount_24words, ، موصوفة هنا. ويستخدم خوارزمية الترميز بت. من ملاحظة وجدت ذلك clang يمكن أن تولد في الواقع تعليمات تجميع المتجهات المناسبة ، والتي أعطت زيادة في الأداء. هذا جانبا ، الخوارزمية لا تزال سريعة للغاية.

Answer 2

شاهد نسخة 32 بت في دليل تحسين برامج AMD, ، صفحة 195 لتنفيذ واحد. يمنحك هذا رمز التجميع لـ x86 مباشرة.

انظر البديل في ستانفورد بت-تويدولينغنسخة ستانفورد تبدو أفضل واحد بالنسبة لي. يبدو من السهل للغاية أن رمز مثل X86 ASM.

أيا من هذه تستخدم تعليمات الفرع.

يمكن تعميم هذه الإصدارات على 64 بت.

مع إصدارات 32 أو 64 بت ، قد تفكر في القيام بإصدار SIMD. ستقوم SSE2 بأربعة كلمات مزدوجة أو اثنين من الكلمات الرباعية (في كلتا الحالتين 128 بت) مرة واحدة. ما تريد القيام به هو تنفيذ Popcount لـ 32 أو 64 بت في كل من السجلات 2 أو 4 المتاحة. ستنتهي بمجموعة أو 4 مجموعات من Popcounts في سجلات XMM عند الانتهاء ؛ الخطوة الأخيرة هي تخزين وإضافة تلك popcounts معًا للحصول على الإجابة النهائية. التخمين ، كنت أتوقع أن تفعل ذلك بشكل أفضل قليلاً من القيام 4 موازية 32 بت popcounts بدلا من 2 popcounts 64 بت الموازية ، لأن الأخير من المحتمل أن يأخذ 1 أو 2 تعليمات إضافية في كل تكرار ، ومن السهل إضافة 4 ، 32 بت القيم معا النهاية.

Answer 3

اذا أنت كان Popcnt:

http://kent-vandervelden.blogspot.com/2009/10/counting-bits-population-count-and.html

http://software.intel.com/sites/products/documentation/studio/composer/en-us/2011/compiler_c/intref_cls/common/intref_sse42_ata.htm

Answer 4

أود أن أقترح تنفيذ واحدة من روتين Popcnt المحسن 32 بت من فرحة المتسلل, ، ولكن افعل ذلك لعناصر عدد صحيح 4 × 32 بت في ناقل SSE. يمكنك بعد ذلك معالجة 128 بت لكل التكرار ، والتي يجب أن تمنحك حوالي 4x إنتاجية مقارنة بروتين قياسي محسّن 32 بت.