В вычислительной технике встраивание функций () — способ оптимизации, при котором вызов функции заменяется непосредственно её телом. Встраивание функций аналогично по сути подстановке из макроса, но в отличие от неё не изменяет исходный код и происходит во время компиляции, в то время как макросы изменяют исходный код перед компиляцией.
Встраивание функций — это важная оптимизация, однако оказываемый эффект на производительность может быть различным. Как правило, некоторое количество встраиваний помогает улучшить быстродействие при очень незначительных затратах пространства, но избыточность использования может замедлить программу из-за того, что встроенный код станет потреблять слишком много кэша инструкций, а также займёт значительное количество пространства. В книге Jones & Marlow 1999 года приведён обзор академической литературы 1980-х и 1990-х годов по встраиванию функций.
Обзор Встраивание функций аналогично раскрытию макросов — по сути компилятор помещает новую копию функции в каждое место, где она вызывается. Код со встроенными функциями работает немного быстрее обычного, поскольку пропадают дополнительные действия по вызову функций, однако же при этом увеличивается расход памяти. Если функция встроена 10 раз, то в код будет вставлено 10 копий функции. Поэтому встраивание лучше всего подходит для небольших часто используемых функций. В C++ по умолчанию встраиваемыми являются методы, определённые в описании класса (нет необходимости использовать ключевое слово inline); в противном случае ключевое слово необходимо. Компилятор может проигнорировать попытку программиста объявить функцию встраиваемой — в основном это актуально для очень больших функций.
Встраивание функций используется для экономии процессорного времени, затрачиваемого на вызов функции. Как правило используется для часто исполняемых функций. Методика также позволяет сэкономить память для очень малых функций, кроме того она делает возможным применение иных оптимизаций.
Без указаний о встраивании компилятор зачастую сам решает, какие функции следует встроить. Программист практически не контролирует, какие функции станут встраиваемыми. Если программист сам решает вопросы встраивания функций, он может использовать знания о работе конкретного приложения для лучшей оптимизации.
При вызове функции управление передаётся в её тело при помощи инструкции ветвления (branch) или инструкции вызова (call). Встраивание даёт возможность избавиться от этих инструкций — в этом случае управление переходит непосредственно к коду функции.
Как правило, компиляторы используют встраивание для реализации некоторых операторов. К примеру, тела и условия циклов необходимо вычислять непосредственно при исполнении. Это достигается встраиванием кода для вычисления условий и тела циклов в место их вызовов. Встраивание операторов также помогает повысить производительность.
Если рассматривать это в контексте функциональных языков программирования, за встраиванием функций обычно следует преобразование бета-редукции.
Программист может вручную встроить функцию, скопировав её код и вставив его в местах вызова. Однако же другие методы управления встраиванием (см. ниже) являются более предпочтительными, поскольку не вызывают ошибок, возникающих, если программист при исправлении ошибки во встраиваемой функции не обновит какой-то из её дубликатов.
Оказываемый эффект на производительность Основной эффект от этой оптимизации заключается в повышении быстродействия (за счёт устранения расходов на вызовы) и в увеличении расхода памяти (из-за дублирования тела функции). Расход памяти за счёт дублирования кода доминирует, за исключением простых случаев. Таким образом, основной эффект от встраивания заключается в ускорении кода за счёт пространства.
Однако главным преимуществом встраивания является возможность дальнейших оптимизаций и улучшения планирования за счёт увеличения размера тела функции, поскольку более крупные функции можно оптимизировать удачнее. Полностью оценить влияние на производительность довольно сложно из-за большого количества эффектов на систему памяти (в первую очередь на кэш инструкций), которая оказывает значительное влияние на производительность современных процессоров. Встраивание определённых функций в зависимости от конкретной программы и кэша может как увеличивать, так и уменьшать производительность.
Влияние встраивания также зависит от языка программирования из-за различных уровней абстракции. В императивных языках более низкого уровня, таких как C и Fortran, можно достичь увеличения скорости на 10-20 % с незначительным влиянием на размер кода. В более абстрактных языках эффект может быть значительно выше из-за количества слоёв, которые удаляет встраивание. В качестве примера можно привести язык Self, где за счёт встраивания удавалось достичь коэффициентов ускорения от 4 до 55.
Непосредственная выгода от устранения вызова функции заключается в следующем: Устраняются инструкции, необходимые для вызова функции как в вызывающей функции, так и в вызываемом объекте. Это код для размещения аргументов в стеке или в регистрах, сам вызов функции, пролог функции, в конце тела — эпилог функции, , извлечение возвращаемого значения, удаление аргументов из стеков и (при необходимости) восстановление регистров. Упрощается задача распределения регистров, поскольку не нужно задействовать регистры для передачи аргументов. Устраняется необходимость передавать ссылки, а затем разыменовывать их при вызовах по ссылке (или при вызовах по соиспользованию).
Однако, основная выгода от встраивания заключается в предоставляемых этим возможностях дальнейшей оптимизации. Оптимизации кода из нескольких функций могут быть выполнены без необходимости межпроцедурной оптимизации (IPO): после встраивания в расширенном теле функции возможны дополнительные «внутрипроцедурные» («глобальные») оптимизации. К примеру: Константа, переданная в качестве аргумента, может быть присвоена всем соответствующим параметрам. Часть функции (инвариант цикла) может быть «вынута» из цикла. Задача распределения регистров может быть эффективнее решена в более крупном теле функции. Высокоуровневые оптимизации, такие как Хабр: Escape analysis и скаляризация: Пусть GC отдохнет, могут выполняться в большем объёме и быть более эффективными, особенно если компилятор в процессе оптимизации полагается, в первую очередь, на внутрипроцедурный анализ.
Такие оптимизации могут быть выполнены и без встраивания, но требуют значительно более сложных компиляторов и компоновщиков (в том случае, если вызов и реализация находятся в отдельных единицах компиляции).
В некоторых случаях, однако, спецификация языка позволяет программам делать дополнительные предположения относительно аргументов процедур. После встраивания эта информация может быть утеряна, делая невозможными некоторые оптимизации. Более умные компиляторы (такие, как компилятор Haskell из Глазго) будут отслеживать это, но простая реализация встраивания не будет этого учитывать.
Для системы памяти от встраивания можно выделить следующую пользу: При устранении ветвления и расположении исполняемого кода близко в памяти повышается производительность кэша команд за счет улучшения (из-за сопредельности и прямой последовательности инструкций). Эффект значительный, хотя и меньший, чем у специально предназначенных для сопредельности оптимизаций.
Прямые затраты на встраивание заключаются в увеличении размера кода из-за дублирования тела функции в каждом месте вызова. Этих затрат нет только в случае очень маленьких функций, где тело функции меньше затрат на вызов (вызов, обработка аргументов и возвращаемых значений), таких как тривиальный метод доступа (геттеры и сеттеры); или для функций, которые используются лишь единожды. Поэтому при оптимизации по размеру (часто необходимой во встраиваемых (embedded) системах), эта методика оптимизации может быть сведена к минимуму или не использоваться.
Встраивание также ухудшает производительность из-за расширения (дублирования) кода, снижающего производительность кэша инструкций. Замедление заметнее всего, если до расширения рабочий объём программы (т. н. горячий раздел кода) помещается на одном уровне иерархии памяти (например, в кэше 1 уровня), а после расширения он больше не вмещается туда, что приводит к частым промахам в кэш на этом уровне. Из-за существенной разницы в производительности на разных уровнях иерархии кэша это замедляет работу кода. На высшем уровне иерархии это может привести к увеличению количества отказов страниц (page faults), катастрофическому снижению производительности из-за пробуксовок (thrashing) и даже полному отказу программы. Последнее редко встречается в обычных настольных и серверных приложениях, где размер кода невелик по отношению к доступной памяти, однако может быть проблемой для сред с ограниченными ресурсами (напр., для встроенных систем). Один из способов решения состоит в том, чтобы разделить код функции на короткий горячий () путь со встраиваниями и длинный холодный (медленный) путь без встраиваний.
Основной вред встраивания для производительности в первую очередь актуален для больших функций, которые используются во многих местах. Однако определение точки безубыточности, за которой встраивание снижает производительность, является сложным и зависит от реальной нагрузки. Для граничных случаев это может быть вопросом ручной оптимизации или оптимизации с помощью профилирования.см., например, Адаптивная оптимизация системы компилятор Jikes RVM для Java. Аналогичная проблема возникает и с другими расширяющими оптимизациями, такими как размотка цикла: несмотря на уменьшение количества инструкций, производительность может уменьшится из-за более медлительного кэша.
Сложно точно оценить влияние встраивания на производительность кэша. При небольших размерах кэша (значительно меньших, чем рабочий объём до расширения), доминирует эффект от увеличения последовательности, поэтому встраивание улучшает производительность кэша. Если размер кэша близок к рабочему объёму, то производительность кэша снижается за счёт того, что расширенный после встраивания код не вмещается в кэш. При размерах кэша, превышающих рабочий объём, встраивание оказывает незначительное влияние на производительность кэша. Кроме того, некоторые улучшения в конструкции кэша (такие, как переадресация нагрузки (load forwarding)) могут нивелировать увеличение количества промахов в кэш.
Поддержка в компиляторах Компиляторы используют различные способы, чтобы решить, какие функции стоит встроить; среди них имеют значение как явные указания от программистов для конкретных функций, так и общие указания из параметров командной строки. Во многих компиляторах на многих языках автоматическое встраивание основывается на суждении о том, является ли оно полезным; в других случаях оно может быть задано вручную директивами компилятора или с использованием ключевого слова inline. Это ключевое слово лишь указывает на то, что функцию желательно встраивать — значимость этого указания варьируется в зависимости от языка и компилятора.
Разработчики компиляторов учитывают вышеупомянутые проблемы и реализуют в своих компиляторах различные эвристики, подбирающие функции, которые следует встраивать, чтобы в большинстве случаев это улучшало производительность, а не ухудшало её.
Реализация Реализация встраивания компилятором обычно довольно проста. В зависимости от того, проводится ли эта операция в коде на разных языках, компилятор может выполнять встраивание либо в высокоуровневой промежуточной форме (например, в абстрактное синтаксическое дерево), либо в низкоуровневую промежуточную форму. В любом случае компилятор просто вычисляет аргументы, сохраняет их в переменных, соответствующих аргументам функции, а затем вставляет тело функции в место вызова.