هل من الممكن أن نلف نسخة أسرع بكثير من SQRT

Question

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

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

يتم استخدام برنامج التحويل البرمجي MSVC ++ 2008 ، للرجوع إليه ... على الرغم من أنني أفترض أن SQRT لن يضيف الكثير من النفقات العامة.

انظر أيضًا هنا للمناقشة مماثلة على MODF وظيفة.

تحرير: للإشارة ، هذه هل طريقة واحدة تستخدم على نطاق واسع ، ولكن هل هي في الواقع أسرع بكثير؟ كم عدد الدورات SQRT على أي حال هذه الأيام؟

Answer 1

نعم ، من الممكن حتى بدون خداع:

1) دقة التضحية من أجل السرعة: خوارزمية SQRT هي تكرارية ، وإعادة تنفيذ مع عدد أقل من التكرارات.

2) جداول البحث: إما فقط لنقطة بدء التكرار ، أو جنبا إلى جنب مع الاستيفاء لتحصل على الطريق إلى هناك.

3) التخزين المؤقت: هل أنت دائمًا ستصبح نفس المجموعة المحدودة من القيم؟ إذا كان الأمر كذلك ، فإن التخزين المؤقت يمكن أن يعمل بشكل جيد. لقد وجدت هذا مفيدًا في تطبيقات الرسومات حيث يتم حساب الشيء نفسه لكثير من الأشكال بنفس الحجم ، بحيث يمكن تخزين النتائج بشكل مفيد.

Answer 2

هناك جدول مقارنة رائع هنا:http://assemblyrequired.crashworks.org/timing-square-root/

قصة قصيرة طويلة ، SSQRTs SSE2 هو حوالي 2x أسرع من FPU FSQRT ، وتكرار تقريب + هو حوالي 4x أسرع من ذلك (8x بشكل عام).

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

Answer 3

من المحتمل جدًا أن تكتسب المزيد من تحسينات السرعة عن طريق تغييرك الخوارزميات من بتغييرهم التطبيقات: حاول أن تتصل sqrt() أقل بدلا من إجراء المكالمات بشكل أسرع. (وإذا كنت تعتقد أن هذا غير ممكن - التحسينات sqrt() ذكرت ذلك فقط: تحسينات خوارزمية تستخدم لحساب الجذر التربيعي.)

نظرًا لأنه يستخدم في كثير من الأحيان ، فمن المحتمل أن تنفيذ مكتبتك القياسية sqrt() هو الأمثل تقريبا للحالة العامة. ما لم يكن لديك مجال مقيد (على سبيل المثال ، إذا كنت بحاجة إلى أقل دقة) حيث يمكن للخوارزمية أن تأخذ بعض الاختصارات ، فمن غير المرجح أن يأتي شخص ما بتنفيذ أسرع.

لاحظ أنه نظرًا لأن هذه الوظيفة تستخدم 10 ٪ من وقت التنفيذ الخاص بك ، حتى لو تمكنت من التوصل إلى تنفيذ لا يستغرق سوى 75 ٪ من وقت std::sqrt(), ، لا يزال هذا سيؤدي فقط إلى خفض وقت التنفيذ الخاص بك 2,5%. بالنسبة لمعظم التطبيقات ، لن يلاحظ المستخدمون ذلك ، إلا إذا استخدموا ساعة لقياسها.

Answer 4

ما مدى دقةك sqrt ان نكون؟ يمكنك الحصول على تقريب معقول بسرعة كبيرة: انظر Quake3 الممتازة الجذر التربيعي العكسي وظيفة للإلهام (لاحظ أن الرمز gpl'ed ، لذلك قد لا ترغب في دمجه مباشرة).

Answer 5

لا أعرف ما إذا كنت قد أصلحت هذا ، لكنني قرأت عنها من قبل ، ويبدو أن أسرع شيء يجب القيام به هو استبدال sqrt وظيفة مع نسخة تجميع مضمنة.

يمكنك رؤية وصف حمولة من البدائل هنا.

الأفضل هو هذا المقتطف من السحر:

double inline __declspec (naked) __fastcall sqrt(double n)
{
    _asm fld qword ptr [esp+4]
    _asm fsqrt
    _asm ret 8
} 

إنه حوالي 4.7x أسرع من المعيار sqrt اتصل بنفس الدقة.

Answer 6

فيما يلي طريقة سريعة مع طاولة نظرة على 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;
}