تنفيذ جدول البحث القائم على وظائف علم حساب المثلثات

Question

من أجل ألعاب الفيديو انا تنفيذ في وقت فراغي ، لقد حاولت تنفيذ بلدي إصدارات sinf(), cosf () ، atan2f () ، وذلك باستخدام جداول البحث.القصد هو أن يكون تطبيقات التي هي أسرع, وإن كانت أقل دقة.

بدء تنفيذ أدناه.مهام العمل والعودة جيدة القيم التقريبية.المشكلة الوحيدة هي أنها أبطأ مما يدعو القياسية sinf(), cosf () ، atan2f() وظائف.

إذن ما الخطأ الذي فعلته ؟

// Geometry.h includes definitions of PI, TWO_PI, etc., as
// well as the prototypes for the public functions
#include "Geometry.h"

namespace {
    // Number of entries in the sin/cos lookup table
    const int SinTableCount = 512;

    // Angle covered by each table entry
    const float SinTableDelta = TWO_PI / (float)SinTableCount;

    // Lookup table for Sin() results
    float SinTable[SinTableCount];

    // This object initializes the contents of the SinTable array exactly once
    class SinTableInitializer {
    public:
        SinTableInitializer() {
            for (int i = 0; i < SinTableCount; ++i) {
                SinTable[i] = sinf((float)i * SinTableDelta);
            }
        }
    };
    static SinTableInitializer sinTableInitializer;

    // Number of entries in the atan lookup table
    const int AtanTableCount = 512;

    // Interval covered by each Atan table entry
    const float AtanTableDelta = 1.0f / (float)AtanTableCount;

    // Lookup table for Atan() results
    float AtanTable[AtanTableCount];

    // This object initializes the contents of the AtanTable array exactly once
    class AtanTableInitializer {
    public:
        AtanTableInitializer() {
            for (int i = 0; i < AtanTableCount; ++i) {
                AtanTable[i] = atanf((float)i * AtanTableDelta);
            }
        }
    };
    static AtanTableInitializer atanTableInitializer;

    // Lookup result in table.
    // Preconditions: y > 0, x > 0, y < x
    static float AtanLookup2(float y, float x) {
        assert(y > 0.0f);
        assert(x > 0.0f);
        assert(y < x);

        const float ratio = y / x;
        const int index = (int)(ratio / AtanTableDelta);
        return AtanTable[index];    
    }

}

float Sin(float angle) {
    // If angle is negative, reflect around X-axis and negate result
    bool mustNegateResult = false;
    if (angle < 0.0f) {
        mustNegateResult = true;
        angle = -angle;
    }

    // Normalize angle so that it is in the interval (0.0, PI)
    while (angle >= TWO_PI) {
        angle -= TWO_PI;
    }

    const int index = (int)(angle / SinTableDelta);
    const float result = SinTable[index];

    return mustNegateResult? (-result) : result;
}

float Cos(float angle) {
    return Sin(angle + PI_2);
}

float Atan2(float y, float x) {
    // Handle x == 0 or x == -0
    // (See atan2(3) for specification of sign-bit handling.)
    if (x == 0.0f) {
        if (y > 0.0f) {
            return PI_2;
        }
        else if (y < 0.0f) {
            return -PI_2;
        }
        else if (signbit(x)) {
            return signbit(y)? -PI : PI;
        }
        else {
            return signbit(y)? -0.0f : 0.0f;
        }
    }

    // Handle y == 0, x != 0
    if (y == 0.0f) {
        return (x > 0.0f)? 0.0f : PI;
    }

    // Handle y == x
    if (y == x) {
        return (x > 0.0f)? PI_4 : -(3.0f * PI_4);
    }

    // Handle y == -x
    if (y == -x) {
        return (x > 0.0f)? -PI_4 : (3.0f * PI_4);
    }

    // For other cases, determine quadrant and do appropriate lookup and calculation
    bool right = (x > 0.0f);
    bool top = (y > 0.0f);
    if (right && top) {
        // First quadrant
        if (y < x) {
            return AtanLookup2(y, x);
        }
        else {
            return PI_2 - AtanLookup2(x, y);
        }
    }
    else if (!right && top) {
        // Second quadrant
        const float posx = fabsf(x);
        if (y < posx) {
            return PI - AtanLookup2(y, posx);
        }
        else {
            return PI_2 + AtanLookup2(posx, y);
        }
    }
    else if (!right && !top) {
        // Third quadrant
        const float posx = fabsf(x);
        const float posy = fabsf(y);
        if (posy < posx) {
            return -PI + AtanLookup2(posy, posx);
        }
        else {
            return -PI_2 - AtanLookup2(posx, posy);
        }
    }
    else { // right && !top
        // Fourth quadrant
        const float posy = fabsf(y);
        if (posy < x) {
            return -AtanLookup2(posy, x);
        }
        else {
            return -PI_2 + AtanLookup2(x, posy);
        }
    }

    return 0.0f;
}

Answer 1

و"التحسين من السابق لأوانه هو أصل كل الشرور" - دونالد نث

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

Answer 2

وحفظ لديك شارك في المعالج ... كنت قد شهدت زيادة في سرعة لو كانت 1993 ... ولكن اليوم سوف يكافحون للتغلب intrinsics الأم.

وحاول عرض disassebly إلى sinf.

Answer 3

شخص ما لديه بالفعل قياس ذلك ، يبدو كما لو أن Trig.Math وظائف بالفعل الأمثل, و سوف يكون أسرع من أي جدول بحث كنت يمكن أن تأتي مع:

http://www.tommti-systems.de/go.html?http://www.tommti-systems.de/main-Dateien/reviews/languages/benchmarks.html

(لم تستخدم المراسي على الصفحة لذلك عليك أن انتقل حوالي 1/3 من الطريق)

Answer 4

وأنا قلق بهذا المكان:

// Normalize angle so that it is in the interval (0.0, PI)
while (angle >= TWO_PI) {
    angle -= TWO_PI;
}

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

وأيضا هل يمكن استخدام بعض أدوات التنميط مثل AQTime.

Answer 5

وظائف المدمج في وجيدا الأمثل بالفعل، لذلك سيكون صعبا للغاية لضربهم. شخصيا، أود أن ننظر في أي مكان آخر على الأماكن للحصول على الأداء.

وقال، والتحسين واحد أستطيع أن أرى في التعليمات البرمجية:

// Normalize angle so that it is in the interval (0.0, PI)
while (angle >= TWO_PI) {
    angle -= TWO_PI;
}

ويمكن أن يتم استبدال:

angle = fmod(angle, TWO_PI);