Оптимизация с использованием справочной таблицы:

Question

Этот парень: http://andrew -hoyer.com / эксперименты / ткань / создал алгоритм javascript для имитации ткани. Он указал, что код слишком медленный, поэтому ему пришлось оптимизировать квадратные корни, используя ряды Тейлора.

1. Разве нельзя оптимизировать это, предварительно рассчитав каждое возможное значение и используя таблицу поиска для его получения?

2. Часто ли это используется? Например, в 3d играх они действительно выполняют вычисления или у них уже есть таблица поиска для всех функций sin, cos, tg, sqrt и аналогичных функций?

3. Почему это не запрограммировано в процессоры?

Answer 1

Таблицы поиска в значительной степени мертвы и похоронены с современными процессорами.Особенно для таких вещей, как sqrt.Большинство FPU могут выполнять их за 9-20 циклов, и они обычно чередуются с другими вычислениями.Доступ к памяти в настоящее время часто является узким местом для процессоров с отсутствием кэша, занимающим сотни циклов.Даже кэш второго уровня может занять 20-30 циклов.Часто вычисление выполняется быстрее, чем удержание предварительно вычисленных значений.

Answer 2

Поскольку ваш средний ЦП по умолчанию определяет свои плавающие операции на основе стандарта IEEE-754, который довольно строго определяет, каким должен быть результат любой математической операции.Поисковая таблица по дизайну является лишь приблизительной и будет содержать только определенный диапазон и детализацию, которые вам необходимы для вашей конкретной задачи - что делает практически невозможным разумную реализацию в аппаратном обеспечении.Если вы хотите сохранить любое возможное значение - сделайте математику самостоятельно.

Это не означает, что мы никогда не приближаем результаты - таблицы поиска просто не являются хорошим решением для этого.Т.е. SSE имеет и sqrtss, и rsqrtss - последний возвращает приблизительное значение реального результата и работает намного быстрее.Там немного математики.

Answer 3

Использование таблицы поиска, вероятно, не так, но, возможно, микрооптимизация.Разумнее использовать алгоритм или сосредоточиться на другом коде.Может быть, это из-за крайнего срока, когда это не жестко закодировано в процессор.Что насчет логарифма?Есть ли в процессоре таблица соответствия?