• Партиционная компиляция (ocamlc)
• Система верхнего уровня или REPL (ocaml)
• Система выполнения (ocamlrun)
• Компиляция в машинный код (ocamlopt)
• Генераторы лексических и синтаксических анализаторов (ocamllex, ocamlyacc)
• Генератор зависимостей (ocamldep)
• Генератор документации (ocamldoc)
• Отладчик (ocamldebug)
• Профилирование (ocamlprof)
• Интерфейсы C с OCaml
• Оптимизация с Flambda
• Fuzzing с afl-fuzz
• Отслеживание выполнения с помощью событий runtime
• Преобразование программы «Tail Modulo Constructor»
• Обнаружение гонок данных в runtime с ThreadSanitizer

Глава 23 Оптимизация с Flambda

1 Обзор

Flambda — это термин, используемый для описания серии оптимизирующих проходов, предоставляемых компиляторами машинного кода начиная с OCaml 4.03.

Flambda предназначен для упрощения написания идиоматического кода OCaml без потери производительности.

Для использования оптимизаторов Flambda необходимо передать параметр -flambda скрипту конфигурации OCaml configure. (Нет поддержки единого компилятора, который может работать как в режиме Flambda, так и без него.) Код, скомпилированный с Flambda, не может быть связан в одну программу с кодом, скомпилированным без Flambda. Попытка сделать это приведёт к ошибке компилятора.

Можно определить, использует ли конкретный ocamlopt Flambda, вызвав его с параметром -config и просмотрев любую строку, начинающуюся с «flambda:». Если такая строка есть и содержит «true», то Flambda поддерживается, в противном случае — нет.

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

Оптимизация с Flambda в настоящее время не поддерживается при генерации байт-кода.

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

Flambda пока не оптимизирует проверки границ массивов или строк. Он также не использует подсказки для оптимизации, полученные из утверждений, написанных пользователем в коде.

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

2 Флаги командной строки

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

Часто используемые параметры:

-O2

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

-O3

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

-Oclassic

Принимать решения об инлайнинге на момент определения функции, а не в местах вызова. Это соответствует поведению компиляторов OCaml, не использующих Flambda. По сравнению с компиляцией с новыми эвристиками инлайнинга Flambda (например, при -O2) он создаёт файлы .cmx меньшего размера, сокращает время компиляции и код, который, вероятно, работает немного медленнее. При использовании -Oclassic актуальны только следующие параметры, описанные в этом разделе: -inlining-report и -inline. Если используются какие-либо другие параметры, описанные в этом разделе, поведение является неопределённым и может вызвать ошибку в будущих версиях компилятора.

-inlining-report

Создавать файлы .inlining (один на раунд оптимизации), показывающие все решения инлайнера.

Реже используемые параметры:

-remove-unused-arguments

Удалять неиспользуемые аргументы функций, даже если аргумент не специализирован. Это может немного сказаться на производительности. См. раздел 23.10.3.

-unbox-closures

Передавать свободные переменные через специализированные аргументы, а не замыкания (оптимизация для уменьшения выделения памяти). См. раздел 23.9.3. Это может немного сказаться на производительности.

Расширенные параметры, необходимые только для тонкой настройки:

-inline

Поведение зависит от использования -Oclassic.

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

-inline-toplevel

Аналогично -inline, но используется, когда спекулятивный инлайнинг начинается на верхнем уровне. См. раздел 23.3.6. Не используется в режиме -Oclassic.

...

Примечания

• Набор флагов командной строки, относящихся к оптимизации, обычно должен быть одинаковым для всего проекта. Flambda в настоящее время не записывает запрошенные флаги в файлы .cmx. В связи с этим, встраивание функций из ранее скомпилированных модулей подвергнет их код параметрам оптимизации текущего компилируемого модуля, а не тем, которые были указаны при их предыдущей компиляции. В будущем планируется устранить этот недостаток.
• Флаги, специфичные для Flambda, не влияют на линковку, за исключением влияния на оптимизацию кода в стартовом файле (содержащем сгенерированные функции, такие как вспомогательные функции кэрирования). Обычно такая оптимизация не будет значительной, поэтому отключение таких флагов на этапе линковки может быть целесообразно.
• Флаги, специфичные для Flambda, принимаются без каких-либо сообщений об ошибках даже в том случае, если параметр -flambda не был передан в скрипт configure. (Не предусмотрено изменение этого поведения.) Это призвано упростить выполнение бенчмарков с включёнными и выключенными оптимизаторами Flambda.
• Некоторые флаги Flambda могут быть изменены в будущих выпусках.

2.1 Указание параметров оптимизации по раундам

Flambda работает в раундах: один раунд состоит из определенной последовательности преобразований, которые затем могут быть повторены для достижения более удовлетворительных результатов. Количество раундов можно установить вручную, используя параметр -rounds (хотя это не требуется при использовании предопределенных уровней оптимизации, таких как -O2 и -O3). Для высокой оптимизации количество раундов может быть установлено на 3 или 4.

Флаги командной строки, которые могут применяться в каждом раунде, например, те, у которых в имени есть -cost, принимают аргументы в формате:

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

Флаги -Oclassic, -O2 и -O3 применяются до всех остальных флагов, что означает, что некоторые параметры могут быть перезаписаны без необходимости указывать каждый параметр, обычно вызываемый данным уровнем оптимизации.

3 Встраивание

Встраивание относится к копированию кода функции в место, где функция вызывается. Код функции будет окружён связыванием его параметров с соответствующими аргументами.

Цели встраивания:

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

Эти цели часто достигаются не только самим встраиванием, но и другими оптимизациями, которые компилятор может выполнить в результате встраивания.

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

Например, приведённый ниже код:

let rec fact x =
  if x = 0 then
    1
  else
    x * fact (x - 1)

let n = fact 4

раскручивание один раз в месте вызова fact 4 даёт (с неизменённым телом fact):

let n =
  if 4 = 0 then
    1
  else
    4 * fact (4 - 1)

Это упрощается до:

let n = 4 * fact 3

Flambda предоставляет значительно расширенные возможности встраивания по сравнению с предыдущими версиями компилятора.

Примечание: при выполнении встраивания

Встраивание выполняется вместе со всеми другими этапами оптимизации Flambda, то есть после преобразования замыканий. Это даёт три конкретных преимущества по сравнению с потенциально более простым реализацией до преобразования замыканий:

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

3.1 Эвристика классического встраивания

В режиме -Oclassic поведение встраивателя Flambda имитирует предыдущие версии компилятора. (Код всё ещё может подвергаться дальнейшей оптимизации, не выполняемой предыдущими версиями компилятора: могут встраиваться функторы, константы поднимаются, и удаляется неиспользуемый код, всё как описано в этой главе. См. разделы 23.3.3, 23.8.1 и 23.10. В месте определения функции измеряется объём тела функции. Функция будет помечена как пригодная для встраивания (и, следовательно, встроенная в каждом непосредственном месте вызова) если:

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

Не-Flambda версии компилятора не могут встраивать функции, содержащие определение другой функции. Однако -Oclassic это позволяет. Кроме того, не-Flambda версии также не могут встраивать функции, которые сами являются результатом предыдущего этапа встраивания, но это разрешено -Oclassic. Например:

module M : sig
  val i : int
end = struct
  let f x =
    let g y = x + y in
    g
  let h = f 3
  let i = h 4  (* h is correctly discovered to be g and inlined *)
end

Всё это контрастирует с обычным режимом Flambda, то есть без -Oclassic, где:

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

Режим Flambda описан в следующем разделе.

3.2 Обзор эвристик встраивания “Flambda”

Эвристики встраивания Flambda, используемые всякий раз, когда компилятор настроен на Flambda и -Oclassic не указан, принимают решения о встраивании в местах вызова. Это помогает в ситуациях, когда контекст важен. Например:

let f b x =
  if b then
    x
  else
    ... big expression ...

let g x = f true x

В этом случае мы хотели бы встроить f в g, так как условный переход может быть устранён, и размер кода должен уменьшиться. Если решение о встраивании принято после объявления f без учёта его использования, его размер, вероятно, сделал бы его непригодным для встраивания; но в месте вызова его окончательный размер может быть известен. Кроме того, эту функцию, вероятно, не следует встраивать систематически: если b неизвестно, или даже false, польза не велика по сравнению с большим увеличением размера кода. В существующем не-Flambda встраивателе это не большая проблема, потому что цепочки встраивания обрывались довольно быстро. Однако это привело к чрезмерному использованию чрезмерно больших параметров встраивания, таких как -inline 10000.

Более подробно, в каждом месте вызова выполняется следующая процедура:

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

Встраивание внутри рекурсивных функций вызовов других функций в той же группе взаимной рекурсии контролируется глубиной раскручивания, описанной ниже. Это гарантирует, что функции не будут раскручиваться чрезмерно. (Раскручивание включено только если выбран уровень оптимизации -O3 и/или флаг -inline-max-unroll передан с аргументом, большим нуля.)

3.3 Обработка конкретных конструкций языка

Функторы

Нет ничего особенного в функторах, что препятствует встраиванию по сравнению с обычными функциями. Для встраивателя они выглядят одинаково, за исключением того, что функторы помечены как таковые.

Приложения функторов на верхнем уровне имеют тенденцию к встраиванию. (Этот уклон может быть изменён: см. документацию по -inline-lifting-benefit ниже.)

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

Модули первого класса

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

Объекты

Вызовы методов к объектам в настоящее время не встраиваются в Flambda.

3.4 Отчёты о встраивании

Если в компилятор передаётся опция -inlining-report, то будет создан файл, соответствующий каждому раунду оптимизации. Для файла исходного кода OCaml basename.ml файлы называются basename.round.inlining.org, где round — целое число с нулевой базой. Внутри файлов, отформатированных как «org-режим», будет представлен английский текст, описывающий решения, принятые инлайнером.

3.5 Оценка выгоды от встраивания

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

Например, для следующего кода:

let f b x =
  if b then
    x
  else
    ... big expression ...

let g x = f true x

будет отмечено, что встраивание f удалит:

• один прямой вызов;
• одну условную ветвь.

Формально, оценка выгоды от производительности во время выполнения вычисляется путём предварительного суммирования стоимости операций, которые, как известно, удаляются в результате встраивания и последующей упрощения тела встраиваемой функции. Индивидуальные стоимости различных типов операций могут быть скорректированы с помощью различных флагов -inline-...-cost следующим образом. Стоимости задаются как целые числа. Все эти флаги принимают один аргумент, описывающий такие целые числа с использованием соглашений, описанных в разделе 23.2.1.

-inline-alloc-cost

Стоимость выделения.

-inline-branch-cost

Стоимость ветвления.

-inline-call-cost

Стоимость прямого вызова функции.

-inline-indirect-cost

Стоимость косвенного вызова функции.

-inline-prim-cost

Стоимость примитива. Примитивы охватывают операции, включая арифметические операции и доступ к памяти.

(Значения по умолчанию описаны в разделе 23.5 ниже.)

Начальное значение выгоды затем масштабируется с помощью коэффициента, который пытается компенсировать тот факт, что текущая точка в коде, если она находится под несколькими условными ветвями, может быть холодной. (Flambda в настоящее время не вычисляет горячие и холодные пути.) Коэффициент — предполагаемая вероятность того, что инлайнер действительно находится на горячем пути — вычисляется как 1/(1 + f)^d, где f задаётся флагом -inline-branch-factor, а d — глубина вложенности ветвлений в текущей точке. По мере того, как инлайнер спускается по более глубоко вложенным ветвям, выгода от встраивания уменьшается.

Полученное значение выгоды известно как ожидаемая выгода.

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

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

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

3.6 Управление спекуляцией

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

• пороговое значение встраивания;
• глубина встраивания;
• глубина развертывания.

Эти параметры в конечном итоге ограничены аргументами, предоставляемыми соответствующим флагам командной строки (или их значениям по умолчанию):

• -inline (или, если место вызова, которое вызвало спекуляцию, находится на верхнем уровне, -inline-toplevel);
• -inline-max-depth;
• -inline-max-unroll.

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

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

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

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

4 Специализация

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

Если не переопределено атрибутом (см. ниже), специализация функции не будет выполняться, если:

• компилятор находится в режиме -Oclassic;
• функция не является очевидно рекурсивной;
• функция не является замкнутой.

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

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

Пример: хорошо известная функция List.iter

Эта функция может быть записана следующим образом:

let rec iter f l =
  match l with
  | [] -> ()
  | h :: t ->
    f h;
    iter f t

и использоваться так:

let print_int x =
  print_endline (Int.to_string x)

let run xs =
  iter print_int (List.rev xs)

Аргумент f функции iter является инвариантным, поэтому функция может быть специализирована:

let run xs =
  let rec iter' f l =
    (* The compiler knows: f holds the same value as foo throughout iter'. *)
    match l with
    | [] -> ()
    | h :: t ->
      f h;
      iter' f t
  in
  iter' print_int (List.rev xs)

Компилятор отмечает, что для функции iter’ аргумент f специализирован на постоянном замыкании print_int. Это означает, что тело iter’ может быть упрощено:

let run xs =
  let rec iter' f l =
    (* The compiler knows: f holds the same value as foo throughout iter'. *)
    match l with
    | [] -> ()
    | h :: t ->
      print_int h;  (* this is now a direct call *)
      iter' f t
  in
  iter' print_int (List.rev xs)

Вызов print_int можно действительно встроить:

let run xs =
  let rec iter' f l =
    (* The compiler knows: f holds the same value as foo throughout iter'. *)
    match l with
    | [] -> ()
    | h :: t ->
      print_endline (Int.to_string h);
      iter' f t
  in
  iter' print_int (List.rev xs)

Неиспользуемый специализированный аргумент f теперь может быть удалён, оставив:

let run xs =
  let rec iter' l =
    match l with
    | [] -> ()
    | h :: t ->
      print_endline (Int.to_string h);
      iter' t
  in
  iter' (List.rev xs)

Отступление по инвариантным параметрам.

В настоящее время компилятор не может определить инвариантность в таких случаях, как следующий.

let rec iter_swap f g l =
  match l with
  | [] -> ()
  | 0 :: t ->
    iter_swap g f l
  | h :: t ->
    f h;
    iter_swap f g t

4.1 Оценка выгоды от специализации

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

5 Параметры по умолчанию

Значения по умолчанию (если не используется -Oclassic) предназначены для одного цикла оптимизации с использованием следующих параметров.

5.1 Настройки уровня оптимизации -O2

При указании -O2 выполняются два цикла оптимизации. Первый цикл использует параметры по умолчанию (см. выше). Второй использует следующие параметры.

5.2 Настройки уровня оптимизации -O3

При указании -O3 выполняются три цикла оптимизации. Первые два цикла аналогичны циклам для -O2. Третий цикл использует следующие параметры.

6 Ручное управление встраиванием и специализацией

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

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

@@inline always или @@inline never

Прикрепленные к объявлению функции или фукнтора, эти директивы заставляют встроенную функцию всегда или никогда не встраивать, независимо от расчётов размера/выгоды. (Если функция рекурсивная, то тело подставляется, и никакие специальные действия не выполняются для рекурсивного вызова(ов).) @@inline без аргумента эквивалентно @@inline always.

@inlined always или @inlined never

Прикрепленные к применению функции, эти директивы заставляют встроенную функцию действовать аналогично. Эти атрибуты в местах вызова переопределяют любые другие атрибуты, которые могут присутствовать в соответствующем объявлении. @inlined без аргумента эквивалентно @inlined always. @@inlined hint эквивалентно @@inline always за исключением того, что оно не будет генерировать предупреждение 55, если приложение функции не может быть встроено.

Для рекурсивных функций соответствующие атрибуты:

@@specialise always или @@specialise never

Прикрепленные к объявлению функции или фукнтора, они заставляют встроенную функцию всегда или никогда не специализировать функцию, пока у неё есть соответствующие контекстные знания, независимо от расчётов размера/выгоды. @@specialise без аргумента эквивалентно @@specialise always.

@specialised always или @specialised never

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

@unrolled n

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

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

Таким образом, n выступает в качестве «максимальной глубины развертывания».

Предупреждение компилятора будет выведено, если обнаружено, что невозможно выполнить аннотацию из атрибута @inlined или @specialised.

Пример правильного размещения атрибутов

module F (M : sig type t end) = struct
  let[@inline never] bar x =
    x * 3

  let foo x =
    (bar [@inlined]) (42 + x)
end [@@inline never]

module X = F [@inlined] (struct type t = int end)

7 Упрощение

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

Распространение может помочь устранить выделение памяти в таких случаях, как:

let f x y =
  ...
  let p = x, y in
  ...
  ... (fst p) ... (snd p) ...

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

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

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

8 Другие преобразования перемещения кода

8.1 Поднятие констант

Выражения, которые оказались константами, будут подняты до связываний символов — другими словами, они будут статически выделены в объектном файле — когда они при оценке приводят к упакованным значениям. Такие константы могут быть простыми числовыми константами, такими как число с плавающей запятой 42.0, или более сложными значениями, такими как константные замыкания.

Поднятие констант в верхний уровень уменьшает выделение памяти во время выполнения.

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

Примечания к массивам с плавающей точкой

Следующие семантики языка применяются конкретно к массивам с константными числами с плавающей точкой. (Под «константным массивом с плавающей точкой» понимается массив, состоящий целиком из чисел с плавающей точкой, известные на этапе компиляции. Распространённым случаем является литерал, такой как [| 42.0; 43.0; |].

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

8.2 Поднятие связываний let на верхнем уровне

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

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

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

9 Преобразования разворачивания

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

9.1 Развёртывание переменных замыканий

Это преобразование включено, если не указано -no-unbox-free-vars-of-closures.

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

Пример:

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

let f x0 x1 =
  let pair = x0, x1 in
  Printf.printf "foo\n";
  fun y ->
    fst pair + snd pair + y

После некоторых упрощений получается:

let f x0 x1 =
  let pair_0 = x0 in
  let pair_1 = x1 in
  Printf.printf "foo\n";
  fun y ->
    pair_0 + pair_1 + y

и затем:

let f x0 x1 =
  Printf.printf "foo\n";
  fun y ->
    x0 + x1 + y

Выделение пары было устранено.

Это преобразование не применяется, если оно приведёт к увеличению количества переменных замыкания в замыкании более чем в два раза по сравнению с исходным.

9.2 Развёртывание специализированных аргументов

Это преобразование включено, если не указано -no-unbox-specialised-args.

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

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

Пример:

После того, как компилятор предоставил следующий код, он встроит loop в f, а затем обнаружит, что inv является неизменным и всегда представляет пару, образованную путем добавления 42 и 43 к аргументу x функции f.

let rec loop inv xs =
  match xs with
  | [] -> fst inv + snd inv
  | x::xs -> x + loop2 xs inv
and loop2 ys inv =
  match ys with
  | [] -> 4
  | y::ys -> y - loop inv ys

let f x =
  Printf.printf "%d\n" (loop (x + 42, x + 43) [1; 2; 3])

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

let f x =
  let rec loop' xs inv_0 inv_1 =
    match xs with
    | [] -> inv_0 + inv_1
    | x::xs -> x + loop2' xs inv_0 inv_1
  and loop2' ys inv_0 inv_1 =
    match ys with
    | [] -> 4
    | y::ys -> y - loop' ys inv_0 inv_1
  in
  Printf.printf "%d\n" (loop' [1; 2; 3] (x + 42) (x + 43))

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

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

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

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

9.3 Развёртывание замыканий

Это преобразование по умолчанию не включено. Его можно включить, используя флаг -unbox-closures.

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

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

Простой пример:

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

let f x =
  let g y =
    x + y
  in
  (g [@inlined never]) 42

Распаковка замыкания приводит к тому, что значение x внутри g передается в качестве аргумента функции g, а не через её замыкание. Это означает, что замыкание g становится постоянным и может быть поднято на верхний уровень, устраняя выделение памяти во время выполнения.

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

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

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

Более сложный пример:

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

let foo c =
  let rec bar zs fv =
    match zs with
    | [] -> []
    | z::zs ->
      let rec baz f = function
        | [] -> []
        | a::l -> let r = fv + ((f [@inlined never]) a) in r :: baz f l
      in
      (map2 (fun y -> z + y) [z; 2; 3; 4]) @ bar zs fv
  in
  Printf.printf "%d" (List.length (bar [1; 2; 3; 4] c))

Код, полученный в результате применения -O3 -unbox-closures к этому коду, передаёт свободные переменные через аргументы функций, чтобы устранить всё выделение памяти для замыканий в этом примере (кроме тех, которые могут быть выполнены внутри printf).

10 Удаление неиспользуемого кода и значений

10.1 Удаление избыточных выражений let

Пасс упрощения удаляет неиспользуемые привязки let, если соответствующие определяющие выражения «не имеют побочных эффектов». Смотрите раздел «Обработка побочных эффектов» ниже для точного определения этого термина.

10.2 Удаление избыточных конструкций программы

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

10.3 Удаление неиспользуемых аргументов

Это преобразование по умолчанию включено только для специализированных аргументов. Его можно включить для всех аргументов, используя флаг -remove-unused-arguments.

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

10.4 Удаление неиспользуемых переменных замыканий

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

11 Другие преобразования кода

11.1 Преобразование ссылок, не выходящих за пределы области видимости, в переменные

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

11.2 Подстановка переменных замыканий специализированными аргументами

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

12 Обработка побочных эффектов

Оптимизаторы Flambda классифицируют выражения, чтобы определить, может ли выражение:

• вообще не нуждаться в вычислении; и/или
• быть продублированным.

Это делается путём формирования суждений о побочных эффектах и сопутствующих эффектах, которые могли бы быть выполнены при выполнении выражения. Побочные эффекты говорят о том, как выражение может повлиять на мир; сопутствующие эффекты говорят о том, как мир может повлиять на выражение.

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

Без побочных эффектов:

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

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

Только генеративные эффекты:

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

Произвольные эффекты:

Все остальные выражения.

Существует одна классификация для сопутствующих эффектов:

Без сопутствующих эффектов:

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

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

13 Компиляция статически размещённых модулей

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

14 Запрет оптимизации

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

15 Использование небезопасных операций

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

В частности, запрещается изменять любые значения (например, используя Obj.set_field или Obj.set_tag), которые не являются изменяемыми. (Значения, возвращаемые из C-заглушек, всегда обрабатываются как изменяемые.) Компилятор выведет предупреждение 59, если обнаружит такую запись, но не может предупредить во всех случаях. Вот пример кода, который вызовет предупреждение:

let f x =
  let a = 42, x in
  (Obj.magic a : int ref) := 1;
  fst a

Причина, по которой это небезопасно, заключается в том, что проход упрощения считает, что fst a содержит значение 42; и на самом деле оно должно быть, если целостность типов не нарушена небезопасными операциями.

Если необходимо написать код, который вызывает предупреждение 59, но код, по определению, является корректным, то Sys.opaque_identity можно использовать для обертывания значения перед выполнением небезопасных операций. Следует проявлять особую осторожность при этом, чтобы убедиться, что непрозрачность добавлена в нужном месте. Необходимо подчеркнуть, что это использование Sys.opaque_identity предназначено только для исключительных случаев. Его не следует использовать в обычном коде или для попыток направить оптимизатор.

В качестве примера, этот код вернет целое число 1:

let f x =
  let a = Sys.opaque_identity (42, x) in
  (Obj.magic a : int ref) := 1;
  fst a

Однако следующий код по-прежнему вернет 42:

let f x =
  let a = 42, x in
  Sys.opaque_identity (Obj.magic a : int ref) := 1;
  fst a

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

16 Словарь терминов

В этой главе руководства используется следующая терминология.

Место вызова

См. прямое место вызова и косвенное место вызова ниже.

Закрытая функция

Функция, тело которой не имеет свободных переменных, кроме своих параметров и любых, которые связаны с другими функциями в одном (возможно, взаимно-рекурсивном) объявлении.

Закрытие

Представление функции во время выполнения. Оно включает указатели на код функции вместе со значениями любых переменных, которые используются в теле функции, но фактически определены вне функции, в области видимости функции. Значения таких переменных, вместе известных как окружение, необходимы, поскольку функция может быть вызвана из места, где исходные привязки таких переменных больше не находятся в области видимости. Группа, возможно, взаимно-рекурсивных функций, определённых с использованием let rec, делят одно закрытие. (Примечание для разработчиков: в исходном коде Flambda закрытие всегда соответствует одной функции; набор закрытий относится к группе таких.)

Переменная закрытия

Член окружения, содержащегося в закрытии данной функции.

Константа

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

Закрытие константы

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

Определяющее выражение

Выражение e в let x = e in e’.

Прямое место вызова

Место в коде программы, где вызывается функция, и известно во время компиляции, какая функция это будет всегда.

Косвенное место вызова

Место в коде программы, где вызывается функция, но не известно, что это прямое место вызова.

Программа

Коллекция связываний символов, образующих определение единицы компиляции (т.е. файла .cmx).

Специализированный аргумент

Аргумент функции, который, как известно, всегда содержит определённое значение во время выполнения. Они вводятся инлайнером при специализации рекурсивных функций; и проходом unbox-closures. (См. раздел 23.4.)

Символ

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

Связывание символов

Аналогично выражению let, но работает на уровне символов, определённых в объектном файле. Адрес символа фиксирован, но он может быть привязан как к константным, так и к неконстантным выражениям.

Топ-уровень

Выражение в текущей программе, которое не заключено внутри объявления функции.

Переменная

Имя сущности, которой какое-то значение OCaml привязано выражением let, конструкцией сопоставления с образцом или аналогичным.