Встроенное расширение - Inline expansion

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

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

Обзор

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

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

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

Обычно при вызове функции контроль переносится на его определение ответвляться или позвоните в инструкцию. При встраивании управление передается непосредственно коду функции без инструкции перехода или вызова.

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

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

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

Влияние на производительность

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

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

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

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

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

  • А постоянный переданный в качестве аргумента часто может быть распространен на все экземпляры соответствующего параметра, или часть функции может быть «выведена» из цикла (через движение кода с инвариантным циклом ).
  • Размещение регистров может выполняться через большее тело функции.
  • Оптимизация высокого уровня, например анализ побега и удвоение хвоста, может выполняться в большем объеме и быть более эффективным, особенно если компилятор, реализующий эти оптимизации, в первую очередь полагается на внутрипроцедурный анализ.[4]

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

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

Еще одно преимущество встраивания для системы памяти:

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

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

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

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

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

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

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

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

Выполнение

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

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

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

int пред(int Икс){    если (Икс == 0)        возвращаться 0;    еще        возвращаться Икс - 1;}

Перед встраиванием:

int func(int у) {    возвращаться пред(у) + пред(0) + пред(у+1);}

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

int func(int у) {    int tmp;    если (у   == 0) tmp  = 0; еще tmp  = у - 1;       /* (1) */    если (0   == 0) tmp += 0; еще tmp += 0 - 1;       /* (2) */    если (у+1 == 0) tmp += 0; еще tmp += (у + 1) - 1; /* (3) */    возвращаться tmp;}

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

Встраивание с помощью расширения макроса сборки

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

ПЕРЕМЕСТИТЬ ОТ = array1, TO = array2, INLINE = NO

Эвристика

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

Помимо информации о профиле, более новые своевременные компиляторы применить несколько более сложных эвристик, таких как:[4]

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

Преимущества

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

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

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

Новая функция выглядит так:

int func(int у) {    если (у == 0)        возвращаться 0;    если (у == -1)        возвращаться -2;    возвращаться 2*у - 1;}

Ограничения

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

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

Традиционно в таких языках, как C, встроенное расширение было выполнено на уровне исходного кода с использованием параметризованные макросы. Использование настоящих встроенных функций, доступных в C99, дает несколько преимуществ по сравнению с этим подходом:

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

Многие компиляторы также могут расширять некоторые рекурсивные функции;[13] рекурсивные макросы обычно недопустимы.

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

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

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

Языковая поддержка

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

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

Функции в Common Lisp может быть определен как встроенный в соответствии декларация как таковая:[14]

 (декламировать (в соответствии отправлять)) (defun отправлять (Икс)   (веселье     (получать (машина Икс) 'отправлять) Икс))

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

key_function :: Int -> Строка -> (Bool, Двойной){- # INLINE key_function # -}

C и C ++

Основная статья: Встроенная функция

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

Смотрите также

Примечания

  1. ^ Использование пространства - это «количество инструкций», и одновременно это использование пространства во время выполнения и двоичный файл размер.
  2. ^ Размер кода фактически уменьшается для очень коротких функций, когда накладные расходы на вызовы больше, чем тело функции, или одноразовых функций, где не происходит дублирования.

Рекомендации

  1. ^ а б Chen et al. 1993 г..
  2. ^ Chen et al. 1993 г., 3.4 Встроенное расширение функций, стр. 14.
  3. ^ а б c [1] Prokopec et al., Оптимизационный алгоритм инкрементальной встроенной замены для своевременных компиляторов, публикация CGO'19 о встраиваемом модуле, используемом в компиляторе Graal для JVM
  4. ^ Chen et al. 1993 г., 3.4 Встроенное расширение функций, стр. 19–20.
  5. ^ а б Бенджамин Пулен (8 августа 2013 г.). «Необычный прирост скорости: размер имеет значение».
  6. ^ См., Например, Адаптивная система оптимизации В архиве 2011-08-09 на Wayback Machine в Jikes RVM для Java.
  7. ^ Chen et al. 1993 г., 3.4 Встроенное расширение функций, стр. 24–26.
  8. ^ [2] Описание инлайнера, используемого в JIT-компиляторе Graal для Java
  9. ^ [3] Шайфлер, Анализ встроенной подстановки для языка структурированного программирования
  10. ^ [4] Мэтью Арнольд, Стивен Финк, Вивек Саркар и Питер Ф. Суини, Сравнительное исследование статических и профильных эвристик для встраивания
  11. ^ Джонс и Марлоу 1999, 4. Обеспечение расторжения, стр. 6–9.
  12. ^ Встраивание семантики для подпрограмм, которые являются рекурсивными " к Генри Г. Бейкер
  13. ^ Декларация В СООТВЕТСТВИИ, NOTINLINE на Common Lisp HyperSpec
  14. ^ 7.13.5.1. INLINE прагма Глава 7. Возможности языка GHC

внешняя ссылка