هل من الممكن أن نلف نسخة أسرع بكثير من SQRT
-
26-09-2019 - |
سؤال
في تطبيق أنا أتنفس ، وجدت أنه في بعض السيناريوهات ، هذه الوظيفة قادرة على الحصول على أكثر من 10 ٪ من إجمالي وقت التنفيذ.
لقد رأيت نقاشًا على مر السنين من تطبيقات SQRT الأسرع باستخدام خداع النقطة العائمة المتسللة ، لكنني لا أعرف ما إذا كانت مثل هذه الأشياء عفا عليها الزمن في وحدات المعالجة المركزية الحديثة.
يتم استخدام برنامج التحويل البرمجي MSVC ++ 2008 ، للرجوع إليه ... على الرغم من أنني أفترض أن SQRT لن يضيف الكثير من النفقات العامة.
انظر أيضًا هنا للمناقشة مماثلة على MODF وظيفة.
تحرير: للإشارة ، هذه هل طريقة واحدة تستخدم على نطاق واسع ، ولكن هل هي في الواقع أسرع بكثير؟ كم عدد الدورات SQRT على أي حال هذه الأيام؟
المحلول
نعم ، من الممكن حتى بدون خداع:
1) دقة التضحية من أجل السرعة: خوارزمية SQRT هي تكرارية ، وإعادة تنفيذ مع عدد أقل من التكرارات.
2) جداول البحث: إما فقط لنقطة بدء التكرار ، أو جنبا إلى جنب مع الاستيفاء لتحصل على الطريق إلى هناك.
3) التخزين المؤقت: هل أنت دائمًا ستصبح نفس المجموعة المحدودة من القيم؟ إذا كان الأمر كذلك ، فإن التخزين المؤقت يمكن أن يعمل بشكل جيد. لقد وجدت هذا مفيدًا في تطبيقات الرسومات حيث يتم حساب الشيء نفسه لكثير من الأشكال بنفس الحجم ، بحيث يمكن تخزين النتائج بشكل مفيد.
نصائح أخرى
هناك جدول مقارنة رائع هنا:http://assemblyrequired.crashworks.org/timing-square-root/
قصة قصيرة طويلة ، SSQRTs SSE2 هو حوالي 2x أسرع من FPU FSQRT ، وتكرار تقريب + هو حوالي 4x أسرع من ذلك (8x بشكل عام).
أيضًا ، إذا كنت تحاول أخذ SQRT أحادية الدقة ، فتأكد من أن هذا ما تحصل عليه بالفعل. لقد سمعت عن مترجم واحد على الأقل من شأنه أن يحول الوسيطة العائمة إلى مزدوج ، واتصل بـ SQRT مزدوج ، ثم تحويله إلى الطوائف.
من المحتمل جدًا أن تكتسب المزيد من تحسينات السرعة عن طريق تغييرك الخوارزميات من بتغييرهم التطبيقات: حاول أن تتصل sqrt()
أقل بدلا من إجراء المكالمات بشكل أسرع. (وإذا كنت تعتقد أن هذا غير ممكن - التحسينات sqrt()
ذكرت ذلك فقط: تحسينات خوارزمية تستخدم لحساب الجذر التربيعي.)
نظرًا لأنه يستخدم في كثير من الأحيان ، فمن المحتمل أن تنفيذ مكتبتك القياسية sqrt()
هو الأمثل تقريبا للحالة العامة. ما لم يكن لديك مجال مقيد (على سبيل المثال ، إذا كنت بحاجة إلى أقل دقة) حيث يمكن للخوارزمية أن تأخذ بعض الاختصارات ، فمن غير المرجح أن يأتي شخص ما بتنفيذ أسرع.
لاحظ أنه نظرًا لأن هذه الوظيفة تستخدم 10 ٪ من وقت التنفيذ الخاص بك ، حتى لو تمكنت من التوصل إلى تنفيذ لا يستغرق سوى 75 ٪ من وقت std::sqrt()
, ، لا يزال هذا سيؤدي فقط إلى خفض وقت التنفيذ الخاص بك 2,5%. بالنسبة لمعظم التطبيقات ، لن يلاحظ المستخدمون ذلك ، إلا إذا استخدموا ساعة لقياسها.
ما مدى دقةك sqrt
ان نكون؟ يمكنك الحصول على تقريب معقول بسرعة كبيرة: انظر Quake3 الممتازة الجذر التربيعي العكسي وظيفة للإلهام (لاحظ أن الرمز gpl'ed ، لذلك قد لا ترغب في دمجه مباشرة).
لا أعرف ما إذا كنت قد أصلحت هذا ، لكنني قرأت عنها من قبل ، ويبدو أن أسرع شيء يجب القيام به هو استبدال sqrt
وظيفة مع نسخة تجميع مضمنة.
يمكنك رؤية وصف حمولة من البدائل هنا.
الأفضل هو هذا المقتطف من السحر:
double inline __declspec (naked) __fastcall sqrt(double n)
{
_asm fld qword ptr [esp+4]
_asm fsqrt
_asm ret 8
}
إنه حوالي 4.7x أسرع من المعيار sqrt
اتصل بنفس الدقة.
فيما يلي طريقة سريعة مع طاولة نظرة على 8 كيلو بايت فقط. الخطأ هو ~ 0.5 ٪ من النتيجة. يمكنك بسهولة تكبير الجدول ، وبالتالي تقليل الخطأ. يدير حوالي 5 مرات أسرع من SQRT العادية ()
// LUT for fast sqrt of floats. Table will be consist of 2 parts, half for sqrt(X) and half for sqrt(2X).
const int nBitsForSQRTprecision = 11; // Use only 11 most sagnificant bits from the 23 of float. We can use 15 bits instead. It will produce less error but take more place in a memory.
const int nUnusedBits = 23 - nBitsForSQRTprecision; // Amount of bits we will disregard
const int tableSize = (1 << (nBitsForSQRTprecision+1)); // 2^nBits*2 because we have 2 halves of the table.
static short sqrtTab[tableSize];
static unsigned char is_sqrttab_initialized = FALSE; // Once initialized will be true
// Table of precalculated sqrt() for future fast calculation. Approximates the exact with an error of about 0.5%
// Note: To access the bits of a float in C quickly we must misuse pointers.
// More info in: http://en.wikipedia.org/wiki/Single_precision
void build_fsqrt_table(void){
unsigned short i;
float f;
UINT32 *fi = (UINT32*)&f;
if (is_sqrttab_initialized)
return;
const int halfTableSize = (tableSize>>1);
for (i=0; i < halfTableSize; i++){
*fi = 0;
*fi = (i << nUnusedBits) | (127 << 23); // Build a float with the bit pattern i as mantissa, and an exponent of 0, stored as 127
// Take the square root then strip the first 'nBitsForSQRTprecision' bits of the mantissa into the table
f = sqrtf(f);
sqrtTab[i] = (short)((*fi & 0x7fffff) >> nUnusedBits);
// Repeat the process, this time with an exponent of 1, stored as 128
*fi = 0;
*fi = (i << nUnusedBits) | (128 << 23);
f = sqrtf(f);
sqrtTab[i+halfTableSize] = (short)((*fi & 0x7fffff) >> nUnusedBits);
}
is_sqrttab_initialized = TRUE;
}
// Calculation of a square root. Divide the exponent of float by 2 and sqrt() its mantissa using the precalculated table.
float fast_float_sqrt(float n){
if (n <= 0.f)
return 0.f; // On 0 or negative return 0.
UINT32 *num = (UINT32*)&n;
short e; // Exponent
e = (*num >> 23) - 127; // In 'float' the exponent is stored with 127 added.
*num &= 0x7fffff; // leave only the mantissa
// If the exponent is odd so we have to look it up in the second half of the lookup table, so we set the high bit.
const int halfTableSize = (tableSize>>1);
const int secondHalphTableIdBit = halfTableSize << nUnusedBits;
if (e & 0x01)
*num |= secondHalphTableIdBit;
e >>= 1; // Divide the exponent by two (note that in C the shift operators are sign preserving for signed operands
// Do the table lookup, based on the quaternary mantissa, then reconstruct the result back into a float
*num = ((sqrtTab[*num >> nUnusedBits]) << nUnusedBits) | ((e + 127) << 23);
return n;
}