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

Глава 24 Оптимизация с помощью Flambda

1 Обзор

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

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

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

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

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

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

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

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

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

2 Параметры командной строки

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

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

-O2

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

-O3

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

-Oclassic

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

-inlining-report

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

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

-remove-unused-arguments

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

-unbox-closures

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

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

-inline

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

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

-inline-toplevel

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

-inline-branch-factor

Управляет оценкой модуля встраивания: насколько вероятно, что путь выполнения будет часто или редко используемым. См. раздел 24.3.5.

-inline-alloc-cost, -inline-branch-cost, -inline-call-cost

Управляют оценкой модулем встраивания потерь производительности во время выполнения, связанных с различными операциями. См. раздел 24.3.5.

-inline-indirect-cost, -inline-prim-cost

Аналогично.

-inline-lifting-benefit

Управляет встраиванием функторов на верхнем уровне. См. раздел 24.3.5.

-inline-max-depth

Максимальная глубина любого спекулятивного поиска встраивания. См. раздел 24.3.6.

-inline-max-unroll

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

-no-unbox-free-vars-of-closures

Не распаковывать переменные замыканий. См. раздел 24.9.1.

-no-unbox-specialised-args

Не распаковывать аргументы, по которым были специализированы функции. См. раздел 24.9.2.

-rounds

Число выполняемых проходов оптимизации. См. раздел 24.2.1.

-unbox-closures-factor

Коэффициент масштабирования при расчёте выгоды от использования -unbox-closures. См. раздел 24.9.3.

Примечания

• Набор параметров командной строки, относящихся к оптимизации, обычно следует задавать одинаковым для всего проекта. В настоящее время 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 ведёт себя так же, как в предыдущих версиях компилятора. (Код всё ещё может подвергаться дополнительным оптимизациям, отсутствовавшим в предыдущих версиях компилятора: функторы могут встраиваться, константы выносятся, а неиспользуемый код удаляется — всё это описано в других разделах этой главы. См. разделы 24.3.3, 24.8.1 и 24.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 mode», содержится текст на английском языке с описанием решений, принятых модулем встраивания.

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

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

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

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

let g x = f true x

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

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

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

-inline-alloc-cost

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

-inline-branch-cost

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

-inline-call-cost

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

-inline-indirect-cost

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

-inline-prim-cost

Стоимость примитива. К примитивам относятся, в частности, арифметические операции и доступ к памяти.

(Значения по умолчанию описаны ниже в разделе 24.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 Перенос констант

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

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

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

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

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

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

8.2 Перенос привязок let верхнего уровня

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

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

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

9 Преобразования распаковки

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

9.1 Распаковка переменных замыканий

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

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

Пример:

В следующем коде компилятор обнаруживает, что замыкание, возвращаемое функцией 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.

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

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

Пример:

Получив следующий код, компилятор встроит 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. (См. раздел 24.4.)

Символ

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

Привязка символа

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

Верхний уровень

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

Переменная

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