Встраивание функций

Материал из Википедии — свободной энциклопедии
Данная страница не проверялась участниками с соответствующими правами.
Перейти к навигации Перейти к поиску

В вычислительной технике встраивание функций (англ. Inlining) — способ оптимизации, при котором вызов функции заменяется непосредственно её телом. Встраивание функций аналогично по сути подстановке из макроса, но в отличие от неё не изменяет исходный код и происходит во время компиляции, в то время как макросы изменяют исходный код перед компиляцией.

Встраивание функций — это важная оптимизация, однако оказываемый эффект на производительность может быть различным[1]. Как правило, некоторое количество встраиваний помогает улучшить быстродействие при очень незначительных затратах пространства, но избыточность использования может замедлить программу из-за того, что встроенный код станет потреблять слишком много кэша инструкций, а также займёт значительное количество пространства. В книге Jones & Marlow 1999 года[2] приведён обзор академической литературы 1980-х и 1990-х годов по встраиванию функций.

Обзор

[править | править код]

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

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

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

При вызове функции управление передаётся в её тело при помощи инструкции ветвления (branch) или инструкции вызова (call). Встраивание даёт возможность избавиться от этих инструкций — в этом случае управление переходит непосредственно к коду функции.

Как правило, компиляторы используют встраивание для реализации некоторых операторов. К примеру, тела и условия циклов необходимо вычислять непосредственно при исполнении. Это достигается встраиванием кода для вычисления условий и тела циклов в место их вызовов. Встраивание операторов также помогает повысить производительность.

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

Программист может вручную встроить функцию, скопировав её код и вставив его в местах вызова. Однако же другие методы управления встраиванием (см. ниже) являются более предпочтительными, поскольку не вызывают ошибок, возникающих, если программист при исправлении ошибки во встраиваемой функции не обновит какой-то из её дубликатов.

Оказываемый эффект на производительность

[править | править код]

Основной эффект от этой оптимизации заключается в повышении быстродействия (за счёт устранения расходов на вызовы) и в увеличении расхода памяти [a] (из-за дублирования тела функции). Расход памяти за счёт дублирования кода доминирует, за исключением простых случаев[b]. Таким образом, основной эффект от встраивания заключается в ускорении кода за счёт пространства.

Однако главным преимуществом встраивания является возможность дальнейших оптимизаций и улучшения планирования за счёт увеличения размера тела функции, поскольку более крупные функции можно оптимизировать удачнее[3]. Полностью оценить влияние на производительность довольно сложно из-за большого количества эффектов на систему памяти (в первую очередь на кэш инструкций), которая оказывает значительное влияние на производительность современных процессоров. Встраивание определённых функций в зависимости от конкретной программы и кэша может как увеличивать, так и уменьшать производительность[1].

Влияние встраивания также зависит от языка программирования из-за различных уровней абстракции. В императивных языках более низкого уровня, таких как C и Fortran, можно достичь увеличения скорости на 10-20 % с незначительным влиянием на размер кода. В более абстрактных языках эффект может быть значительно выше из-за количества слоёв, которые удаляет встраивание. В качестве примера можно привести язык Self, где за счёт встраивания удавалось достичь коэффициентов ускорения от 4 до 55[4].

Непосредственная выгода от устранения вызова функции заключается в следующем:

Однако, основная выгода от встраивания заключается в предоставляемых этим возможностях дальнейшей оптимизации. Оптимизации кода из нескольких функций могут быть выполнены без необходимости межпроцедурной оптимизации (IPO): после встраивания в расширенном теле функции возможны дополнительные «внутрипроцедурные» («глобальные») оптимизации. К примеру:

  • Константа, переданная в качестве аргумента, может быть присвоена всем соответствующим параметрам. Часть функции (инвариант цикла) может быть «вынута» из цикла.
  • Задача распределения регистров может быть эффективнее решена в более крупном теле функции.
  • Высокоуровневые оптимизации, такие как Escape-анализ[англ.][5], могут выполняться в большем объёме и быть более эффективными, особенно если компилятор в процессе оптимизации полагается, в первую очередь, на внутрипроцедурный анализ.[6]

Такие оптимизации могут быть выполнены и без встраивания, но требуют значительно более сложных компиляторов и компоновщиков (в том случае, если вызов и реализация находятся в отдельных единицах компиляции).

В некоторых случаях, однако, спецификация языка позволяет программам делать дополнительные предположения относительно аргументов процедур. После встраивания эта информация может быть утеряна, делая невозможными некоторые оптимизации. Более умные компиляторы (такие, как компилятор Haskell из Глазго) будут отслеживать это, но простая реализация встраивания не будет этого учитывать.

Для системы памяти от встраивания можно выделить следующую пользу:

  • При устранении ветвления и расположении исполняемого кода близко в памяти повышается производительность кэша команд за счет улучшения ссылочной локальности[англ.] (из-за сопредельности и прямой последовательности инструкций). Эффект значительный, хотя и меньший, чем у специально предназначенных для сопредельности оптимизаций.[7]

Прямые затраты на встраивание заключаются в увеличении размера кода из-за дублирования тела функции в каждом месте вызова. Этих затрат нет только в случае очень маленьких функций, где тело функции меньше затрат на вызов (вызов, обработка аргументов и возвращаемых значений), таких как тривиальный метод доступа[англ.] (геттеры и сеттеры); или для функций, которые используются лишь единожды. Поэтому при оптимизации по размеру (часто необходимой во встраиваемых (embedded) системах), эта методика оптимизации может быть сведена к минимуму или не использоваться.

Встраивание также ухудшает производительность из-за расширения (дублирования) кода, снижающего производительность кэша инструкций.[8] Замедление заметнее всего, если до расширения рабочий объём программы (т. н. горячий раздел кода) помещается на одном уровне иерархии памяти (например, в кэше 1 уровня), а после расширения он больше не вмещается туда, что приводит к частым промахам в кэш на этом уровне. Из-за существенной разницы в производительности на разных уровнях иерархии кэша это замедляет работу кода. На высшем уровне иерархии это может привести к увеличению количества отказов страниц (page faults), катастрофическому снижению производительности из-за пробуксовок (thrashing) и даже полному отказу программы. Последнее редко встречается в обычных настольных и серверных приложениях, где размер кода невелик по отношению к доступной памяти, однако может быть проблемой для сред с ограниченными ресурсами (напр., для встроенных систем). Один из способов решения состоит в том, чтобы разделить код функции на короткий горячий (быстрый[англ.]) путь со встраиваниями и длинный холодный (медленный) путь без встраиваний.[8]

Основной вред встраивания для производительности в первую очередь актуален для больших функций, которые используются во многих местах. Однако определение точки безубыточности, за которой встраивание снижает производительность, является сложным и зависит от реальной нагрузки. Для граничных случаев это может быть вопросом ручной оптимизации или оптимизации с помощью профилирования.[9] Аналогичная проблема возникает и с другими расширяющими оптимизациями, такими как размотка цикла: несмотря на уменьшение количества инструкций, производительность может уменьшится из-за более медлительного кэша.

Сложно точно оценить влияние встраивания на производительность кэша. При небольших размерах кэша (значительно меньших, чем рабочий объём до расширения), доминирует эффект от увеличения последовательности, поэтому встраивание улучшает производительность кэша. Если размер кэша близок к рабочему объёму, то производительность кэша снижается за счёт того, что расширенный после встраивания код не вмещается в кэш. При размерах кэша, превышающих рабочий объём, встраивание оказывает незначительное влияние на производительность кэша. Кроме того, некоторые улучшения в конструкции кэша (такие, как переадресация нагрузки (load forwarding)) могут нивелировать увеличение количества промахов в кэш.[10]

Поддержка в компиляторах

[править | править код]

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

Разработчики компиляторов учитывают вышеупомянутые проблемы и реализуют в своих компиляторах различные эвристики, подбирающие функции, которые следует встраивать, чтобы в большинстве случаев это улучшало производительность, а не ухудшало её.

Реализация

[править | править код]

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

Компоновщик также может встраивать функции, исходный код которых недоступен, например, библиотечные функции (см. оптимизация во время компоновки). Среда выполнения тоже может встраивать функции во время выполнения[англ.]. Такие среды, как Java Hotspot, используют информацию динамического профилирования для принятия решения о том, какие функции следует встроить[11].

Вот простой пример встраивания, выполняемого «вручную» на уровне исходника в языке Cи: 

int pred(int x)
{
    if (x == 0)
        return 0;
    else
        return x - 1;
}

До встраивания: 

int func(int y) 
{
    return pred(y) + pred(0) + pred(y+1);
}

После встраивания: 

int func(int y) 
{
    int tmp;
    if (y   == 0) tmp  = 0; else tmp  = y - 1;       /* (1) */
    if (0   == 0) tmp += 0; else tmp += 0 - 1;       /* (2) */
    if (y+1 == 0) tmp += 0; else tmp += (y + 1) - 1; /* (3) */
    return tmp;
}

Обратите внимание, что это только пример. В реальном приложении на языке Си было бы предпочтительнее использовать функционал для встраивания, например как параметризованный макрос или встроенную функцию[англ.] чтобы компилятор сам преобразовал код таким образом. В следующем разделе перечислены способы оптимизации этого кода.

Встраивание в макросах ассемблера

[править | править код]

Макросы в языке ассемблера предлагают альтернативный подход к встраиванию, при котором последовательность инструкций генерируется при "раскрытии" некоего исходного оператора-макрокоманды (с нулём или более параметров). Один из параметров может указывать, чтобы вместо последовательности инструкций генерировалась отдельная одноразовая подпрограмма, содержащая нужную последовательность, которая вызывалась бы вместо встроенного кода. Пример: 

MOVE FROM=array1,TO=array2,INLINE=NO

Эвристики

[править | править код]

Проводились исследования целого ряда различных эвристик для встраивания. Обычно алгоритму встраивания предоставляется определённый бюджет пространства (допустимое увеличение размера программы). Алгоритм стремится встроить наиболее ценные вызовы, не превысив этого бюджета. В этом смысле многие алгоритмы встраивания обычно моделируют решение задачи о рюкзаке.[12] Чтобы решить, какие места вызовов являются наиболее ценными, встроенный алгоритм должен оценить их пользу — т. е. ожидаемое сокращение времени исполнения. Обычно для оценки пользы используются данные профилирования о частоте выполнения различных путей кода.[13]

Кроме данных профилирования, современные динамические компиляторы применяют несколько более продвинутых эвристик, таких как:[6]

  • Оценка того, какие пути исполнения приведут к наибольшему росту быстродействия (при включении дополнительных оптимизаций компилятора после встраивания) и увеличение уровня выгоды от таких путей для алгоритма.
  • Адаптивная корректировка порога безубыточности встраивания на основе размера единицы компиляции и объёма уже встроенного кода.
  • Группировка подпрограмм в кластеры и встраивание целых кластеров вместо отдельных подпрограмм. В этом случае эвристика подбирает кластеры, группируя методы, для которых встраивание правильного подмножества кластера приводит к худшей производительности, чем отсутствие встраивания.

Выгоды

[править | править код]

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

В вышеприведённом примере на языке C предостаточно возможностей для дальнейшей оптимизации. Компилятор может произвести нижеследующие действия:

  • Операторы tmp += 0 в строках, отмеченных (2) и (3), ничего не делают. Компилятор может удалить их.
  • Условие 0 == 0 всегда истинно, поэтому компилятор может заменить строку (2), на tmp += 0 (которая ничего не делает).
  • Компилятор может переписать условие y+1 == 0 на y == -1.
  • Компилятор может сократить выражение (y + 1) - 1 до просто y.
  • Выражения y и y+1 не могут быть равны нулю. Это позволяет компилятору исключить одну проверку.
  • В операторах вида if (y == 0) return y значение y известно в теле и может быть встроено.

В результате функция станет выглядеть так: 

int func(int y) 
{
    if (y == 0)
        return 0;
    if (y == -1)
        return -2;
    return 2*y - 1;
}

Ограничения

[править | править код]

Полное встраивание не всегда возможно из-за рекурсии: рекурсивное встраивание вызовов никогда не завершится. Существуют различные решения этой задачи, к примеру встраивание до определённой границы или анализ графа вызовов и разрыв циклов в определённых узлах (т. е. прекращение цикла встраиваний в некоторых местах)[14]. Аналогичная проблема возникает при раскрытии макрокоманд — рекурсивное раскрытие никогда не заканчивается. Как правило, это решается простым запретом на использование рекурсивных макросов (как в C и C++).

Сравнение с макросами

[править | править код]

Традиционно в таких языках, как Си, встраивание выполнялось на уровне исходников при помощи параметризованных макросов. Возможность использовать настоящее встраивание функций, доступное в C99, даёт ряд преимуществ:

  • В языке C макросы не выполняют проверки типов и даже не проверяют правильности формирования аргументов, в отличие от вызовов функций.
  • В макросе языка C ключевое слово return имеет другое значение, нежели в функции (это приведёт к завершению вызывающей функции, а не завершению макроса). Иными словами, макрос не может возвращать ничего, что не является результатом последнего выражения, вызванного внутри него.
  • Поскольку макросы C используют простую текстовую подстановку, это может привести к непреднамеренным побочным эффектам и неэффективности из-за пересчёта аргументов и приоритетов операций.
  • Зачастую трудно понять ошибки компилятора в макросах, потому что они относятся к вставленному коду, а не к коду, написанному программистом. Поэтому отладочная информация для встроенного кода обычно полезнее, чем информация для кода с раскрытыми макросами.
  • Многие конструкции неудобно или невозможно выразить с помощью макросов, или же необходим существенно другой синтаксис. Встроенные функции используют тот же синтаксис, что и обычные функции, и могут быть с лёгкостью объявлены встраиваемыми или не встраиваемыми.

Многие компиляторы могут также встраивать некоторые рекурсивные функции,[15] а рекурсивные макросы, как правило, запрещены.

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

Методы подбора

[править | править код]

Многие компиляторы агрессивно встраивают функции везде, где это выгодно. Хотя это и может привести к увеличению размера исполняемого файла, тем не менее такая агрессивная стратегия, как правило, окупается, поскольку объемы памяти компьютерных систем увеличиваются быстрее, чем скорость процессоров. Встраивание — это критически важная оптимизация для функциональных и объектно-ориентированных языков программирования: как правило, в них применяются функции небольшого размера, а встраивание позволяет обеспечить им достаточный контекст для того, чтобы классическая оптимизация была эффективной.

Поддержка в языках программирования

[править | править код]

Многие языки, включая Java и функциональные языки, не предоставляют языковых конструкций для встраивания функций, но их компиляторы или интерпретаторы автоматически агрессивно встраивают функции.[6] Другие языки предоставляют синтаксис для явных указаний, как правило, в виде директив компилятора (прагм).

В языке программирования Aда существует директива для встроенных функций.

В языке Common Lisp можно определять функции встраиваемыми при помощи объявления inline:[16] 

 (declaim (inline dispatch))
 (defun dispatch (x)
   (funcall
     (get (car x) 'dispatch) x))

Компилятор GHC языка Haskell автоматически пытается встраивать достаточно малые функции, однако же возможно прямо указать на необходимость встраивания при помощи директивы:[17] 

key_function :: Int -> String -> (Bool, Double)
{-# INLINE key_function #-}

C и C++

[править | править код]

В языках C и C++ есть ключевое словоinline. Оно функционирует одновременно как директива компилятора, указывая, что встраивание является «желательным», но не «обязательным», а также изменяет видимость функции и поведение компоновщика. Изменение видимости необходимо для того, чтобы функция могла быть встроена при помощи стандартного набора инструментов C: где компиляция отдельных файлов (или единиц трансляции) предшествует компоновке. Поэтому, чтобы компоновщик мог встраивать функции, они должны быть объявлены в заголовке (чтобы быть видимыми) и помечены inline (чтобы избежать двусмысленности из-за нескольких определений).

См. также

[править | править код]

Заметки

[править | править код]
  1. ↑ Расход памяти — это «количество инструкций». Это и занимаемое программой место в оперативной памяти и непосредственно размер исполняемого файла.
  2. ↑ Размер кода фактически уменьшается для функций, которые вызываются лишь раз или для очень маленьких функций, где затраты на вызов больше тела функции

Ссылки

[править | править код]
  1. ↑ 1 2 Chen, Chang, Conte, Hwu, 1993.
  2. ↑ Jones, Marlow, 1999, 8. Related work, p. 17.
  3. ↑ Chen, Chang, Conte, Hwu, 1993, 3.4 Встраивание функций (function inline expansion), стр. 14.
  4. ↑ Jones, Marlow, 1999, 8. См. также (related work) стр. 17.
  5. ↑ Хабр: Escape analysis и скаляризация: Пусть GC отдохнет
  6. ↑ 1 2 3 [1] Архивная копия от 8 ноября 2020 на Wayback Machine Прокопец и др., Оптимизирующий поэтапный алгоритм встраивания для JIT-компиляторов (An Optimization Driven Incremental Inline Substitution Algorithm for Just-In-Time Compilers), публикация CGO'19 о встройщике, используемом в компиляторе Graal для JVM
  7. ↑ Chen, Chang, Conte, Hwu, 1993, 3.4 Встраивание функций (Function inline expansion), стр. 19-20.
  8. ↑ 1 2 Бенжамин Пулен (Benjamin Poulain). Необычное ускорение: размер имеет значение (Unusual speed boost: size matters) (8 августа 2013). Дата обращения: 4 декабря 2020. Архивировано 12 ноября 2020 года.
  9. ↑ см., например, Адаптивная оптимизация системы Архивная копия от 9 августа 2011 на Wayback Machine компилятор Jikes RVM для Java.
  10. ↑ Chen, Chang, Conte, Hwu, 1993, 3.4 Встраивание функций (Function inline expansion), стр. 24-26.
  11. ↑ [2] Архивная копия от 8 ноября 2020 на Wayback Machine Система встраивания функций в JIT-компиляторе Graal для Java (Description of the inliner used in the Graal JIT compiler for Java)
  12. ↑ [3] Scheifler, анализ встраивания функций для структурного языка программирования
  13. ↑ [4] Мэтью Арнольд, Стивен Финк, Вивек Саркар и Питер Ф. Суини, Сравнительное исследование статической и профильной эвристик для встраивания (A Comparative Study of Static and Profile-based Heuristics for Inlining)
  14. ↑ Jones, Marlow, 1999, 4. Обеспечение прекращения (Ensuring Termination), стр. 6-9.
  15. ↑ и Встраивание семантики для рекурсивных подпрограмм (Inlining Semantics for Subroutines which are Recursive)", Генри Бейкер
  16. ↑ Declaration INLINE, NOTINLINE Архивная копия от 14 января 2020 на Wayback Machine в стандарте Common Lisp HyperSpec
  17. ↑ 7.13.5.1. прагма INLINE Архивная копия от 6 мая 2014 на Wayback Machine Глава 7. языковые возможности GHC (GHC Language Features)

Литература

[править | править код]
  • Chen, W. Y.; Chang, P. P.; Conte, T. M.; Hwu, W. W. (Сентябрь 1993). "Влияние раскрывающих код оптимизаций на конструкцию кэша инструкций (The effect of code expanding optimizations on instruction cache design)" (PDF). Труды IEEE о компьютерах (IEEE Transactions on Computers). 42 (9): 1045—1057. doi:10.1109/12.241594. hdl:2142/74513. {{cite journal}}: Недопустимый |ref=harv (справка)
  • Jones, Simon Peyton; Marlow, Simon (Сентябрь 1999). Секреты системы встраивания функций компилятора Haskell Глазго (Secrets of the Glasgow Haskell Compiler Inliner) (Technical report).

Внешние ссылки

[править | править код]
Источник — https://ru.wikipedia.org/wiki/Встраивание_функций