مضاعفة السرعة/القسمة على 2 للعوامات والمضاعفات(C/C++)




optimization division (6)

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

int a = 1;
int b = a<<24

ومع ذلك ، لا أستطيع ، ولا بد لي من التمسك مع الزوجي.

سؤالي هو: حيث أن هناك تمثيلًا قياسيًا للزوجي (الإشارة ، الأس ، العشري) ، هل هناك طريقة للعب مع الأس للحصول على مضاعفات / تقسيمات سريعة بقوة 2 ؟

يمكنني أن أفترض أن عدد البتات سيكون ثابتًا (سيعمل البرنامج على الآلات التي ستحصل دائمًا على مضاعفات 64 بت طويلة)

PS: ونعم ، الخوارزمية في الغالب لا هذه العمليات فقط. هذا هو عنق الزجاجة (بالفعل multithreaded).

تحرير: أو هل أنا مخطئ تماما ومعبرين ذكية بالفعل تحسين الأشياء بالنسبة لي؟

النتائج المؤقتة (مع كيو تي لقياس الوقت ، المبالغة ، لكنني لا أهتم):

#include <QtCore/QCoreApplication>
#include <QtCore/QElapsedTimer>
#include <QtCore/QDebug>

#include <iostream>
#include <math.h>

using namespace std;

int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);

while(true)
{
    QElapsedTimer timer;
    timer.start();

    int n=100000000;
    volatile double d=12.4;
    volatile double D;
    for(unsigned int i=0; i<n; ++i)
    {
        //D = d*32;      // 200 ms
        //D = d*(1<<5);  // 200 ms
        D = ldexp (d,5); // 6000 ms
    }

    qDebug() << "The operation took" << timer.elapsed() << "milliseconds";
}

return a.exec();
}

تشير التقديرات إلى أن D = d*(1<<5); و D = d*32; تشغيل في نفس الوقت (200 مللي ثانية) بينما D = ldexp (d,5); أبطأ بكثير (6000 مللي ثانية). وأنا أعلم أن هذا هو المعيار الصغير ، وفجأة ، فقد انفجرت ذاكرة الوصول العشوائي لأن Chrome طلب فجأة لحساب Pi في ظهري في كل مرة أقوم بتشغيل ldexp() ، لذلك لا يستحق هذا المعيار أي شيء. لكن سأبقيها مع ذلك.

من ناحية أخرى ، أواجه مشكلة في reinterpret_cast<uint64_t *> نظرًا لوجود انتهاك قانوني (يبدو أن الكلمة الرئيسية volatile تتداخل)


أسرع طريقة للقيام بذلك هي على الأرجح:

x *= (1 << p);

يمكن القيام بهذا النوع من الأشياء ببساطة عن طريق استدعاء تعليمة آلة لإضافة p إلى الأس. إن إخبار المترجم بدلاً من استخلاص بعض البتات بقناع والقيام بشيء ما يدويًا قد يجعل الأمور أبطأ ، وليس أسرع.

تذكر ، C / C ++ ليست لغة التجميع. إن استخدام مشغل bitshift لا يتم بالضرورة ترجمة عملية تجميع bitshift ، وليس باستخدام الضرب الذي يتم بالضرورة تجميعه إلى الضرب. هناك كل أنواع الأشياء الغريبة والرائعة التي تحدث مثل السجلات المستخدمة وما هي التعليمات التي يمكن تشغيلها في نفس الوقت والتي لست ذكيًا بما يكفي لفهمها. لكن المترجم الخاص بك ، مع العديد من سنوات الخبرة والمعرفة والكثير من القوة الحسابية ، هو أفضل بكثير في صنع هذه الأحكام.

ملاحظة: ضع في اعتبارك ، إذا كانت زوجتك في صفيف أو بنية بيانات مسطحة أخرى ، فقد يكون المترجم الخاص بك ذكيًا حقًا واستخدم SSE للعديد من 2 ، أو حتى 4 مضاعفات في نفس الوقت. ومع ذلك ، فإن القيام بالكثير من تغيير البتات ربما يؤدي إلى إرباك المترجم ومنع هذا التحسين.


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


ما العمليات الأخرى التي تتطلبها هذه الخوارزمية؟ قد تتمكن من كسر العوامات الخاصة بك إلى أزواج int (علامة / mantissa وحجم) ، قم بمعالجتك وإعادة تكوينها في النهاية.


ماذا عن ldexp ؟

أي مترجم نصف لائق سيولد رمز الأمثل على النظام الأساسي الخاص بك.

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

ومن المؤكد أنه لن يكون الإسراع في تمثيل التمثيل العائم ، إلى جانب كونه غير محمول ، أسرع (وربما يكون أبطأ).

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

[تحديث]

حسنًا ، لقد حاولت استخدام ldexp مع g + 4.5.2. cmath رأس cmath كدعوة إلى __builtin_ldexp ، وهذا بدوره ...

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

لذا ، فإن ضرب 1 << p هو أفضل رهان لك ، كما اكتشفت.


يمكن استبدال الضرب بـ 2 بإضافة: x *= 2 تساوي x += x .

يمكن استبدال القسمة على 2 بالتضاعف بمقدار 0.5. عادة ما يكون الضرب أسرع بشكل ملحوظ من التقسيم.


يمكنك أن تفترض بأمان تنسيق IEEE 754 بأمان ، ويمكن الحصول على تفاصيل gnarley جميلة (esp. عند الوصول إلى subnormals). ومع ذلك ، في الحالات الشائعة ، يجب أن يعمل هذا:

const int DOUBLE_EXP_SHIFT = 52;
const unsigned long long DOUBLE_MANT_MASK = (1ull << DOUBLE_EXP_SHIFT) - 1ull;
const unsigned long long DOUBLE_EXP_MASK = ((1ull << 63) - 1) & ~DOUBLE_MANT_MASK; 
void unsafe_shl(double* d, int shift) { 
    unsigned long long* i = (unsigned long long*)d; 
    if ((*i & DOUBLE_EXP_MASK) && ((*i & DOUBLE_EXP_MASK) != DOUBLE_EXP_MASK)) { 
        *i += (unsigned long long)shift << DOUBLE_EXP_SHIFT; 
    } else if (*i) {
        *d *= (1 << shift);
    }
} 

تعديل: بعد إجراء بعض التوقيت ، تكون هذه الطريقة أبطأ بشكل غريب من الطريقة المزدوجة في المترجم والجهاز ، حتى يتم تجريدها إلى الحد الأدنى من الشفرة المنفذة:

    double ds[0x1000];
    for (int i = 0; i != 0x1000; i++)
        ds[i] = 1.2;

    clock_t t = clock();

    for (int j = 0; j != 1000000; j++)
        for (int i = 0; i != 0x1000; i++)
#if DOUBLE_SHIFT
            ds[i] *= 1 << 4;
#else
            ((unsigned int*)&ds[i])[1] += 4 << 20;
#endif

    clock_t e = clock();

    printf("%g\n", (float)(e - t) / CLOCKS_PER_SEC);

في DOUBLE_SHIFT يكمل في 1.6 ثانية ، مع حلقة داخلية من

movupd xmm0,xmmword ptr [ecx]  
lea    ecx,[ecx+10h]  
mulpd  xmm0,xmm1  
movupd xmmword ptr [ecx-10h],xmm0

مقابل 2.4 ثانية خلاف ذلك ، مع حلقة داخلية من:

add dword ptr [ecx],400000h
lea ecx, [ecx+8]  

غير متوقع حقا!

تحرير 2: حل اللغز! أحد التغييرات لـ VC11 هو الآن أنه يقوم دائماً بتوجيه حلقات النقطة العائمة ، مما يؤدي إلى فرض / القوس: SSE2 ، على الرغم من VC10 ، حتى مع / القوس: SSE2 لا يزال أسوأ مع 3.0 ثانية مع حلقة داخلية من:

movsd xmm1,mmword ptr [esp+eax*8+38h]  
mulsd xmm1,xmm0  
movsd mmword ptr [esp+eax*8+38h],xmm1  
inc   eax

VC10 بدون / القوس: SSE2 (حتى مع / القوس: SSE) هو 5.3 ثانية ... مع 1 / 100th من التكرار !! ، الحلقة الداخلية:

fld         qword ptr [esp+eax*8+38h]  
inc         eax  
fmul        st,st(1)  
fstp        qword ptr [esp+eax*8+30h]

كنت أعرف أن المكدس X87 FP كان أوفيول ، ولكن أسوأ 500 مرة أسوأ من نوع كيندا. من المحتمل ألا تشاهد هذه الأنواع من عمليات التعجيل ، أي مصفوفة العمليات إلى SSE أو الاختراق ، لأن هذا هو أسوأ حالة تحميل في مكدس FP ، وإجراء عملية تخزين واحدة ، وتخزينها ، لكنه مثال جيد لماذا x87 ليس الطريق للذهاب لأي شيء مثالي. ذات صلة.





multiplication