Реализация триггерных функций на основе табличного поиска

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

" Преждевременная оптимизация - корень всего зла " - Дональд Кнут

В настоящее время компиляторы предоставляют очень эффективные встроенные функции для тригонометрических функций, которые получают максимальную отдачу от современных процессоров (SSE и т. д.), что объясняет, почему вы едва ли можете превзойти встроенные функции. Не теряйте слишком много времени на этих деталях, вместо этого сосредоточьтесь на реальных узких местах, которые вы можете обнаружить с помощью профилировщика.

Answer 2

Помните, что у вас есть сопроцессор ... вы бы увидели увеличение скорости, если бы это было в 1993 году ... однако сегодня вы будете бороться за то, чтобы побить нативную природу.

Попробуйте просмотреть разборчиво, чтобы 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);