أين يمكنني العثور على أسرع تطبيق في العالم؟

Question

أنا أبحث عن تنفيذ سريع للغاية لـ atof() على IA32 مُحسَّن للغة US-en وASCII والتدوين غير العلمي.يسقط CRT متعدد مؤشرات الترابط في Windows بشكل بائس هنا لأنه يتحقق من التغييرات المحلية في كل استدعاء لـ isdigit().أفضل ما لدينا حاليًا مستمد من أفضل ما في تطبيق perl + tcl، ويتفوق على msvcrt.dll من حيث الحجم.أريد أن أفعل ما هو أفضل، ولكن ليس لدي أفكار.بدت تعليمات x86 ذات الصلة بـ BCD واعدة، لكنني لم أتمكن من جعلها تتفوق على كود Perl/tcl C.هل يمكن لأي SO'ers البحث عن رابط لأفضل ما هو موجود؟نرحب أيضًا بالحلول التي لا تعتمد على التجميع x86.

توضيحات بناءً على الإجابات الأولية:

تعد عدم الدقة التي تصل إلى ~2 ulp أمرًا جيدًا لهذا التطبيق.
ستصل الأرقام المطلوب تحويلها في رسائل ascii عبر الشبكة على دفعات صغيرة ويحتاج تطبيقنا إلى تحويلها في أقل زمن وصول ممكن.

Answer 1

ما هو شرط الدقة الخاص بك؟إذا كنت في حاجة إليها حقًا "صحيحة" (تحصل دائمًا على أقرب قيمة فاصلة عائمة إلى العلامة العشرية المحددة)، فمن المحتمل أن يكون من الصعب التغلب على إصدارات المكتبة القياسية (بخلاف إزالة دعم الإعدادات المحلية، وهو ما قمت به بالفعل)، نظرًا لأن وهذا يتطلب إجراء عمليات حسابية دقيقة بشكل تعسفي.إذا كنت على استعداد لتحمل خطأ أو اثنين من الأخطاء (وأكثر من ذلك بالنسبة للأخطاء دون الطبيعية)، فإن هذا النوع من النهج الذي يقترحه كروزر يمكن أن ينجح وقد يكون أسرع، لكنه بالتأكيد لن ينتج مخرجات <0.5ulp.ستحقق دقة أفضل لحساب الأجزاء الصحيحة والكسرية بشكل منفصل، وحساب الكسر في النهاية (على سبيل المثال:بالنسبة إلى 12345.6789، احسبها كـ 12345 + 6789 / 10000.0، بدلاً من 6*.1 + 7*.01 + 8*.001 + 9*0.0001) نظرًا لأن 0.1 جزء ثنائي غير منطقي وسيتراكم الخطأ بسرعة أثناء حساب 0.1^ ن.يتيح لك هذا أيضًا إجراء معظم العمليات الحسابية باستخدام الأعداد الصحيحة بدلاً من الأعداد العائمة.

لم يتم تنفيذ تعليمات BCD في الأجهزة منذ (IIRC) 286، وهي ببساطة مشفرة في الوقت الحاضر.ومن غير المرجح أن تكون عالية الأداء بشكل خاص.

Answer 2

هذا التنفيذ الذي انتهيت منه للتو من البرمجة يعمل بسرعة مضاعفة مثل "atof" المدمج على سطح المكتب.إنه يحول مدخلات الأرقام 1024*1024*39 في ثانيتين، مقارنة بـ 4 ثوانٍ مع gnu 'atof' القياسي لنظامي.(بما في ذلك وقت الإعداد والحصول على الذاكرة وكل ذلك).

تحديث:آسف لا بد لي من إلغاء مطالبتي السريعة مرتين.يكون الأمر أسرع إذا كان الشيء الذي تقوم بتحويله موجودًا بالفعل في سلسلة، ولكن إذا كنت تقوم بتمريره بسلسلة حرفية مشفرة، فسيكون الأمر مشابهًا تقريبًا لـ atof.ومع ذلك، سأترك الأمر هنا، لأنه من المحتمل مع بعض التغيير والتبديل في ملف ragel وجهاز الحالة، قد تتمكن من إنشاء تعليمات برمجية أسرع لأغراض محددة.

https://github.com/matiu2/yajp

الملفات المثيرة للاهتمام بالنسبة لك هي:

https://github.com/matiu2/yajp/blob/master/tests/test_number.cpp

https://github.com/matiu2/yajp/blob/master/number.hpp

قد تكون مهتمًا أيضًا بجهاز الحالة الذي يقوم بالتحويل:

Answer 3

لقد قمت بتنفيذ شيء قد تجده مفيدًا.بالمقارنة مع atof فهو أسرع بحوالي x5 وإذا تم استخدامه مع __forceinline حوالي X10 أسرع.شيء جميل آخر هو أنه يحتوي على نفس العمليات الحسابية تمامًا مثل تنفيذ crt.بالطبع له بعض السلبيات أيضًا:

• وهو يدعم تعويم دقة واحدة فقط،
• ولا يقوم بمسح أي قيم خاصة مثل #INF، وما إلى ذلك...

__forceinline bool float_scan(const wchar_t* wcs, float* val)
{
int hdr=0;
while (wcs[hdr]==L' ')
    hdr++;

int cur=hdr;

bool negative=false;
bool has_sign=false;

if (wcs[cur]==L'+' || wcs[cur]==L'-')
{
    if (wcs[cur]==L'-')
        negative=true;
    has_sign=true;
    cur++;
}
else
    has_sign=false;

int quot_digs=0;
int frac_digs=0;

bool full=false;

wchar_t period=0;
int binexp=0;
int decexp=0;
unsigned long value=0;

while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
{
    if (!full)
    {
        if (value>=0x19999999 && wcs[cur]-L'0'>5 || value>0x19999999)
        {
            full=true;
            decexp++;
        }
        else
            value=value*10+wcs[cur]-L'0';
    }
    else
        decexp++;

    quot_digs++;
    cur++;
}

if (wcs[cur]==L'.' || wcs[cur]==L',')
{
    period=wcs[cur];
    cur++;

    while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
    {
        if (!full)
        {
            if (value>=0x19999999 && wcs[cur]-L'0'>5 || value>0x19999999)
                full=true;
            else
            {
                decexp--;
                value=value*10+wcs[cur]-L'0';
            }
        }

        frac_digs++;
        cur++;
    }
}

if (!quot_digs && !frac_digs)
    return false;

wchar_t exp_char=0;

int decexp2=0; // explicit exponent
bool exp_negative=false;
bool has_expsign=false;
int exp_digs=0;

// even if value is 0, we still need to eat exponent chars
if (wcs[cur]==L'e' || wcs[cur]==L'E')
{
    exp_char=wcs[cur];
    cur++;

    if (wcs[cur]==L'+' || wcs[cur]==L'-')
    {
        has_expsign=true;
        if (wcs[cur]=='-')
            exp_negative=true;
        cur++;
    }

    while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
    {
        if (decexp2>=0x19999999)
            return false;
        decexp2=10*decexp2+wcs[cur]-L'0';
        exp_digs++;
        cur++;
    }

    if (exp_negative)
        decexp-=decexp2;
    else
        decexp+=decexp2;
}

// end of wcs scan, cur contains value's tail

if (value)
{
    while (value<=0x19999999)
    {
        decexp--;
        value=value*10;
    }

    if (decexp)
    {
        // ensure 1bit space for mul by something lower than 2.0
        if (value&0x80000000)
        {
            value>>=1;
            binexp++;
        }

        if (decexp>308 || decexp<-307)
            return false;

        // convert exp from 10 to 2 (using FPU)
        int E;
        double v=pow(10.0,decexp);
        double m=frexp(v,&E);
        m=2.0*m;
        E--;
        value=(unsigned long)floor(value*m);

        binexp+=E;
    }

    binexp+=23; // rebase exponent to 23bits of mantisa


    // so the value is: +/- VALUE * pow(2,BINEXP);
    // (normalize manthisa to 24bits, update exponent)
    while (value&0xFE000000)
    {
        value>>=1;
        binexp++;
    }
    if (value&0x01000000)
    {
        if (value&1)
            value++;
        value>>=1;
        binexp++;
        if (value&0x01000000)
        {
            value>>=1;
            binexp++;
        }
    }

    while (!(value&0x00800000))
    {
        value<<=1;
        binexp--;
    }

    if (binexp<-127)
    {
        // underflow
        value=0;
        binexp=-127;
    }
    else
    if (binexp>128)
        return false;

    //exclude "implicit 1"
    value&=0x007FFFFF;

    // encode exponent
    unsigned long exponent=(binexp+127)<<23;
    value |= exponent;
}

// encode sign
unsigned long sign=negative<<31;
value |= sign;

if (val)
{
    *(unsigned long*)val=value;
}

return true;
}

Answer 4

يبدو لي أنك تريد بناء (يدويًا) ما يرقى إلى مستوى آلة الحالة حيث تتعامل كل حالة مع رقم الإدخال N أو أرقام الأس؛ستكون آلة الحالة هذه على شكل شجرة (بدون حلقات!).الهدف هو إجراء عمليات حسابية للأعداد الصحيحة حيثما كان ذلك ممكنًا، و(من الواضح) تذكر متغيرات الحالة ("البادئة ناقص"، "النقطة العشرية في الموضع 3") في الحالات ضمنيًا، لتجنب التعيينات والتخزين وجلب/اختبارات هذه القيم لاحقًا .قم بتنفيذ آلة الحالة باستخدام عبارات "if" القديمة البسيطة على أحرف الإدخال فقط (بحيث تصبح شجرتك عبارة عن مجموعة من ifs المتداخلة).الوصول المضمن إلى الأحرف العازلة؛لا تريد استدعاء وظيفة ل getchar لإبطائك.

يمكن ببساطة حذف الأصفار البادئة؛قد تحتاج إلى حلقة هنا للتعامل مع التسلسلات الصفرية الطويلة بشكل يبعث على السخرية.يمكن جمع الرقم الأول غير الصفري دون صفر المجمع أو الضرب في عشرة.يمكن جمع أول 4-9 أرقام غير صفرية (للأعداد الصحيحة 16 بت أو 32 بت) بعدد صحيح يتضاعف بقيمة ثابتة عشرة (يحولها معظم المترجمين إلى عدد قليل من التحولات والإضافات).[فوق القمة:لا تتطلب الأرقام الصفرية أي عمل حتى يتم العثور على رقم غير صفري ومن ثم يلزم ضرب 10^N لـ N من الأصفار المتسلسلة؛يمكنك توصيل كل هذا بجهاز الدولة].يمكن جمع الأرقام التي تلي الأرقام 4-9 الأولى باستخدام مضاعفات 32 أو 64 بت اعتمادًا على حجم الكلمة في جهازك.نظرًا لأنك لا تهتم بالدقة، يمكنك ببساطة تجاهل الأرقام بعد أن تجمع ما يعادل 32 أو 64 بت؛أعتقد أنه يمكنك التوقف فعليًا عندما يكون لديك عدد ثابت من الأرقام غير الصفرية بناءً على ما يفعله تطبيقك بالفعل بهذه الأرقام.تؤدي العلامة العشرية الموجودة في سلسلة الأرقام إلى إنشاء فرع في شجرة آلة الحالة.يعرف هذا الفرع الموقع الضمني للنقطة وبالتالي كيفية قياسه لاحقًا بقوة العشرة بشكل مناسب.مع بذل الجهد، قد تتمكن من دمج بعض الأشجار الفرعية لآلة الحالة إذا لم يعجبك حجم هذا الرمز.

[فوق القمة:احتفظ بالأجزاء الصحيحة والكسرية كأعداد صحيحة منفصلة (صغيرة).سيتطلب هذا عملية فاصلة عائمة إضافية في النهاية للجمع بين الأجزاء الصحيحة والكسرية، ربما لا يستحق ذلك].

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

عند مواجهة "E"، اجمع الأس كعدد صحيح كما هو مذكور أعلاه؛ابحث عن القوى المحسوبة مسبقًا/المقاسة بدقة للعشرة في جدول المضاعف المحسوب مسبقًا (المقلوبات إذا كانت علامة "-" موجودة في الأس) واضرب الجزء العشري المجمع.(لا تقم أبدًا بتقسيم عائم).نظرًا لأن كل روتين جمع أسي موجود في فرع (ورقة) مختلفة من الشجرة، فيجب عليه ضبط الموقع الظاهري أو الفعلي للفاصلة العشرية عن طريق موازنة قوة المؤشر العشري.

[فوق القمة:يمكنك تجنب تكلفة ptr++ إذا كنت تعلم أن أحرف الرقم يتم تخزينها خطيًا في مخزن مؤقت ولا تتجاوز حدود المخزن المؤقت.في الحالة kth على طول فرع الشجرة، يمكنك الوصول إلى الحرف kth كـ *(start+k).يمكن للمترجم الجيد عادةً إخفاء "...+k" في الإزاحة المفهرسة في وضع العنونة.]

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

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

Answer 5

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

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

مثال:123.456

تشغيل المجموع = 0 ، أضف 1 (الآن هو 1) تشغيل إجمالي = 1 * 10 = 10 ، أضف 2 (الآن هو 12) تشغيل إجمالي = 12 * 10 = 120 ، أضف 3 (الآن 123) واجهت نقطة ، استعد ل مضاعف الجزء الكسري = 0.1 ، مضاعفة على 4 ، الحصول على 0.4 ، إضافة إلى إجمالي الجري ، يجعل 123.4 مضاعف = 0.1 / 10 = 0.01 ، اضرب في 5 ، الحصول على 0.05 ، إضافة إلى إجمالي الجري ، يجعل 123.45 متعددة = 0.01 / 10 = 0.001 ، اضرب ب 6 ، الحصول على 0.006 ، إضافة إلى إجمالي الجري ، يجعل 123.456

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

Answer 6

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

بدلاً من ذلك، قم بذلك في FPGA - هناك لوحات FPGA PCI-E يمكنك استخدامها لإنشاء معالجات مساعدة عشوائية.استخدم DMA لتوجيه FPGA إلى جزء الذاكرة الذي يحتوي على مجموعة السلاسل التي تريد تحويلها والسماح لها بالمرور عبرها تاركًا القيم المحولة خلفها.

هل نظرت إلى معالج رباعي النواة؟إن عنق الزجاجة الحقيقي في معظم هذه الحالات هو الوصول إلى الذاكرة على أي حال...

-آدم