Каковы хорошие эвристики для встраивания функций?

Question

Учитывая, что вы пытаетесь оптимизировать исключительно для повышения скорости, каковы хорошие эвристические методы для принятия решения о том, встроить функцию или нет?Очевидно, что размер кода должен быть важен, но есть ли какие-либо другие факторы, обычно используемые, когда (скажем) gcc или icc определяют, следует ли встроить вызов функции?Была ли проведена какая-либо значительная научная работа в этой области?

Answer 1

В Википедии есть a немногие параграфы об этом, с некоторыми ссылками внизу:

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

Языки с JIT-компиляторами и загрузкой классов среды выполнения имеют другие компромиссы, поскольку виртуальные методы неизвестны статически, но JIT может собирать информацию о профилировании среды выполнения, такую как частота вызова метода:

• Проектирование, реализация и оценка оптимизаций в компиляторе "Точно в срок" (для Java) рассказывает о встраивании статических методов и динамически загружаемых классов и его улучшении в производительности.

• Практикующий ДЗЮДО:Java В условиях динамической оптимизации утверждает, что их "политика встраивания основана на размере кода и информации о профилировании.Если частота выполнения записи метода ниже определенного порога, то метод не включается, поскольку он рассматривается как холодный метод.Чтобы избежать взрыва кода, мы не встраиваем метод с размером байт-кода более 25 байт....Чтобы избежать встраивания по цепочке глубоких вызовов, встраивание прекращается, когда накопленный размер встроенного байт-кода по цепочке вызовов превышает 40 байт ". Хотя у них есть информация о профилировании среды выполнения (частота вызова метода), они по-прежнему стараются избегать встраивания больших функций или цепочек функций, чтобы предотвратить раздувание.

Поиск в Google Scholar раскрывается ряд работ, таких как

• Влияние оптимизации, расширяющей код, на проектирование кэша команд
• Встраивание функций в соответствии с ограничениями по размеру кода для встроенных процессоров

Поиск в Google Books раскрывает довольно много книг со статьями или главами о внедрении функций в различных контекстах.

• Руководство по проектированию компилятора:Оптимизация и генерация машинного кода содержит главу о статистических методах и методах машинного обучения при разработке компиляторов, с эвристикой для установки различных параметров и профилирования результатов.Эта глава ссылается на статью Васвани и др. Эмпирические модели, чувствительные к микроархитектуре, для оптимизации компилятора где они предлагают "использование эмпирического моделирования методы построения чувствительных к микроархитектуре моделей для оптимизации компилятора".

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

Answer 2

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

Единственное преимущество, которое я вижу в вызове функции вместо ее встраивания, связано с размером.Я предполагаю, что встраивание функции с последующим развертыванием цикла может привести к значительному увеличению размера.

Answer 3

насколько я видел, размер функции — единственный фактор, используемый компиляторами для определения встроенных функций.Однако, если вы выполняете оптимизацию на основе профиля (PGO), я считаю, что компилятор может использовать другие переменные, такие как количество вызовов/время установки вызова.

Answer 4

В .NET это в основном зависит от размера.Измерьте размер родительской функции и дочерней функции в скомпилированных байтах.Затем измерьте размер объединенной функции.Если объединенная функция меньше, то встраивание — хорошая идея.

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