определяют, какие постоянные постоянные в каких ситуациях

Question

Идея несколько схожа с тем, что Apple has done in the OpenGL stack. Я хочу, чтобы это было немного более общим.

В принципе, я хочу иметь специализированные и оптимизированные варианты кода для некоторых конкретных случаев.

Других слов: я дан алгоритм/код для функции (пусть В = {0,1})

f : B^n -> B^m 

Теперь я специальный частный случай функции (которая предопределяет часть вход е)

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. Они уже делают такие оптимизации? В какой степени?

Есть ли хорошие недавние исследовательские работы, которые отвечают на некоторые из моих вопросов? Или, может быть, некоторые результаты, которые говорят, что это слишком сложно сделать так в общем?

Answer 1

Мне кажется, вы спрашиваете о partial evaluation.

У меня на самом деле проблема с этой концепцией, потому что она обычно формулируется в терминах, которые являются чрезмерно академичными и сложными.

Способ, которым обычно выражается, состоит в том, что у вас есть общая функция F(Islow, Ifast), имеющая аргументы, которые могут принимать разные значения в разное время. Аргументы Islow редко меняются, и аргументы Ifast могут быть разными при каждом вызове.

Тогда задача заключается в написании какого-то функция частичного оценщика G(F, Islow) -> F1(Ifast), которая принимает функцию F и Islow аргументов, и генерирует новую (простую) функцию F1 что только принимает на Ifast аргументов.

Проблема с этим: 1) кто-то должен написать общую функцию F, и 2) кто-то должен написать общий частичный оценщик G.

Что делает больше смысла для меня, чтобы написать с нуля функции H(Islow) -> F1(Ifast), то есть написать код-генератор специально для F1, а не писать две функции F и G, особенно там, где G очень трудно писать.

H обычно намного проще написать, чем F, и G не обязательно писать вообще! Функция результата F1 обычно меньше и имеет гораздо более высокую производительность, чем F, так что это беспроигрышная ситуация.

Когда люди пишут генераторы кода, это то, что они делают, и это очень эффективный метод программирования.