Встроенное расширение

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

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

Обзор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация

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

Линкеры также могут выполнять встраивание функций. Когда компоновщик встраивает функции, он может встраивать функции, исходный код которых недоступен, например библиотечные функции (см. Оптимизация времени компоновки ). Система времени выполнения также может функционировать в режиме реального времени. Встраивание во время выполнения может использовать информацию динамического профилирования для принятия более эффективных решений о том, какие функции встраивать, как в компиляторе 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
 

Эвристика

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

В дополнение к профилированию информации, новые JIT-компиляторы применяют несколько более продвинутых эвристик, таких как:

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

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

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

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

• The 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  ; 
  } 

Ограничения

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

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

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

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

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

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

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

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

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

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

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

Функции в Common Lisp могут быть определены как встроенные с помощью inline декларация как таковая:

 (  декламация   (  встроенная   отправка  )) 
  (  defun   отправка   (  x  ) 
    (  funcall 
      (  get   (  car   x  )   'отправка  )   x  )) 

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

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

C и C++

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

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

См. также

• Макрос
• Частичная оценка
• Устранение хвостового вызова
• Описание кода

Ссылки

• Чен, Вайоминг; Чанг, ПП; Конте, ТМ; Хву, WW (сентябрь 1993 г.). «Влияние оптимизации расширения кода на дизайн кэша инструкций» (PDF) . Транзакции IEEE на компьютерах . 42 (9): 1045–1057. дои : 10.1109/12.241594 . hdl : 2142/74513 .
• Пейтон Джонс, Саймон ; Марлоу, Саймон (сентябрь 1999 г.). Секреты инлайнера компилятора Glasgow Haskell (технический отчет).

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

• « Устранение вызовов виртуальных функций в программах на C++ », Джеральд Айгнер и Урс Хельцле
• « Уменьшение накладных расходов на косвенный вызов функций в программах на C++ », Брэд Колдер и Дирк Грумвальд
• ALTO — оптимизатор времени соединения для DEC Alpha
• « Продвинутые методы » Джона Р. Левина
• « Полная оптимизация программы с помощью Visual C++ .NET », Брэндон Брей