В вычислительной технике встроенное расширение или встраивание — это ручная или компиляторная оптимизация , которая заменяет место вызова функции телом вызываемой функции. Встроенное расширение похоже на макрорасширение , но происходит во время компиляции, без изменения исходного кода (текста), тогда как макрорасширение происходит до компиляции и приводит к другому тексту, который затем обрабатывается компилятором.
Встраивание является важной оптимизацией, но имеет сложные эффекты на производительность. [1] Как правило , некоторое встраивание улучшит скорость при очень незначительной стоимости пространства, но избыточное встраивание ухудшит скорость из-за того, что встраиваемый код будет потреблять слишком много кэша инструкций , а также будет стоить значительного пространства. Обзор скромной академической литературы по встраиванию с 1980-х и 1990-х годов дан в Peyton Jones & Marlow 1999. [2]
Расширение Inline похоже на расширение макроса, поскольку компилятор помещает новую копию функции в каждое место, где она вызывается. Встроенные функции работают немного быстрее обычных функций, поскольку экономятся накладные расходы на вызов функций, однако есть штраф за использование памяти. Если функция встраивается 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 ) { если ( x == 0 ) вернуть 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) */ если ( 0 == 0 ) tmp += 0 ; иначе tmp += 0 - 1 ; /* (2) */ если ( y + 1 == 0 ) tmp += 0 ; иначе tmp += ( y + 1 ) - 1 ; /* (3) */ вернуть tmp ; } Обратите внимание, что это всего лишь пример. В реальном приложении C было бы предпочтительнее использовать встроенную языковую функцию, такую как параметризованные макросы или встроенные функции, чтобы сообщить компилятору о необходимости преобразовать код таким образом. В следующем разделе перечислены способы оптимизации этого кода.
Макросы ассемблера предоставляют альтернативный подход к встраиванию, при котором последовательность инструкций обычно может быть сгенерирована встраиванием путем макрорасширения из одного исходного оператора макроса (с нулевым или большим количеством параметров). Одним из параметров может быть опция для альтернативного создания одноразовой отдельной подпрограммы, содержащей последовательность и обработанной вместо этого встраиваемым вызовом функции. Пример:
ПЕРЕМЕСТИТЬ ОТ=массив1,ДО=массив2,ВСТРОЕННО=НЕТ
Для встраивания был изучен ряд различных эвристик. Обычно алгоритм встраивания имеет определенный бюджет кода (допустимое увеличение размера программы) и нацелен на встраивание наиболее ценных callsites без превышения этого бюджета. В этом смысле многие алгоритмы встраивания обычно моделируются по образцу задачи о рюкзаке . [10] Чтобы решить, какие callsites более ценны, алгоритм встраивания должен оценить их выгоду, т. е. ожидаемое сокращение времени выполнения. Обычно встраиватели используют информацию профилирования о частоте выполнения различных путей кода для оценки выгод. [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 ; if ( y == -1 ) return -2 ; return 2 * y - 1 ; } Полное встроенное расширение не всегда возможно из-за рекурсии : рекурсивное встроенное расширение вызовов не завершится. Существуют различные решения, такие как расширение ограниченного количества или анализ графа вызовов и разрыв циклов в определенных узлах (т. е. не расширение некоторого ребра в рекурсивном цикле). [12] Идентичная проблема возникает при макрорасширении, поскольку рекурсивное расширение не завершается и обычно решается запретом рекурсивных макросов (как в C и C++).
Традиционно в таких языках, как C , встроенное расширение выполнялось на уровне исходного кода с использованием параметризованных макросов . Использование настоящих встроенных функций, которые доступны в C99 , обеспечивает несколько преимуществ по сравнению с этим подходом:
Многие компиляторы также могут встраивать некоторые рекурсивные функции ; [13] рекурсивные макросы обычно недопустимы.
Бьярне Страуструп , разработчик C++, любит подчеркивать, что макросов следует избегать везде, где это возможно, и выступает за широкое использование встроенных функций.
Многие компиляторы агрессивно встраивают функции везде, где это выгодно. Хотя это может привести к увеличению исполняемых файлов , агрессивное встраивание тем не менее становится все более и более желательным, поскольку объем памяти увеличивается быстрее, чем скорость ЦП. Встраивание является критической оптимизацией в функциональных языках и объектно-ориентированных языках программирования , которые полагаются на него, чтобы обеспечить достаточный контекст для своих обычно небольших функций, чтобы сделать классические оптимизации эффективными.
Многие языки, включая Java и функциональные языки , не предоставляют языковых конструкций для встроенных функций, но их компиляторы или интерпретаторы часто выполняют агрессивное встроенное расширение. [4] Другие языки предоставляют конструкции для явных подсказок, как правило, в виде директив компилятора (прагм).
В языке программирования Ada существует прагма для встроенных функций.
Функции в Common Lisp могут быть определены как встроенные с помощью inlineследующего объявления: [14]
( declaim ( inline dispatch )) ( defun dispatch ( x ) ( funcall ( get ( car x ) 'dispatch ) x )) Компилятор Haskell GHC пытается встроить функции или значения, которые достаточно малы, но встраивание может быть явно указано с помощью языковой прагмы: [ 15]
key_function :: Int -> String -> ( Bool , Double ) {-# INLINE key_function #-} В C и C++ есть inlineключевое слово, которое служит подсказкой о том, что встраивание может быть полезным; однако в новых версиях его основная цель — изменить видимость и связывающее поведение функции. [16]
