В вычислениях, встроенное расширение или встраивание - это ручная или оптимизация компилятора, которая заменяет функцию call site телом вызываемой функции. Встроенное расширение похоже на расширение макроса, но происходит во время компиляции без изменения исходного кода (текста), тогда как расширение макроса происходит до компиляции и приводит к другому тексту, который затем обрабатывается компилятором.
Встраивание - важная оптимизация, но она оказывает сложное влияние на производительность. Как показывает эмпирическое правило, некоторая встраивание улучшит скорость при очень незначительных затратах места, но избыточное встраивание повредит скорости из-за того, что встроенный код потребляет слишком много кэша инструкций , и также стоят значительного места. Обзор скромной академической литературы по встраиванию с 1980-х и 1990-х годов дан в Jones Marlow 1999.
Встроенное расширение аналогично раскрытию макроса, поскольку компилятор помещает новую копию функции в каждую место это называется. Встроенные функции работают немного быстрее, чем обычные функции, так как накладные расходы на вызов функций сохраняются, однако это приводит к потере памяти. Если функция встроена 10 раз, в код будет вставлено 10 копий функции. Следовательно, встраивание лучше всего подходит для небольших часто вызываемых функций. В C ++ функции-члены класса, если они определены в определении класса, по умолчанию встроены (нет необходимости использовать ключевое слово inline); в противном случае необходимо ключевое слово. Компилятор может игнорировать попытку программиста встроить функцию, особенно если она очень большая.
Встроенное расширение используется для устранения затрат времени (лишнего времени) при вызове функции. Обычно он используется для часто выполняемых функций. Он также имеет преимущество по пространству для очень маленьких функций и позволяет преобразовать другие оптимизации.
Без встроенных функций компилятор решает, какие функции встроить. Программист практически не контролирует, какие функции встроены, а какие нет. Предоставление такой степени контроля программисту позволяет использовать знания конкретного приложения при выборе функций для встраивания.
Обычно, когда функция вызывается, элемент управления передается в ее определение с помощью ветви или инструкции вызова. При встраивании управление передается непосредственно коду функции без инструкции перехода или вызова.
Компиляторы обычно реализуют операторы с встраиванием. Условия цикла и тела цикла нуждаются в отложенной оценке. Это свойство выполняется, когда код для вычисления условий цикла и тела цикла встроен. Еще одна причина для использования встроенных операторов - соображения производительности.
В контексте языков функционального программирования за встроенным расширением обычно следует преобразование бета-редукция.
Программист может встроить функцию вручную с помощью копирования и вставки программирования, как одноразовую операцию над исходным кодом. Однако другие методы управления встраиванием (см. Ниже) предпочтительнее, поскольку они не вызывают ошибок, возникающих, когда программист игнорирует (возможно, измененную) дублированную версию тела исходной функции, исправляя ошибку во встроенной функции.
Прямым эффектом этой оптимизации является улучшение временных показателей (за счет устранения накладных расходов на вызовы) за счет ухудшения использования пространства (из-за дублирования тело функции). Расширение кода из-за дублирования тела функции преобладает, за исключением простых случаев, и, следовательно, прямой эффект встроенного расширения заключается в сокращении времени за счет пространства.
Однако основное преимущество встроенного расширения - это возможность дальнейшей оптимизации и улучшенного планирования из-за увеличения размера тела функции, так как лучшая оптимизация возможна для более крупных функций. Конечное влияние встроенного расширения на скорость усложняется из-за множественного влияния на производительность системы памяти (в первую очередь кэш инструкций ), которая доминирует над производительностью современных процессоров: в зависимости от конкретной программы и кеша, встраивание конкретного функции могут увеличивать или уменьшать производительность.
Влияние встраивания зависит от языка программирования и программы из-за разной степени абстракции. В низкоуровневых императивных языках, таких как C и Fortran, скорость обычно увеличивается на 10–20% с незначительным влиянием на размер кода, тогда как в более абстрактных языках это может быть значительно более важным из-за количества удаляемых при встраивании слоев, крайним примером является Self, где один компилятор увидел коэффициенты улучшения от 4 до 55 за счет встраивания.
Прямые преимущества исключения вызова функции:
Однако основным преимуществом встраивания является возможность дальнейшей оптимизации. Оптимизации, которые пересекают границы функций, могут выполняться без необходимости межпроцедурной оптимизации (IPO): после выполнения встраивания дополнительные внутрипроцедурные оптимизации («глобальные оптимизации») становятся возможными в увеличенном теле функции. Например:
Это можно сделать без встраивания, но для этого потребуется значительно более сложный компилятор и компоновщик (в случае, если вызывающий и вызываемый объекты находятся в отдельных единицах компиляции).
И наоборот, в некоторых случаях спецификация языка может позволить программе делать дополнительные предположения об аргументах процедур, которые она больше не может делать после встраивания процедуры, предотвращая некоторые оптимизации. Более умные компиляторы (например, Glasgow Haskell Compiler ) будет отслеживать это, но наивный инлайнинг теряет эту информацию.
Еще одним преимуществом встраивания для системы памяти является:
Прямые затраты на встраивание - это увеличение размера кода из-за дублирования тела функции на каждом сайте вызова. Однако это происходит не всегда, а именно в случае очень коротких функций, когда тело функции меньше размера вызова функции (у вызывающего, включая обработку аргументов и возвращаемого значения), например тривиальный метод доступа методы или методы-мутаторы (геттеры и сеттеры); или для функции, которая используется только в одном месте, и в этом случае она не дублируется. Таким образом, встраивание может быть минимизировано или исключено при оптимизации для размера кода, как это часто бывает в встроенных системах.
Встраивание также накладывает затраты на производительность из-за расширения кода (из-за дублирования), ухудшающего производительность кэша инструкций. Это наиболее важно, если до расширения рабочий набор программы (или горячая часть кода) помещается на один уровень иерархии памяти (например, кэш L1 ), но после расширения он больше не подходит, что приводит к частым пропускам кеша на этом уровне. Из-за значительной разницы в производительности на разных уровнях иерархии это значительно снижает производительность. На самом высоком уровне это может привести к увеличению количества ошибок страниц, катастрофическому снижению производительности из-за перегрузки или к тому, что программа не запустится вообще. Последнее редко встречается в обычных настольных и серверных приложениях, где размер кода невелик по сравнению с доступной памятью, но может быть проблемой для сред с ограниченными ресурсами, таких как встроенные системы. Одним из способов смягчения этой проблемы является разделение функций на меньший горячий встроенный путь (быстрый путь ) и более крупный холодный не встроенный путь (медленный путь).
Встраивание снижает производительность. в первую очередь проблема для больших функций, которые используются во многих местах, но точка безубыточности, за которой встраивание снижает производительность, трудно определить и в целом зависит от точной загрузки, поэтому она может быть подвергнута ручной оптимизации или профилированию. управляемая оптимизация. Это аналогичная проблема с другими оптимизациями расширения кода, такими как разворачивание цикла, что также уменьшает количество обрабатываемых инструкций, но может снизить производительность из-за более низкой производительности кеша.
Точное влияние встраивания на производительность кеша сложно. Для небольших размеров кэша (намного меньших, чем рабочий набор до расширения) преобладает повышенная последовательность, а встраивание улучшает производительность кеша. Для размеров кэша, близких к рабочему набору, где встраивание расширяет рабочий набор, поэтому он больше не помещается в кеш, это доминирует, и производительность кеша снижается. Для размеров кэша, превышающих рабочий набор, встраивание оказывает незначительное влияние на производительность кеша. Кроме того, изменения в конструкции кеша, например, могут компенсировать увеличение количества промахов в кэше.
Компиляторы используют различные механизмы, чтобы решить, какие вызовы функций должны быть встроены; они могут включать ручные подсказки программистов для конкретных функций, а также общее управление с помощью параметров командной строки. Встраивание выполняется автоматически многими компиляторами на многих языках на основе суждения о целесообразности встраивания, в то время как в других случаях его можно указать вручную с помощью директив компилятора , обычно с использованием ключевого слова или директивы компилятора называется встроенным
. Обычно это только намекает на то, что встраивание желательно, а не требует встраивания, причем сила подсказки зависит от языка и компилятора.
Обычно разработчики компиляторов учитывают указанные выше проблемы производительности и включают в свои компиляторы эвристику, которая выбирает, какие функции встраивать, чтобы улучшить производительность, а не ухудшать ее, в большинстве случаев..
После того, как компилятор решил встроить конкретную функцию, выполнение самой операции встраивания обычно является простым. В зависимости от того, встраивает ли компилятор функции в код на разных языках, компилятор может выполнять встраивание либо в высокоуровневое промежуточное представление (например, абстрактные синтаксические деревья ), либо на низкоуровневое промежуточное представление. В любом случае компилятор просто вычисляет аргументы, сохраняет их в переменных, соответствующих аргументам функции, а затем вставляет тело функции в место вызова.
Линкеры также могут выполнять встраивание функций. Когда компоновщик встраивает функции, он может встраивать функции, источник которых недоступен, например, библиотечные функции (см. оптимизация времени компоновки ). Система времени выполнения также может встраиваться. Во время выполнения встраивание может использовать информацию динамического профилирования, чтобы принимать более правильные решения о том, какие функции встраивать, как в компиляторе Java Hotspot.
Вот простой пример встроенного расширения, выполняемого «вручную» на уровне исходного кода в языке программирования 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
Для встраивания был исследован ряд различных эвристик. Обычно алгоритм встраивания имеет определенный бюджет кода (допустимое увеличение размера программы) и нацелен на встраивание наиболее ценных сайтов вызовов без превышения этого бюджета. В этом смысле многие алгоритмы встраивания обычно моделируются после задачи о ранце. Чтобы решить, какие call-сайты более ценны, алгоритм встраивания должен оценить их выгоду, т. Е. ожидаемое сокращение времени выполнения. Обычно инлайнеры используют профилирующую информацию о частоте выполнения различных путей кода для оценки преимуществ.
Помимо информации профилирования, более новые оперативные компиляторы применяют несколько более продвинутых эвристики, например:
Встроенное расширение само по себе является оптимизацией, поскольку он устраняет накладные расходы на вызовы, но гораздо более важен как , разрешающий преобразование. То есть, как только компилятор расширяет тело функции в контексте своего сайта вызова - часто с аргументами, которые могут быть фиксированными константами, - он может выполнять различные преобразования, которые раньше были невозможны. Например, условная ветвь может оказаться всегда истинной или всегда ложной на этом конкретном сайте вызова. Это, в свою очередь, может разрешить устранение мертвого кода, перемещение кода с инвариантным циклом или исключение индукционной переменной.
В примере 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; return 2 * y - 1; }
Полное встроенное расширение не всегда возможно из-за рекурсии : при рекурсивном встроенном расширении вызовы не завершаются. Существуют различные решения, такие как расширение ограниченного количества или анализ графа вызовов и прерывание циклов в определенных узлах (то есть, не расширение некоторого ребра в рекурсивном цикле). Аналогичная проблема возникает при расширении макросов, поскольку рекурсивное раскрытие не завершается и обычно разрешается путем запрета рекурсивных макросов (как в C и C ++).
Традиционно в таких языках, как C, встроенное расширение выполнялось на уровне источника с использованием параметризованных макросов. Использование настоящих встроенных функций, доступных в C99, дает несколько преимуществ по сравнению с этим подходом:
Многие компиляторы также могут встроить некоторые рекурсивные функции ; рекурсивные макросы обычно недопустимы.
Бьярн Страуструп, разработчик C ++, любит подчеркивать, что по возможности следует избегать макросов, и выступает за широкое использование встроенных функций.
Многие компиляторы агрессивно встраивают функции везде, где это выгодно. Хотя это может привести к увеличению размера исполняемых файлов, агрессивное встраивание, тем не менее, становится все более и более желательным, поскольку объем памяти увеличивается быстрее, чем скорость процессора. Встраивание - это критическая оптимизация в функциональных языках и объектно-ориентированных языках программирования, которые полагаются на него, чтобы обеспечить достаточный контекст для своих обычно небольших функций, чтобы сделать классические оптимизации эффективными.
Многие языки, включая Java и функциональные языки, не предоставляют языковые конструкции для встроенных функций, но часто их компиляторы или интерпретаторы выполняйте агрессивное встроенное расширение. Другие языки предоставляют конструкции для явных подсказок, обычно в виде директив компилятора (прагмы).
В языке программирования Ada существует прагма для встроенных функций.
Функции в Common Lisp могут быть определены как встроенные с помощью объявления inline
как такового:
(declim (inline dispatch)) (defun dispatch (x) (funcall (get (car x) 'dispatch) x))
Компилятор Haskell GHC пытается встроить функции или значения, которые достаточно малы, но встраивание может быть отмечено явно с помощью прагма языка:
key_function :: Int ->String ->(Bool, Double) {- # INLINE key_function # -}
C и C ++ имеют inline
ключевое слово, которое действует как директива компилятора, указывая, что встраивание желательно, но не обязательно, а также изменяет видимость и поведение связывания. Изменение видимости необходимо для того, чтобы функция могла быть встроена с помощью стандартной инструментальной цепочки C, где за компиляцией отдельных файлов (скорее, единиц перевода ) следует связывание: чтобы компоновщик мог встраивать функции, они должны быть указаны в заголовке (чтобы быть видимыми) и помечены как inline
(во избежание двусмысленности из нескольких определений).
Искать встраивание в Wiktionary, бесплатный словарь. |