Идея чем-то похожа на то, что Apple сделала в стеке OpenGL . Я хочу, чтобы это было немного более общим.
По сути, я хочу иметь специализированные и оптимизированные варианты кода для некоторых конкретных случаев.
Другими словами: я дал алгоритм / код для функции (пусть B = {0,1})
f : B^n -> B^m
Теперь я особый случай с помощью функции (которая предопределяет часть ввода f )
preset : {1..n} -> {0,1,unset}
Количество предопределений (∈ {0..n}) тогда определяется как
pn := |preset⁻¹({0,1})|
Канонически, теперь мы получаем специализированную функцию
f_preset : B^(n-pn) -> B^m
Также канонически мы получаем код / алгоритм для этой специализированной функции. Естественно, код для f_preset будет несколько быстрее, чем f с pn> 0. Затем вы также можете оптимизировать этот код дальше (теперь может быть какой-то мертвый код, некоторые циклы можно распаковать сейчас, некоторые расчеты можно предварительно рассчитать и т. д.). В некоторых случаях он может иметь заметные улучшения.
Apple примерно делает это для своего стека OpenGL (из того, что я прочитал / знаю): они пытаются найти хорошую предустановку во время выполнения после того, как все настроено для переменных, которые больше не будут меняться, а затем сделать оптимизированную версию специализированного использовать эту функцию вместо исходной функции.
Изначально я думал о способе оптимизации симуляции физики какой-то собственной игры. Там у меня есть много объектов частиц и набор типов частиц (что неизвестно во время компиляции). Тип частицы - это набор атрибутов. Типы частиц являются фиксированными и постоянными после загрузки. Каждый объект частицы имеет один из этих типов частиц. Физическое моделирование для объекта частицы представляет собой очень сложный код с множеством ветвей и очень сильно зависит от типа частицы. Моя идея состояла в том, чтобы теперь иметь оптимизированную физическую функцию моделирования для каждого типа частиц.
Подумав немного об этом, я хотел пойти немного дальше:
Я хочу автоматически вычислять набор таких пресетов во время выполнения и поддерживать оптимизированный код для каждого. И я хочу автоматически добавлять или удалять пресеты, когда обстоятельства меняются.
Теперь есть несколько вопросов:
- Есть ли простой способ рассчитать хороший пресет? Как мне узнать, какие переменные являются постоянными для данной ситуации?
- Есть ли простой способ проверить, насколько хорош пресет? «Хорошо» относится к производительности полученного оптимизированного кода.
- Как сравнить два алгоритма / кода по производительности? С помощью какой-то эвристики? Или путем тестирования со случайным вводом?
- Сколько пресетов (и оптимизированных вариантов кода) должно быть для функции? Фиксированный лимит для всех функций? Или это отличается для каждой функции? Может быть, это даже зависит от текущего состояния компьютера?
- Как сохранить различные оптимизированные варианты кода? Функция-обертка вокруг f , которая автоматически выбирает наилучший оптимизированный вариант, кажется не очень приятной, поскольку, возможно, для каждого отдельного вызова потребуется не такая простая проверка. Решение этой проблемы также может быть тесно связано с вопросом о том, как найти набор / количество хороших пресетов. (В случае типа частиц оптимизированный код будет прикреплен к / сохранен вместе с типом частицы. Количество типов частиц также определяет количество предустановок.)
Для моего первоначального случая большинство из этих вопросов устарели, но сейчас мне действительно интересно, как это сделать в более общем плане. Конечно, большинство / все эти вопросы также не поддаются расчету, но мне интересно, в какой степени вы все еще можете получить хорошие результаты.
Вся эта тема также очень важна для оптимизации в JIT-компиляторах. Они уже делают такого рода оптимизацию? До какой степени?
Есть ли хорошие недавние исследовательские работы, которые отвечают на некоторые мои вопросы? Или, может быть, также некоторые результаты, которые говорят, что это слишком сложно сделать таким общим способом?