أسرع طريقة لمعرفة عدد البايتات المتساوية بين المصفوفات ذات الطول الثابت

Question

لدي صفيفتان مكونتان من 16 عنصرًا (حرفًا) أحتاج إلى "مقارنتهما" ومعرفة عدد العناصر المتساوية بين الاثنين.

سيتم استخدام هذا الروتين ملايين المرات (التشغيل المعتاد حوالي 60 أو 70 مليون مرة)، لذا أريد أن يكون سريعًا قدر الإمكان.أنا أعمل على C++ (C++Builder 2007، للسجل)

الآن لدي أمر بسيط:

matches += array1[0] == array2[0];

تكرر 16 مرة (حيث يبدو أن إنشاء ملف تعريف أسرع بنسبة 30% من القيام بذلك باستخدام حلقة for)

هل هناك أي طريقة أخرى يمكن أن تعمل بشكل أسرع؟

بعض البيانات حول البيئة والبيانات نفسها:

• أنا أستخدم C++ Builder، الذي لا يحتوي على أي تحسينات للسرعة يجب أخذها في الاعتبار.سأحاول في نهاية المطاف مع مترجم آخر، ولكن الآن أنا عالق مع هذا.
• ستكون البيانات مختلفة في معظم الأوقات.عادةً ما تكون البيانات المتساوية بنسبة 100% نادرة جدًا (ربما أقل من 1%)

Answer 1

تحديث:تم تعديل هذه الإجابة لجعل تعليقاتي تتطابق مع كود المصدر الموضح أدناه.

هناك تحسين متاح إذا كانت لديك القدرة على استخدام تعليمات SSE2 وpopcnt.

يحدث أن 16 بايت تتناسب بشكل جيد مع سجل SSE.باستخدام لغة c++ والتجميع/intrinsics، قم بتحميل الصفيفتين المكونتين من 16 بايت في سجلات xmm، ثم قم بهما.يؤدي هذا إلى إنشاء قناع نقطي يمثل حالة الصواب/الخطأ للمقارنة.يمكنك بعد ذلك استخدام تعليمة movmsk لتحميل تمثيل بت لقناع البت في سجل x86؛يصبح هذا بعد ذلك حقلًا صغيرًا يمكنك من خلاله حساب كل الأرقام 1 لتحديد عدد القيم الحقيقية لديك.يمكن أن تكون تعليمات popcnt الخاصة بالأجهزة طريقة سريعة لحساب جميع الأرقام 1 الموجودة في السجل.

وهذا يتطلب معرفة التجميع/الجوهريات وSSE على وجه الخصوص.يجب أن تكون قادرًا على العثور على موارد الويب لكليهما.

إذا قمت بتشغيل هذا الرمز على جهاز لا يدعم SSE2 أو popcnt، فيجب عليك بعد ذلك التكرار عبر المصفوفات وحساب الاختلافات باستخدام أسلوب الحلقة غير المسجلة.

حظ سعيد

يحرر:نظرًا لأنك أشرت إلى أنك لا تعرف التجميع، فإليك بعض نماذج التعليمات البرمجية لتوضيح إجابتي:

#include "stdafx.h"
#include <iostream>
#include "intrin.h"

inline unsigned cmpArray16( char (&arr1)[16], char (&arr2)[16] )
{
    __m128i first = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr1 ) );
    __m128i second = _mm_loadu_si128( reinterpret_cast<__m128i*>( &arr2 ) );

    return _mm_movemask_epi8( _mm_cmpeq_epi8( first, second ) );
}

int _tmain( int argc, _TCHAR* argv[] )
{
    unsigned count = 0;
    char    arr1[16] = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0 };
    char    arr2[16] = { 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 };

    count = __popcnt( cmpArray16( arr1, arr2 ) );

    std::cout << "The number of equivalent bytes = " << count << std::endl;

    return 0;
}

بعض الملاحظات:تستخدم هذه الوظيفة تعليمات SSE2 وتعليمات popcnt المقدمة في معالج Phenom (هذا هو الجهاز الذي أستخدمه).أعتقد أن أحدث معالجات Intel المزودة بـ SSE4 تحتوي أيضًا على popcnt.لا تتحقق هذه الوظيفة من دعم التعليمات باستخدام CPUID؛تكون الوظيفة غير محددة إذا تم استخدامها على معالج لا يحتوي على SSE2 أو popcnt (من المحتمل أن تحصل على تعليمات كود تشغيل غير صالحة).رمز الكشف هذا هو موضوع منفصل.

لم أقم بتوقيت هذا الرمز؛السبب الذي يجعلني أعتقد أنه أسرع هو أنه يقارن 16 بايت في المرة الواحدة، بدون فروع.يجب عليك تعديل هذا ليناسب بيئتك، وتوقيته بنفسك لمعرفة ما إذا كان يناسبك.لقد كتبت هذا واختبرته على VS2008 SP1.

يفضل SSE البيانات التي تتم محاذاتها على حدود طبيعية تبلغ 16 بايت؛إذا كان بإمكانك ضمان ذلك، فيجب أن تحصل على تحسينات إضافية في السرعة، ويمكنك تغيير تعليمات _mm_loadu_si128 إلى _mm_load_si128، الأمر الذي يتطلب المحاذاة.

Answer 2

المفتاح هو إجراء المقارنات باستخدام أكبر سجل تدعمه وحدة المعالجة المركزية لديك، ثم الرجوع إلى وحدات البايت إذا لزم الأمر.

يوضح الكود أدناه كيفية استخدام أعداد صحيحة ذات 4 بايت، ولكن إذا كنت تعمل على بنية SIMD (أي شريحة Intel أو AMD حديثة)، فيمكنك مقارنة كلا المصفوفتين في تعليمة واحدة قبل الرجوع إلى حلقة قائمة على الأعداد الصحيحة.يتمتع معظم المترجمين هذه الأيام بدعم جوهري لأنواع 128 بت، لذا لن يتطلبوا ASM.

(لاحظ أنه بالنسبة لمقارنات SIMD، يجب أن تكون صفائفك محاذاة 16 بايت، وقد تتطلب بعض المعالجات (مثل MIPS) أن تكون الصفائف محاذاة 4 بايت للمقارنات المستندة إلى int.

على سبيل المثال

int* array1 = (int*)byteArray[0];
int* array2 = (int*)byteArray[1];

int same = 0;

for (int i = 0; i < 4; i++)
{
  // test as an int
  if (array1[i] == array2[i])
  {
    same += 4;
  }
  else
  {
    // test individual bytes
    char* bytes1 = (char*)(array1+i);
    char* bytes2 = (char*)(array2+i);

    for (int j = 0; j < 4; j++)
    {
      same += (bytes1[j] == bytes2[j];
    }
  }
}

لا أستطيع أن أتذكر بالضبط ما الذي يدعمه مترجم MSVC لـ SIMD، ولكن يمكنك القيام بشيء مثل؛

// depending on compiler you may have to insert the words via an intrinsic
__m128 qw1 = *(__m128*)byteArray[0];
__m128 qw2 = *(__m128*)byteArray[1];

// again, depending on the compiler the comparision may have to be done via an intrinsic
if (qw1 == qw2)
{
    same = 16;
}
else
{
    // do int/byte testing
}

Answer 3

إذا كانت لديك القدرة على التحكم في موقع المصفوفات، ووضع واحدة تلو الأخرى في الذاكرة على سبيل المثال، فقد يتسبب ذلك في تحميلها إلى ذاكرة التخزين المؤقت لوحدة المعالجة المركزية عند الوصول الأول.

يعتمد ذلك على وحدة المعالجة المركزية وبنية ذاكرة التخزين المؤقت الخاصة بها وسيختلف من جهاز إلى آخر.

يمكنك أن تقرأ عن التسلسل الهرمي للذاكرة وذاكرة التخزين المؤقت هندسة الكمبيوتر هينيسي وباترسون:نهج كمي

Answer 4

إذا كنت تريد أقل مساحة على الإطلاق، فسأختار رمز التجميع.لم أفعل هذا منذ فترة ولكني أراهن أن MMX (أو على الأرجح SSE2/3) لديها تعليمات يمكن أن تمكنك من القيام بذلك بالضبط في عدد قليل جدًا من التعليمات.

Answer 5

إذا كانت المطابقات هي الحالة الشائعة، فحاول تحميل القيم بتنسيق 32 بت بدلاً من 16 حتى تتمكن من مقارنة 2 دفعة واحدة (واحتسابها كمطابقتين).

إذا كانت القيمتان 32 بت لا نفس الشيء، فسيتعين عليك اختبارها بشكل منفصل (وإخراج قيم 16 بت العلوية والسفلية).

سيكون الرمز أكثر تعقيدًا، لكن يجب أن يكون أسرع.

إذا كنت تستهدف نظامًا 64 بت، فيمكنك القيام بنفس الخدعة باستخدام 64 بت، وإذا كنت تريد حقًا تجاوز الحد الأقصى، ففكر في الانتقال إلى المجمّع واستخدام الإرشادات المتنوعة المستندة إلى المتجهات والتي ستتيح لك العمل مع 128 بت. ذات مرة.

Answer 6

ستختلف خيارات المترجم السحري بمرور الوقت بشكل كبير.على وجه الخصوص، فإن جعلها تولد توجيهات SSE من المرجح أن تحصل على تسريع كبير.

Answer 7

هل يجب أن يكون هذا نظامًا أساسيًا مستقلاً، أم أن هذا الرمز سيعمل دائمًا على نفس نوع وحدة المعالجة المركزية؟إذا قمت بتقييد نفسك بوحدات المعالجة المركزية x86 الحديثة، فقد تتمكن من استخدامها MMX التعليمات، والتي ينبغي أن تسمح لك بالعمل على مجموعة من 8 بايت في علامة الساعة الواحدة.AFAIK، gcc يسمح لك بتضمين التجميع في كود C الخاص بك، ويدعم مترجم Intel (icc) الجوهرية، وهي عبارة عن أغلفة تسمح لك باستدعاء تعليمات تجميع محددة مباشرة.قد تكون مجموعات تعليمات SIMD الأخرى، مثل SSE، مفيدة أيضًا لهذا الغرض.

Answer 8

هل هناك أي علاقة بين القيم في المصفوفات؟هل من المرجح أن تكون بعض البايتات متماثلة أكثر من غيرها؟هل يمكن أن يكون هناك بعض الترتيب الجوهري في القيم؟ثم يمكنك تحسين الحالة الأكثر احتمالا.

Answer 9

إذا قمت بشرح ما تمثله البيانات فعليًا، فقد تكون هناك طريقة مختلفة تمامًا لتمثيل البيانات في الذاكرة والتي من شأنها أن تجعل هذا النوع من مقارنة القوة الغاشمة غير ضروري.احرص على توضيح ما تمثله البيانات فعليًا؟؟

Answer 10

هل هو أسرع كبيان واحد؟

matches += (array1[0] == array2[0]) + (array1[1] == array2[1]) + ...;

Answer 11

إذا كانت كتابة ذلك 16 مرة أسرع من تكرار حلقة بسيطة، فإما أن برنامج التحويل البرمجي لديك سيئ أو أنه لم يتم تشغيل التحسين لديك.

اجابة قصيرة:لا توجد طريقة أسرع، إلا إذا قمت بإجراء عمليات متجهة على أجهزة متوازية.

Answer 12

حاول استخدام المؤشرات بدلاً من المصفوفات:

p1 = &array1[0];
p2 = &array2[0];
match += (*p1++ == *p2++);
// copy 15 times.

بالطبع يجب عليك قياس هذا مع الأساليب الأخرى لمعرفة أيهما الأسرع.

وهل أنت متأكد من أن هذا الروتين يمثل عنق الزجاجة في معالجتك؟هل تقوم بالفعل بتسريع أداء تطبيقك ككل من خلال تحسين ذلك؟مرة أخرى، القياس وحده هو الذي سيخبرنا.

Answer 13

هل هناك أي طريقة يمكنك من خلالها تعديل طريقة تخزين المصفوفات؟تعد مقارنة بايت واحد في كل مرة بطيئة للغاية مع الأخذ في الاعتبار أنك ربما تستخدم مترجمًا 32 بت.بدلاً من ذلك، إذا قمت بتخزين 16 بايت في 4 أعداد صحيحة (32 بت) أو 2 طول (64 بت)، فستحتاج فقط إلى إجراء 4 أو 2 مقارنات على التوالي.

السؤال الذي يجب أن تطرحه على نفسك هو ما هي تكلفة تخزين البيانات كمصفوفات مكونة من 4 أعداد صحيحة أو مصفوفتين طويلتين.كم مرة تحتاج للوصول إلى البيانات، وما إلى ذلك؟

Answer 14

هناك دائمًا تعليمات x86 REPNE CMPS القديمة الجيدة.

Answer 15

أحد التحسينات الممكنة الإضافية:إذا كنت تتوقع أن تكون المصفوفات متطابقة في معظم الأوقات، فقد يكون من الأسرع قليلاً إجراء الدالة memcmp() كخطوة أولى، مع تعيين "16" كإجابة إذا كان الاختبار صحيحًا.إذا كنت لا تتوقع أن تكون المصفوفات متطابقة في كثير من الأحيان، فهذا لن يؤدي إلا إلى إبطاء الأمور.