Это начало серии статей про разработку. Основной темой будет разработка игр и всё с этим связанное: программирование, игровые движки, технологии, алгоритмы, оптимизация и многое другое.
В этот раз рассмотрим один из популярных способов оптимизации - таблицы поиска.
Что за таблицы такие?
Таблицы поиска (Look-Up Tables, LUT) - это заранее вычисленные значения сохранённые в виде массива. В основном заполняются уже на этапе компиляции, можно конечно посчитать и при старте программы, но таким образом можем замедлить запуск программы , а это иногда бывает важно.
Отсюда и основное применение - это оптимизация производительности, так как мы заранее можем произвести довольно ресурсозатратные вычисления, а во время выполнения, для получения значений, напрямую обращаться к памяти.
Пример реализации
Разберём на простом примере генерации таблицы синусов во время компиляции. Пример скучный, но зато всем понятный😊
Для того чтобы можно было вычислить синус во время компиляции, необходимо сделать функцию с спецификатором consteval. Это позволит нам выполнять вычисления во время компиляции.
Осталось только заполнить таблицу значениями и сохранить в переменную.
Функцию generate_sin_table тоже необходимо пометить consteval.
Где они применяются?
Использование таких таблиц особенно эффективно в случаях:
- Когда вычисление значения требует значительных ресурсов
- При частом доступе к одним и тем же значениям
- В системах реального времени, где важна предсказуемость времени выполнения
- В встраиваемых системах с ограниченными вычислительными ресурсами
Заключение
Генерация таблиц поиска во время компиляции - это достаточно полезный инструмент оптимизации, который позволяет перенести сложные вычисления со времени выполнения на время компиляции.
Основным преимуществом конечно является производительность, так как нет накладных расходов на вычисление значений во время выполнения. Но также можно к плюсам добавить детерминированность полученных значений, что может быть очень полезно при отладке приложения.
Конечно есть и минусы. Основной из них это то, что нам всё таки приходится хранить значения в памяти и если их много это может быть довольно накладно, так что приходится ограничивать количество вычисленных значений. Как компромисс можно вычислять только часто используемые значения (осталось только понять, какие используются чаще😋, но для этого есть уже другие подходы)
Жду ваших вопросов и предложений по статье в комментариях😁