تسريع أداء حلقة أداء عملية مودولو طويلة طويلة غير موقعة
-
23-12-2019 - |
سؤال
أحتاج إلى إجراء العديد من عمليات العثور على بقايا الشعبة unsigned long long
الرقم بواسطة معامل 16 بت:
unsigned long long largeNumber;
long residues[100];
unsigned long modules[100];
intiModules(modules); //set different 16-bit values
for(int i = 0; i < 100; i++){
residues[i] = largeNumber % modules[i];
}
كيف يمكنني تسريع هذه الحلقة?
عدد التكرار ليست كبيرة (32-128) ، ولكن هذه الحلقة أداء في كثير من الأحيان حتى سرعته أمر بالغ الأهمية.
المحلول
يمكن إجراء القسمة على ثابت (ولا يوجد سوى 65536 منها) عن طريق ضرب المعاملة بالمثل متبوعا/مسبوقا ببعض الضبط الدقيق.نظرا لأن هذه الطريقة دقيقة لنطاق محدود ، يمكن للمرء استخدام بعض التقنيات لتقليل معامل 64 بت إلى قيمة أصغر بكثير (والتي لا تزال متطابقة مع القيمة الأصلية):
// pseudo code -- not c
a = 0x1234567890abcdefULL;
a = 0x1234 << 48 + 0x5678 << 32 + 0x90ab << 16 + 0xcdef;
a % N === ((0x1234 * (2^48 % N) + // === means 'is congruent'
(0x5678 * (2^32 % N)) + // ^ means exponentation
(0x90ab * (2^16 % N)) +
(0xcdef * 1)) % N;
يمكن حساب القيمة الوسيطة بمضاعفات (صغيرة) فقط ويمكن حساب الباقي النهائي (٪ن) بالضرب المتبادل.
نصائح أخرى
إذا كانت السرعة حرجة ، وفقا لهذا الإجابة عن التنبؤ فرع و هذا واحد, ، قد يكون فتح الحلقة مفيدا ، وتجنب الاختبار الناجم عن ل التعليمات ، والحد من عدد الاختبارات وتحسين "التنبؤ فرع".
الربح (أو لا شيء ، بعض المجمعين القيام بذلك الأمثل بالنسبة لك) يختلف على أساس الهندسة المعمارية / مترجم.
على جهازي ، تغيير الحلقة مع الحفاظ على عدد العمليات من
for(int i = 0; i < 500000000; i++){
residues[i % 100] = largeNumber % modules[i % 100];
}
إلى
for(int i = 0; i < 500000000; i+=5){
residues[(i+0) % 100] = largeNumber % modules[(i+0) % 100];
residues[(i+1) % 100] = largeNumber % modules[(i+1) % 100];
residues[(i+2) % 100] = largeNumber % modules[(i+2) % 100];
residues[(i+3) % 100] = largeNumber % modules[(i+3) % 100];
residues[(i+4) % 100] = largeNumber % modules[(i+4) % 100];
}
مع gcc -O2
الربح هو ~15٪.(500000000 بدلا من 100 لمراقبة فارق زمني أكثر أهمية)