Implementazione di funzioni Trig basate su ricerca tabella

Question

Per un videogioco che sto implementando nel mio tempo libero, ho provato ad implementare le mie versioni di sinf (), cosf () e atan2f (), usando le tabelle di ricerca. L'intenzione è quella di avere implementazioni più veloci, anche se con meno precisione.

La mia implementazione iniziale è di seguito. Le funzioni funzionano e restituiscono buoni valori approssimativi. L'unico problema è che sono più lenti rispetto a chiamare le funzioni standard sinf (), cosf () e atan2f ().

Quindi, cosa sto facendo di sbagliato?

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

" L'ottimizzazione prematura è la radice di tutti i mali " - Donald Knuth

Oggigiorno i compilatori forniscono intrinsechi molto efficienti per le funzioni trigonometriche che ottengono il meglio dai moderni processori (SSE ecc.), il che spiega perché difficilmente si possono battere le funzioni integrate. Non perdere troppo tempo da queste parti e concentrati invece sui veri colli di bottiglia che puoi individuare con un profiler.

Answer 2

Ricorda che hai un coprocessore ... avresti visto un aumento della velocità se fosse il 1993 ... tuttavia oggi farai fatica a battere i intrinseci nativi.

Prova a visualizzare il disassolutamente sinf.

Answer 3

Qualcuno ha già fatto un benchmark di questo, e sembra che le funzioni Trig.Math siano già ottimizzate e saranno più veloci di qualsiasi tabella di ricerca che puoi trovare:

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

(Non hanno usato le ancore sulla pagina, quindi è necessario scorrere circa 1/3 della discesa)

Answer 4

Sono preoccupato per questo posto:

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

Ma puoi: Aggiungi misuratori di tempo a tutte le funzioni, scrivi test di prestazioni speciali, esegui test di prestazioni, stampa un rapporto di test di tempo .. Penso che saprai rispondere dopo questi test.

Inoltre potresti usare alcuni strumenti di profilazione come AQTime.

Answer 5

Le funzioni integrate sono già ottimizzate molto bene, quindi sarà DAVVERO dura da battere. Personalmente, cercherei altrove luoghi in cui ottenere prestazioni.

Detto questo, un'ottimizzazione che posso vedere nel tuo codice:

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

Potrebbe essere sostituito con:

angle = fmod(angle, TWO_PI);