В вычислительной технике встроенное расширение или встраивание — это оптимизация вручную или компилятором , при которой место вызова функции заменяется телом вызываемой функции. Встроенное расширение похоже на расширение макроса , но происходит во время компиляции без изменения исходного кода (текста), тогда как расширение макроса происходит до компиляции и приводит к получению другого текста, который затем обрабатывается компилятором.
Встраивание — важная оптимизация, но оно оказывает сложное влияние на производительность. [1] Как правило , некоторое встраивание улучшает скорость при очень небольших затратах места, но избыточное встраивание снижает скорость из-за того, что встроенный код потребляет слишком много кэша инструкций , а также требует значительного пространства. Обзор скромной научной литературы по инлайнингу 1980-х и 1990-х годов дан в Peyton Jones & Marlow 1999. [2]
Встроенное расширение похоже на расширение макроса, поскольку компилятор помещает новую копию функции в каждое место ее вызова. Встроенные функции выполняются немного быстрее, чем обычные функции, поскольку сохраняются накладные расходы на вызов функций, однако при этом возникает нехватка памяти. Если функция вставлена 10 раз, в код будет вставлено 10 копий функции. Следовательно, встраивание лучше всего подходит для небольших функций, которые вызываются часто. В C++ функции-члены класса, если они определены в определении класса, встроены по умолчанию (нет необходимости использовать ключевое слово inline ); в противном случае необходимо ключевое слово. Компилятор может игнорировать попытку программиста встроить функцию, особенно если она очень велика.
Встроенное расширение используется для устранения временных затрат (избыточного времени) при вызове функции. Обычно он используется для функций, которые выполняются часто. Он также дает преимущество в пространстве для очень маленьких функций и позволяет использовать преобразование для других оптимизаций .
Без встроенных функций компилятор решает, какие функции встроить. Программист практически не контролирует, какие функции встроены, а какие нет. Предоставление такой степени контроля программисту позволяет использовать знания конкретного приложения при выборе функций для встраивания.
Обычно при вызове функции управление передается ее определению с помощью инструкции ветвления или вызова. При встраивании управление передается непосредственно в код функции без инструкций ветвления или вызова.
Компиляторы обычно реализуют операторы со встраиванием. Условия цикла и тела цикла нуждаются в ленивой оценке . Это свойство реализуется, когда код для вычисления условий цикла и тела цикла встроен. Соображения производительности — еще одна причина использования встроенных операторов.
В контексте функциональных языков программирования за встроенным расширением обычно следует преобразование бета-сокращения .
Программист может встроить функцию вручную посредством копирования и вставки как однократную операцию над исходным кодом . Однако другие методы управления встраиванием (см. ниже) предпочтительнее, поскольку они не вызывают ошибок, возникающих, когда программист пропускает (возможно, модифицированную) дублированную версию исходного тела функции при исправлении ошибки во встроенной функции.
Прямым эффектом этой оптимизации является улучшение производительности по времени (за счет устранения накладных расходов на вызовы) за счет ухудшения использования пространства [a] (из-за дублирования тела функции). Расширение кода за счет дублирования тела функции доминирует, за исключением простых случаев, [b] и, таким образом, прямым эффектом встроенного расширения является улучшение времени за счет пространства.
Однако основным преимуществом встроенного расширения является возможность дальнейшей оптимизации и улучшения планирования за счет увеличения размера тела функции, поскольку лучшая оптимизация возможна для более крупных функций. [3] Окончательное влияние встроенного расширения на скорость сложно из-за множественного воздействия на производительность системы памяти (в первую очередь кэша инструкций ), которая доминирует в производительности современных процессоров: в зависимости от конкретной программы и кэша встраивание определенных функций может увеличиться. или снизить производительность. [1]
Влияние встраивания зависит от языка программирования и программы из-за разной степени абстракции. В императивных языках более низкого уровня, таких как C и Fortran, это обычно дает прирост скорости на 10–20% с незначительным влиянием на размер кода, тогда как в более абстрактных языках это может быть значительно более важным из-за удаления количества слоев при встраивании. Крайним примером является Self , где один компилятор увидел коэффициент улучшения от 4 до 55 за счет встраивания. [2]
Прямые преимущества устранения вызова функции:
Однако основным преимуществом встраивания является возможность дальнейшей оптимизации. Оптимизации, пересекающие границы функций, могут выполняться без необходимости межпроцедурной оптимизации (IPO): после выполнения встраивания становятся возможными дополнительные внутрипроцедурные оптимизации («глобальные оптимизации») в расширенном теле функции. Например:
Это можно сделать без встраивания, но для этого потребуется значительно более сложный компилятор и компоновщик (в случае, если вызывающий и вызываемый объекты находятся в разных модулях компиляции).
И наоборот, в некоторых случаях спецификация языка может позволить программе делать дополнительные предположения об аргументах процедур, которые она больше не может делать после встраивания процедуры, что предотвращает некоторые оптимизации. Более умные компиляторы (такие как Glasgow Haskell Compiler ) отслеживают это, но при наивном встраивании эта информация теряется.
Еще одним преимуществом встраивания для системы памяти является:
Прямая стоимость встраивания — увеличение размера кода из-за дублирования тела функции на каждом месте вызова. Однако это происходит не всегда, а именно в случае очень коротких функций, где тело функции меньше размера вызова функции (в вызывающей стороне, включая обработку аргументов и возвращаемых значений), таких как тривиальные методы доступа или мутаторы. методы (геттеры и сеттеры); или для функции, которая используется только в одном месте, и в этом случае она не дублируется. Таким образом, встраивание может быть сведено к минимуму или устранено при оптимизации размера кода, как это часто бывает во встроенных системах .
Встраивание также снижает производительность, поскольку расширение кода (из-за дублирования) ухудшает производительность кэша инструкций. [6] Это наиболее значимо, если до расширения рабочий набор программы (или горячий участок кода) умещался на одном уровне иерархии памяти (например, кэш L1 ), а после расширения уже не помещается, что приводит к частым промахам в кэше на этом уровне. Из-за значительной разницы в производительности на разных уровнях иерархии это значительно снижает производительность. На самом высоком уровне это может привести к увеличению количества ошибок страниц , катастрофическому снижению производительности из-за сбоя или вообще к невозможности запуска программы. Последнее редко встречается в обычных настольных и серверных приложениях, где размер кода невелик по сравнению с доступной памятью, но может быть проблемой для сред с ограниченными ресурсами, таких как встроенные системы. Один из способов смягчить эту проблему — разделить функции на меньший «горячий» встроенный путь ( быстрый путь ) и больший «холодный» невстроенный путь (медленный путь). [6]
Встраивание, снижающее производительность, в первую очередь является проблемой для больших функций, которые используются во многих местах, но точку безубыточности, за которой встраивание снижает производительность, трудно определить, и она обычно зависит от точной нагрузки, поэтому ее можно оптимизировать вручную или профилировать. -управляемая оптимизация . [7] Это аналогичная проблема с другими оптимизациями расширения кода, такими как развертывание цикла , что также уменьшает количество обрабатываемых инструкций, но может снизить производительность из-за снижения производительности кэша.
Точный эффект встраивания на производительность кэша сложен. Для небольших размеров кэша (намного меньших, чем рабочий набор до расширения) преобладает повышенная последовательность, а встраивание повышает производительность кэша. Для размеров кэша, близких к рабочему набору, когда встраивание расширяет рабочий набор, так что он больше не помещается в кэш, это доминирует, и производительность кэша снижается. Для размеров кэша, превышающих рабочий набор, встраивание оказывает незначительное влияние на производительность кэша. Кроме того, изменения в конструкции кэша, такие как перенаправление нагрузки, могут компенсировать увеличение количества промахов в кэше. [8]
Компиляторы используют различные механизмы, чтобы решить, какие вызовы функций следует встроить; они могут включать ручные подсказки программистов для конкретных функций, а также общий контроль с помощью параметров командной строки . Встраивание выполняется автоматически многими компиляторами на многих языках на основе оценки того, полезно ли встраивание, тогда как в других случаях его можно указать вручную с помощью директив компилятора , обычно с использованием ключевого слова или директивы компилятора с именем inline. Обычно это лишь намекает на то, что встраивание желательно, а не требует, причем сила подсказки зависит от языка и компилятора.
Обычно разработчики компиляторов учитывают вышеупомянутые проблемы с производительностью и включают в свои компиляторы эвристику , которая выбирает, какие функции встроить, чтобы в большинстве случаев повысить производительность, а не ухудшить ее.
После того, как компилятор решил встроить определенную функцию, выполнить саму операцию встраивания обычно не составляет труда. В зависимости от того, встраивает ли компилятор функции в код на разных языках, компилятор может выполнять встраивание либо в промежуточное представление высокого уровня (например, абстрактные синтаксические деревья ), либо в промежуточное представление низкого уровня. В любом случае компилятор просто вычисляет аргументы , сохраняет их в переменных, соответствующих аргументам функции, а затем вставляет тело функции в место вызова.
Линкеры также могут выполнять встраивание функций. Когда компоновщик встраивает функции, он может встраивать функции, исходный код которых недоступен, например библиотечные функции (см. Оптимизация времени компоновки ). Система времени выполнения также может функционировать в режиме реального времени. Встраивание во время выполнения может использовать информацию динамического профилирования для принятия более эффективных решений о том, какие функции встраивать, как в компиляторе Java Hotspot . [9]
Вот простой пример встроенного расширения, выполняемого «вручную» на уровне исходного кода на языке программирования C :
int pred ( int x ) { if ( x == 0 ) return 0 ; иначе вернуть x - 1 ; } Перед встраиванием:
int func ( int y ) { return pred ( y ) + pred ( 0 ) + pred ( y + 1 ); } После встраивания:
int func ( int y ) { int tmp ; если ( y == 0 ) tmp = 0 ; иначе tmp = y - 1 ; /* (1) */ if ( 0 == 0 ) tmp += 0 ; иначе tmp += 0 - 1 ; /* (2) */ if ( y + 1 == 0 ) tmp += 0 ; иначе tmp += ( y + 1 ) - 1 ; /* (3) */ return tmp ; } Обратите внимание, что это только пример. В реальном приложении C было бы предпочтительнее использовать встроенные функции языка, такие как параметризованные макросы или встроенные функции, чтобы сообщить компилятору о необходимости преобразования кода таким образом. В следующем разделе перечислены способы оптимизации этого кода.
Макросы ассемблера предоставляют альтернативный подход к встраиванию, при котором последовательность инструкций обычно может быть сгенерирована встроенно путем расширения макроса из одного исходного оператора макроса (с нулем или более параметрами). Одним из параметров может быть возможность альтернативно сгенерировать однократную отдельную подпрограмму, содержащую последовательность и обрабатываемую вместо этого встроенным вызовом функции. Пример:
MOVE FROM=array1,TO=array2,INLINE=NO
Для встраивания был исследован ряд различных эвристик. Обычно алгоритм встраивания имеет определенный бюджет кода (разрешенное увеличение размера программы) и направлен на встраивание наиболее ценных мест вызова без превышения этого бюджета. В этом смысле многие алгоритмы встраивания обычно моделируются по образцу задачи о рюкзаке . [10] Чтобы решить, какие сайты вызовов более ценны, алгоритм встраивания должен оценить их выгоду, то есть ожидаемое уменьшение времени выполнения. Обычно встроенные программы используют информацию профилирования о частоте выполнения различных путей кода для оценки преимуществ. [11]
В дополнение к профилированию информации, новые JIT-компиляторы применяют несколько более продвинутых эвристик, таких как: [4]
Встроенное расширение само по себе является оптимизацией, поскольку оно устраняет накладные расходы на вызовы, но оно гораздо важнее как обеспечивающее преобразование . То есть, как только компилятор расширяет тело функции в контексте места ее вызова (часто с аргументами, которые могут быть фиксированными константами ), он может выполнять различные преобразования, которые раньше были невозможны. Например, условный переход может оказаться всегда истинным или всегда ложным в этом конкретном месте вызова. Это, в свою очередь, может обеспечить устранение мертвого кода , движение инвариантного к циклу кода или устранение индукционной переменной .
В примере 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 ; если ( y == -1 ) вернуть -2 ; вернуть 2 * y - 1 ; } Полное встроенное расширение не всегда возможно из-за рекурсии : рекурсивное встроенное расширение вызовов не завершится. Существуют различные решения, такие как расширение ограниченного количества или анализ графа вызовов и разрыв циклов в определенных узлах (т. е. отказ от расширения некоторого ребра в рекурсивном цикле). [12] Идентичная проблема возникает при расширении макросов, поскольку рекурсивное расширение не завершается и обычно решается путем запрета рекурсивных макросов (как в C и C++).
Традиционно в таких языках, как C , встроенное расширение выполнялось на уровне исходного кода с помощью параметризованных макросов . Использование настоящих встроенных функций, доступных в C99 , дает несколько преимуществ по сравнению с этим подходом:
Многие компиляторы также могут встроенно расширять некоторые рекурсивные функции ; [13] рекурсивные макросы обычно незаконны.
Бьерн Страуструп , разработчик C++, любит подчеркивать, что макросов следует избегать везде, где это возможно, и выступает за широкое использование встроенных функций.
Многие компиляторы агрессивно встраивают функции везде, где это выгодно. Хотя это может привести к увеличению размера исполняемых файлов , агрессивное встраивание, тем не менее, становится все более желательным, поскольку объем памяти увеличивается быстрее, чем скорость процессора. Встраивание — это критическая оптимизация в функциональных языках и объектно-ориентированных языках программирования , которые полагаются на него, чтобы обеспечить достаточный контекст для своих обычно небольших функций, чтобы сделать классические оптимизации эффективными.
Многие языки, включая Java и функциональные языки , не предоставляют языковых конструкций для встроенных функций, но их компиляторы или интерпретаторы часто выполняют агрессивное встроенное расширение. [4] Другие языки предоставляют конструкции для явных подсказок, обычно в виде директив компилятора (прагм).
В языке программирования Ада существует прагма для встроенных функций.
Функции в Common Lisp могут быть определены как встроенные посредством inlineтакого объявления: [14]
( декламация ( встроенная отправка )) ( defun отправка ( x ) ( funcall ( get ( car x ) 'dispatch ) x )) Компилятор Haskell GHC пытается встроить функции или значения, которые достаточно малы , но встраивание можно явно отметить с помощью языковой прагмы: [15]
key_function :: Int -> String -> ( Bool , Double ) {-# INLINE key_function #-} В C и C++ есть inlineключевое слово, которое действует как директива компилятора, указывая, что встраивание желательно , но не обязательно , а также изменяет видимость и поведение компоновки. Изменение видимости необходимо, чтобы обеспечить возможность встраивания функции через стандартную цепочку инструментов C, где за компиляцией отдельных файлов (скорее, единиц перевода ) следует связывание: чтобы компоновщик мог встраивать функции, они должны быть указаны в заголовок (чтобы быть видимым) и помеченный inline(во избежание двусмысленности из-за нескольких определений).
