Die Implementierung Tabelle-Lookup-Based trigonometrische Funktionen

Question

Für ein Videospiel ich in meiner Freizeit Umsetzung bin, habe ich versucht, meine eigenen Versionen von sinf () Implementierung, cosf () und atan2f (), Lookup-Tabellen. Die Absicht ist es Implementierungen zu haben, die schneller sind, wenn auch mit geringerer Genauigkeit.

Meine erste Implementierung ist unten. Die Funktionen arbeiten und bringen gute Näherungswerte. Das einzige Problem ist, dass sie langsamer als Aufruf der Standard sinf (), cosf () und atan2f () Funktionen.

Also, was mache ich falsch?

// 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

"Vorzeitige Optimierung ist die Wurzel aller Übel" - Donald Knuth

Heute Compiler bieten eine sehr effiziente intrinsics für trigonometrische Funktionen, die das Beste aus der modernen Prozessoren (SSE etc.) erhalten, was erklärt, warum man kaum die eingebauten Funktionen schlagen kann. Verlieren Sie nicht zu viel Zeit auf diesen Teilen und stattdessen konzentrieren sich auf die wirklichen Engpässe, die Sie mit einem Profiler erkennen.

Answer 2

Denken Sie daran, einen Co-Prozessor besitzen ... Sie eine Erhöhung der Geschwindigkeit hätte gesehen, wenn es 1993 sind ... aber heute kann man einheimisch intrinsics schlagen kämpfen.

Versuchen Sie, die disassebly sehen Sinf.

Answer 3

Jemand hat gebenchmarkt dies bereits, und es sieht aus, als ob die Trig.Math Funktionen bereits optimiert sind, und wird schneller als jede Lookup-Tabelle können Sie kommen mit:

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

(Sie haben Anker auf der Seite nicht verwenden, so müssen Sie über ein Drittel des Weges nach unten scrollen)

Answer 4

Ich mache mir Sorgen, von diesem Ort:

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

Aber Sie können: In zeit Meter auf alle Funktionen, schreiben spezielle Leistungstests, führten Performance-Tests, Druckreport Zeittest .. Ich denke, Sie Antwort nach diesen Tests kennen.

Auch Sie könnten einige Profilierwerkzeuge wie AQTime verwenden.

Answer 5

Die integrierten Funktionen sind bereits sehr gut optimiert, so dass es wird wirklich hart sein, sie zu schlagen. Persönlich würde ich woanders nach Orten Leistung zu gewinnen.

Das heißt, eine Optimierung kann ich in Ihrem Code sehen:

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

Kann ersetzt werden:

angle = fmod(angle, TWO_PI);