Универсальная древесная оптимизация $OPT

[Mazdaywik]

Мотивация

Имеющаяся схема древесной оптимизации слишком сложна. Во-первых, есть несколько ключевых слов, объявляющих функции, вызовы которых компилятор должен оптимизировать: $SPEC, $DRIVE, $INLINE. Причём для $SPEC пользователь должен понимать разницу между динамическими и статическими параметрами, а также сложные ограничения для последних. С метками $DRIVE и $INLINE всё ещё сложнее, т.к. различия между ними не синтаксические, а семантические. При неправильной пометке статического параметра мы получим синтаксическую ошибку. А при неправильной пометке функции как $DRIVE или $INLINE получим зацикливание.

В компиляторе есть механизм, позволяющий автоматически размечать оптимизируемые функции (#252). Но он пытается пометить для оптимизации все возможные функции, что может негативно сказаться на времени компиляции. Экспериментов с -OiDS и -OiDGS пока не выполнялось, поскольку разметка пока медленная, её код предстоит оптимизировать (#310).

Кроме того, сложный интерфейс командной строки — много разных опций (по алфавиту): -OA, -OD, -OI, (-Oi), -OS, -OT.

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

Интерфейс

Предлагается ввести единственное ключевое слово — $OPT, которым помечать функции, вызовы которых надо оптимизировать. Оно будет заменять собой объявления $SPEC, $DRIVE и $INLINE. Семантика у него будет следующая:

• Если данную функцию безопасно прогонять, то вызов будет прогнан.
• Иначе вызовы этой функции будут специализироваться.
• Специализированные экземпляры этой функции также будут неявно иметь метку $OPT, поэтому на следующих циклах оптимизации могут быть прогнаны (а может даже, и специализированы?).
• Режим оптимизации включается опцией -OT.
• Безымянные функции, присваивания и блоки, а также вспомогательные функции условий для режима -OC- неявно имеют метку $OPT.
• Опция -OA означает, что все пользовательские функции неявно имеют метку $OPT.

Детали реализации

• Для эффективного решения этой задачи специализатор должен осуществлять элементы прогонки (Специализация без шаблона #251). В этом случае будут оптимизироваться функции, которые ранее могли иметь только метку $INLINE.
  Можно показать, что если рекурсивная функция имела метку $INLINE и была специализирована с элементами прогонки, её экземпляры будут пригодны для обычной прогонки и встроятся в точку вызова на следующих итерациях.
• Проверка допустимости прогонки будет выполняться алгоритмом разметки (Автоматическая разметка оптимизируемых функций #252). В графе алгоритма разметки будут находиться только оптимизируемые функции (что сократит размер этого графа и повысит быстродействие), корнями графа будут вызовы оптимизируемых функций из всех неоптимизируемых + entry-функции + INIT + FINAL.
• Данный подход неточно упоминался в задачах Специализация без шаблона #251, Автоматическая разметка оптимизируемых функций #252 и ошибке Оптимизатор зацикливается на комбинаторе неподвижной точки #278. Здесь он сформулирован полностью.
• Интересный вопрос: продумать возможность специализации экземпляров — когда это не будет приводить к зацикливанию?

[Mazdaywik]

В пользу $DRIVE, $INLINE, $SPEC и -OD, -OS можно выдвинуть такой аргумент: они позволяют раздельно тестировать разные режимы оптимизации.

В компиляторе местами используется $SPEC без статических параметров для подавления оптимизации некоторых функций. Вместо этого можно придумать $NOOPT, но она одновременно и подавит прогонку. На сколько это разумно?

[Mazdaywik]

Неэквивалентность встраивания и специализации

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

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

Но глубина оптимизации в этом случае может быть меньше.

Пример:

Apply {
  s.Func e.Arg = <s.Func e.Arg>;
  (t.Func e.Bound) e.Arg = <Apply t.Func e.Bound e.Arg>;
}

$INLINE Apply;

Map {
  t.Fn t.Next e.Rest = <Apply t.Fn t.Next> <Map t.Fn e.Rest>;
  t.Fn /* empty */ = /* empty */;
}

$SPEC Map t.FN e.items;

$ENTRY Test {
  s.Format e.Numbers = <Map (&Format s.Format) e.Numbers>;
}

Format {
  COMMA s.Number = <Symb s.Number> ',';
  COLON s.Number = <Symb s.Number> ':';
}

$DRIVE Format;

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

(Можно было вместо $DRIVE Format; написать вложенную функцию, но нагляднее расписать так.)

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

$ENTRY Test {
  s.Format e.Numbers = <Map@1 s.Format e.Numbers>;
}

Map@1 {
  s.Format t.Next e.Rest
    = <Apply (&Format s.Format) t.Next> <Map (&Format s.Format) e.Rest>;
  s.Format /* empty */ = /* empty */;
}

Далее два прохода прогонки раскроют функцию Apply:

Map@1 {
  s.Format t.Next e.Rest
    = <Format s.Format t.Next> <Map (&Format s.Format) e.Rest>;
  s.Format /* empty */ = /* empty */;
}

Функция Format прогоняется!

Map@1 {
  COMMA s.Number e.Rest
    = <Symb s.Number> ',' <Map (&Format COMMA) e.Rest>;

  COLON s.Number e.Rest
    = <Symb s.Number> ':' <Map (&Format COLON) e.Rest>;

  s.Format t.Next e.Rest
    = <Format*3 s.Format t.Next> <Map (&Format s.Format) e.Rest>;

  s.Format /* empty */ = /* empty */;
}

Format*3 { }

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

Map@1 {
  COMMA s.Number e.Rest  = <Symb s.Number> ',' <Map@2 e.Rest>;
  COLON s.Number e.Rest = <Symb s.Number> ':' <Map@3 e.Rest>;
  s.Format t.Next e.Rest = <Format*3 s.Format t.Next> <Map@1 s.Format e.Rest>;
  s.Format /* empty */ = /* empty */;
}

Map@2 {
  t.Next e.Rest
    = <Apply (&Format COMMA) t.Next> <Map (&Format COMMA) e.Rest>;

  /* empty */ = /* empty */;
}

Map@3 {
  t.Next e.Rest
    = <Apply (&Format COLON) t.Next> <Map (&Format COLON) e.Rest>;

  /* empty */ = /* empty */;
}

Вызовы Apply встроятся:

Map@2 {
  t.Next e.Rest = <Format COMMA t.Next> <Map (&Format COMMA) e.Rest>;
  /* empty */ = /* empty */;
}

Map@3 {
  t.Next e.Rest = <Format COLON t.Next> <Map (&Format COLON) e.Rest>;
  /* empty */ = /* empty */;
}

Вызовы Format прогонятся:

Map@2 {
  s.Number e.Rest = <Symb s.Number> ',' <Map (&Format COMMA) e.Rest>;
  t.Next e.Rest = <Format*3 COMMA t.Next> <Map (&Format COMMA) e.Rest>;
  /* empty */ = /* empty */;
}

Map@3 {
  s.Number e.Rest = <Symb s.Number> ':' <Map (&Format COLON) e.Rest>;
  t.Next e.Rest = <Format*3 COLON t.Next> <Map (&Format COLON) e.Rest>;
  /* empty */ = /* empty */;
}

Прогонять дальше нечего, проход специализации замкнёт циклы:

Map@1 {
  COMMA s.Number e.Rest  = <Symb s.Number> ',' <Map@2 e.Rest>;
  COLON s.Number e.Rest = <Symb s.Number> ':' <Map@3 e.Rest>;
  s.Format t.Next e.Rest = <Format*3 s.Format t.Next> <Map@1 s.Format e.Rest>;
  s.Format /* empty */ = /* empty */;
}

Map@2 {
  s.Number e.Rest = <Symb s.Number> ',' <Map@2 e.Rest>;
  t.Next e.Rest = <Format*3 COMMA t.Next> <Map@2 e.Rest>;
  /* empty */ = /* empty */;
}

Map@3 {
  s.Number e.Rest = <Symb s.Number> ':' <Map@3 e.Rest>;
  t.Next e.Rest = <Format*3 COLON t.Next> <Map@3 e.Rest>;
  /* empty */ = /* empty */;
}

Получилась очень красивая картинка: режим форматирования проверяется в единственном вызове Map@1, далее крутятся циклы с известными режимами. Специализация прошла настолько глубоко, на сколько возможно.

---

А теперь рассмотрим другую картину:

$SPEC Apply; /* с прогонкой */

Первый шаг тот же:

$ENTRY Test {
  s.Format e.Numbers = <Map@1 s.Format e.Numbers>;
}

Map@1 {
  s.Format t.Next e.Rest
    = <Apply (&Format s.Format) t.Next> <Map (&Format s.Format) e.Rest>;
  s.Format /* empty */ = /* empty */;
}

Далее, Apply специализируется:

Map@1 {
  s.Format t.Next e.Rest
    = <Apply@1 s.Format t.Next> <Map (&Format s.Format) e.Rest>;
  s.Format /* empty */ = /* empty */;
}

Apply@1 {
  s.Format t.Next = <Apply &Format s.Format t.Next>
}

Прогонять здесь нечего, выполняется проход специализации:

Map@1 {
  s.Format t.Next e.Rest
    = <Apply@1 s.Format t.Next> <Map@1 s.Format e.Rest>;
  s.Format /* empty */ = /* empty */;
}

Apply@1 {
  s.Format t.Next = <Apply@2 s.Format t.Next>
}

Apply@2 {
  s.Format t.Next = <Format s.Format t.Next>
}

Здесь уже может прогнаться Format:

Apply@2 {
  COMMA s.Number = <Symb s.Number> ',';
  COLON s.Number = <Symb s.Number> ':';
  s.Format t.Next = <Format*3 s.Format t.Next>;
}

Дальше нечего прогонять и нечего специализировать. Проход авторазметки пометит функции Apply@1 и Apply@2 для прогонки. Они прогонятся:

Map@1 {
  COMMA s.Number e.Rest  = <Symb s.Number> ',' <Map@1 COMMA e.Rest>;
  COLON s.Number e.Rest  = <Symb s.Number> ':' <Map@1 COLON e.Rest>;
  s.Format t.Next e.Rest  = <Format*3 s.Format t.Next> <Map@1 s.Format e.Rest>;
  s.Format /* empty */ = /* empty */;
}

Рекурсивные вызовы Map@1 не проспециализированы полностью.

Что делать?

• Можно смириться с тем, что глубина оптимизации будет меньше, хоть это и обидно.
• Можно выполнять повторную специализацию экземпляров. Для этого должен быть изменён подход к специализации — Интринсики и зацикливание специализатора #320 (comment).
• Можно сохранить режим встраивания, реализовав для него безопасную авторазметку (Автоматическая разметка оптимизируемых функций #252 (comment)).

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

Кстати, ту же проблему будет иметь и дефорестация (#165). Вызовы Apply проспециализируются, функции-конфигурации прогонятся и остаточная программа будет эквивалентна функции Map@1. Но тут тоже поможет повторная дефорестация программы.

[Mazdaywik]

Специализация интерпретаторов без $INLINE

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

$SPEC Int (e.DEFS) (e.CODE) e.data;

где e.DEFS — список определений функций, например, вида

e.Defs ::= (s.FuncName e.Body)*

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

Суть в том, что у нас есть e.DEFS, т.е. язык поддерживает операцию вызова функции. Как она будет реализована? Скорее всего, так:

… <Int (e.Defs) (<Lookup s.FuncName e.Defs>) e.data> …

где функция Lookup будет реализована примерно так:

$INLINE Lookup;

Lookup {
  s.FuncName (s.FuncName e.Body) e._ = e.Body;
  s.FuncName t._ e.Defs = <Lookup s.FuncName e.Defs>;
}

(ветки с пустым списком определений нет, т.к. рассматриваем код, который встроен в программу и должен быть корректен)

Если функция Lookup объявлена как $INLINE, то она будет встроена за несколько последовательных шагов прогонки. После чего <Int (…) (…) …> проспециализируется по константному списку определений и константному телу вызванной функции. Всё получается красиво и эффективно.

Если вместо встраивания используется специализация, то функция Lookup будет развёрнута в несколько нерекурсивных экземпляров за несколько проходов специализации, которые перемежаются как минимум одним проходом прогонки. Уже медленнее. Но хуже другое. Вернёмся к вызову

… <Int (e.Defs) (<Lookup s.FuncName e.Defs>) e.data> …

Функция Int проспециализируется в экземпляр с константным e.DEFS и тривиальным (в виде e-переменной e.Call) e.CODE! Т.е. получится частично проспециализированный экземпляр. В исходном интерпретаторе ветвление осуществляется по параметру e.CODE, в частично проспециализированном оно и останется. Т.е. фактически интерпретатор почти как есть упадёт в остаточную программу.

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

Но, даже если и будет реализована повторная специализация экземпляров, проблем с быстродействием она не решит. Исходный вариант с $INLINE полностью раскрывался за несколько последовательных проходов прогонки. Предлагаемый вариант потребует несколько проходов специализации для построения транзитных экземпляров + проход разметки и повторной прогонки со специализацией. Если в интерпретируемой программе есть несколько последовательных вызовов функции (функция A вызывает B, B вызывает C, C — D…), то каждый следующий вызов будет специализироваться после следующего «большого цикла» оптимизации.

Что делать?

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

В предыдущем комментарии предлагалось три варианта:

• Смириться с тем, что глубина оптимизации ухудшится.
• Сделать повторную специализацию экземпляров. Выше показано, что это не эффективно.
• Распознавать встраиваемые функции и вешать на них $INLINE.

Но можно придумать и ещё:

• Разрешать небезопасную конструкцию $INLINE в дополнение к $OPT.
• Выполнять дефорестацию (см. далее).
• Написать вообще полноценный суперкомпилятор, а не попытки имитировать его логику последовательными проходами.

Дефорестация (#165) иногда работает

В примере выше с вызовом функции

… <Int (e.Defs) (<Lookup s.FuncName e.Defs>) e.data> …

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

… <Int (e.Defs) (e.Body) e.data> …

которое уже будет нормально оптимизироваться.

Впрочем, дефорестация не решает проблемы, описанной в предыдущем комментарии, где встраивание с последующей прогонкой распространяют информацию по горизонтали. И решить не может в принципе, т.к. ради конечного числа конфигураций дефорестация как раз и жертвует горизонтальным распространением информации. Можно распространять информацию «меньшего» типа (e → ε, t → s…), но это будет работать только для ограниченного числа случаев. Да и то не везде. В примере с Map горизонтального распространения информации не будет, т.к. правая часть <Apply …> <Map …> сразу развалится на две конфигурации <Apply …> и <Map …>, которые будут преобразовываться независимо.

А если в дефорестатор добавить отношение Хигмана-Крускала, то будет уже полноценный суперкомпилятор 😎. Но примеру с Map это тоже не поможет.

[Mazdaywik]

Дефорестация не работает

Вызов Int с Lookup будет рекурсивным:

Int {
  …
  … <Int (e.Defs) (<Lookup s.FuncName e.Defs>) e.data> …
  …
}

А для рекурсивных вызовов дефорестатор принудительно вставляет команды обобщения:

Int {
  …
  … <Int (e.Defs) (<$cut <Lookup s.FuncName e.Defs>>) e.data> …
  …
}

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

[Mazdaywik]

Проблема со специализацией inline-функций и её решение

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

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

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

Проблема

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

Далее будем обозначать S — специализируемая функция, I — встраиваемая функция, D — прогоняемая функция.

При встраивании встраиваемой функции возможны два эффекта:

• для вызовов вида <S … <I …> …> встраиваемая функция может замениться на нетривиальное (не e-переменная) выражение, по которому будет проспециализирован вызов S;
• для правых частей вида <I …v.X…> … <S …v.X…> вызов I может замениться на вызов прогоняемой функции, правая часть примет вид <D …v.X…> … <S …v.X…>, что может привести к сужению переменной v.X и уточнению аргумента S.

При специализации встраиваемой функции оба эффекта будут нивелированы:

• обе функции композиции <S … <I …> …> будут проспециализированы независимо — <S@1 … <I@1 …> …>, последующая прогонка I@1 даст тот же результат, что и встраивание I, но вызов S@1 уже проспециализирован с более общим аргументом;
• в правой части <I …v.X…> … <S …v.X…> оба вызова опять будут проспециализированы независимо — <I@1 …v.X…> … <S@1 …v.X…>, прогонка I@1 → D тоже распространит информацию (сужение) слишком поздно.

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

Решение проблемы

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

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

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

Пример.

$ENTRY Test {
  s.X = <PadAndCut s.X>;
}

$INLINE PadAndCut;

PadAndCut {
  s.1 s.2 s.3 s.4 s.5 e._cut = s.1 s.2 s.3 s.4 s.5;
  e.Short = <PadAndCut e.Short ' '>;
}

Функция PadAndCut от длинных строк оставляет первые 5 символов, короткие дополняет пробелами до 5 символов. Очевидно, встраивание этой функции безопасно и функция Test после оптимизации примет вид

$ENTRY Test {
  s.X = s.X '    ';
}

Но при попытке специализации мы получим сигнатуры <PadAndCut s.X> и <PadAndCut s.X ' '>, которые обобщатся до <PadAndCut s.1 e.2> и получим программу (в случае предполагаемой перестройки сверху и расширенной специализации):

$ENTRY Test {
  s.X = <PadAndCut@1 s.X>;
}

PadAndCut@1 {
  s.1 s.2 s.3 s.4 s.5 e._ = s.1 s.2 s.3 s.4 s.5;
  s.1 e.2 = <PadAndCut@1 s.1 e.2 ' '>;
}

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

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

• <S …<I …> …> → (специализация I) → <S … <I@1 …> …> → (прогонка) → <S … expr …> → (специализация S);
• <I …v.X…> … <S …v.X…> → (специализация I) → <I@1 …v.X…> … → (прогонка) → <D …v.X…> … <S …v.X…> → (прогонка с сужением v.X → expr) → … <S …expr…> → (специализация S).

Всё бы хорошо, да только как их отличить? Как при специализации отличить вызовы I от вызовов S? Оказывается, просто.

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

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

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

повторять до неподвижной точки:
    повторять до неподвижной точки:
       проход прогонки
    проход специализации

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

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

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

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

Пример:

$ENTRY Test {
  s.1 = <Double <Double s.1 s.1 s.1>>;
}

Double {
  /* empty */ = /* empty */;
  s.x e.y = s.x s.x <Double e.y>;
}

$INLINE Double;

Очевидно, встраивание здесь безопасно и сделает функцию Test одношаговой.

Внешний вызов Double в Test исходно вызывается с тривиальным аргументом, поэтому проспециализирован быть не может. Поэтому проспециализирован будет только внутренний вызов, будут построены 4 экземпляра:

$ENTRY Test {
  s.1 = <Double <Double@1 s.1>>;
}

Double {
  /* empty */ = /* empty */;
  s.x e.y = s.x s.x <Double e.y>;
}

Double@1 { s.1 = s.1 s.1 <Double@2 s.1> }
Double@2 { s.1 = s.1 s.1 <Double@3 s.1> }
Double@3 { s.1 = s.1 s.1 <Double@4> }
Double@4 { = }

Проход пометки пометит все эти экземпляры как $DRIVE, они окажутся встроены, получим

$ENTRY Test {
  s.1 = <Double s.1 s.1 s.1 s.1 s.1 s.1>;
}

Double {
  /* empty */ = /* empty */;
  s.x e.y = s.x s.x <Double e.y>;
}

Дальше будет кое-что забавное. Три цикла локальной специализации дадут

$ENTRY Test {
  s.1 = <Double@5 s.1>;
}

Double@5 { s.1 = s.1 s.1 <Double@6 s.1> }
Double@6 { s.1 = s.1 s.1 <Double@7 s.1> }
Double@7 { s.1 = s.1 s.1 <Double s.1 s.1 s.1> }

Для вызова в Double@7 сигнатура известна — это Double@1. А прогонщик уже знает Double@1 и будет её прогонять:

$ENTRY Test {
  s.1 = <Double@5 s.1>;
}

Double@5 { s.1 = s.1 s.1 <Double@6 s.1> }
Double@6 { s.1 = s.1 s.1 <Double@7 s.1> }
Double@7 { s.1 = s.1 s.1  s.1 s.1 s.1 s.1 s.1 s.1 }

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

$ENTRY Test {
  s.1 = s.1 s.1 s.1 s.1 s.1 s.1 s.1 s.1 s.1 s.1 s.1 s.1;
}

Выводы

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

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

Как показано выше, универсальная оптимизация не везде способна заменить встраивание. Поэтому директиву $INLINE в целом можно оставить, однако приправив её синтаксической солью (например, $UNSAFEINLINE). Несложно составить пример, когда можно безопасно пометить функцию как $DRIVE, а значит, тоже можно добавить и $UNSAFEDRIVE, которую оптимизатор не стирает (в отличие от обычной $DRIVE).

Пример на $UNSAFEDRIVE.

$UNSAFEDRIVE PadAndCut;

PadAndCut {
  Z       s.1 s.2 s.3 s.4 s.5 e._ = s.1 s.2 s.3 s.4 s.5;
  (t.X)   e.Small = <PadAndCut t.X e.Small ' '>;
}

Можно также придумать и $UNSAFESPEC, для которой не выполняется проверка на Хигмана-Крускала, только зачем?

В общем, $OPT делается в первую очередь, $UNSAFE… — если в них появится потребность.

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

[Mazdaywik]

«Ациклическая суперкомпиляция» вместо прогонки и встраивания

Используемый подход ограничен

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

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

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

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

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

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

Но для прогонки функция должна получить метку $DRIVE, для встраивания — $INLINE, и эти пометки должны выставляться автоматически и безопасно. Для расстановки меток $DRIVE существует специальный инструмент, который выбирает безопасную разметку путём довольно хитрого анализа графа вызовов. А для расстановки меток $INLINE нет подходящего инструмента.

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

Всё бы ничего, да только что-то уж слишком всё костыльно.

• Для выполнения прогонки нужен отдельный этап разметки — нужно выбрать среди оптимизируемых те функции, которые безопасно прогонять. Проход разметки для специализации концептуально не нужен — при развитии специализации (Специализация без шаблона #251) от него можно избавиться.

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

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

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

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

• Есть функции, которые находятся в промежуточном состоянии между прогонкой и встраиванием:

  OneOf {
    t.SearchFor t.SearchFor e.Set = True;
    t.SearchFor t.Other e.Set = <OneOf t.SearchFor e.Set>;
    t.SearchFor /* пусто */ = False;
  }
  

  Её формат <OneOf t.SearchFor e.Set>. По отношению к переменной t.SearchFor она должна прогоняться, по отношению к e.Set — встраиваться. В задаче Разметка неразменных аргументов для прогонки #231 предлагается новый костыль — ручная разметка формата, где прогонять можно, а где — нет.

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

• Резюме: множество жутких нагромождений для борьбы с несовершенством инструмента. Не проще ли заменить сам инструмент на более совершенный?

Новый предлагаемый подход

Предлагается полностью изменить алгоритм прогонки!

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

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

Теперь самое интересное: как построить этот граф. Строится он по следующему алгоритму:

• Выбирается очередной подлежащий оптимизации вызов функции. Функция прогоняется — получаем набор решений — сужений + замену дырки на результат шага выполнения. Если замена выполняется однозначно без сужений — решение единственное. Если прогнать нельзя — решение единственное — подстановка в дырку исходного холодного вызова.
• Для каждого из решений строятся потомки текущей вершины. Им в историю добавляется родительская конфигурация = вся правая часть.
• Если дочерняя конфигурация похожа на одну из своих родительских — в графе выполняется перестройка, причём перестройка сверху! В нашем случае перестройка сводится к тому, что вызов, который был активен у освистываемого предка, делается холодным. Делается попытка прогонки следующего вызова.

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

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

Впрочем, возможны и ложные срабатывания. Например:

$ENTRY Test {
  e.x t.a = <B t.a> <F e.x>;
}

B { t.x = (t.x) }

F {
  t.n e.r = <B t.n> <F e.r>;
  /* empty */ = /* empty */;
}

При прогонке получим такую историю:

<B t.a> <F e.x>
      ↓
(t.a) <F e.x>
      ↓
(t.a) <B t.1> <F e.2>

Свисток! Нужно откатиться назад и заморозить вызов <B t.a>, ведь именно он был тогда активен. Получаем:

<*B t.a*> <F e.x>
     ↓
<*B t.a*> <B t.1> <F e.2>

Опять свисток! Но вызов B был заморожен, значит, нужно заморозить вызов F.

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

Возможно, тут поможет какая-то дополнительная разметка, позволяющая различать вызовы, присутствовавшие в правой части изначально (как <B t.a>), и вызовы, возникшие во время развёртки (как <B t.1>). Но это уже детали реализации.

Функции, предназначенные для прогонки, будут раскрываться в рекурсивные вызовы и поэтому сразу же помечаться холодными. Так что, вызовы вроде <Map {{ … }} e.X> прогонка не поменяет. Но вызов <Map {{ … }} s.1 s.2 s.3> будет полностью оптимизирован!

Предложенный подход полностью решает все вышеперечисленные проблемы.

• Функция Apply будет полностью развёртываться на этапе прогонки, никаких экземпляров для неё строиться не будет.
• Можно показать, что в примере <Map (&Format s.Format) e.Numbers> программа тоже получится полностью эффективной — в экземпляре Map@1 вызовы Apply развернутся, вызов Format прогонится, вызовы Map заморозится. Затем специализация успешно построит экземпляры Map@2 и Map@3.
• Вызов Lookup с константной программой в интерпретаторе будет раскрываться на стадии прогонки, т.к. цепочка вызовов в истории будет уменьшать свой аргумент. Напротив, вызов <Lookup s.FuncName e.Defs> замёрзнет.
• Функция OneOf с константным множеством (вроде <OneOf s.Tag Number Char Ident>) раскроется в конечный граф с сужениями, ибо каждый шаг уменьшает аргумент и функции не будут гомеоморфно вкладываться.

Более того, устраняются костыли:

• Не нужно будет эвристически размечать прогоняемые функции, проход разметки будет не нужен.
• Пропадёт различие между $DRIVE и $INLINE.
• Прогонщик за один проход будет раскрывать все большинство (см. про ложное срабатывания) пригодных для прогонки вызовов. Повторные проходы до неподвижной точки здесь уже будут не нужны.
• Проход разметки будет не нужен, цикл до неподвижной точки прогонки будет не нужен. Критерием завершения проходов оптимизации будет отсутствие активных функций — не «залоченных» и не «замороженных». Логика оптимизации упростится, потребность в DSL исчезнет.
• Различие «локальной» и обычной специализации и дополнительный цикл — лютые костыли. Их не будет.
• Все виды функций, помеченных как $OPT, будут оптимизироваться однообразно. Впрочем, отличие между прогонкой и встраиванием нужно будет сохранять. Например, в предложениях с условиями в правых частях имеет смысл допускать только встраивания (раскрытия без сужений).
• Не будет создаваться избыточных экземпляров для тех функций, которые потом прогонятся. Или меньше будет создаваться.

Впрочем, есть и недостатки:

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

Вывод

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

Таким образом, универсальная древесная оптимизация требует двух механизмов:

• Специализация без шаблона (Специализация без шаблона #251).
• Ациклическая суперкомпиляция при прогонке.

В результате механизм разметки, в обоих имеющихся ипостасях, уходит в прошлое.

UPD

Во-первых, пример на ложное срабатывание просчитан неправильно. В истории

<B t.a> <F e.x>
      ↓
(t.a) <F e.x>
      ↓
(t.a) <B t.1> <F e.2>

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

(t.a) <*F e.x*>

Во-вторых, дополнение про $UNSAFE…. Этими расширениями можно дополнить и рассматриваемый подход. Особенность будет в том, что их вызовы в историю не добавляются (или добавляются с пометкой).

UPD2

Задача из комментария была вынесена в #340.

[Mazdaywik]

Псевдокомментарии

Вместо ключевого слова $OPT предлагается добавить псевдокомментарий *$OPT.

Мотивация

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

Опыт C/C++

В языках C/C++ есть ключевые слова для управления оптимизацией программы: register и inline (C99+). Согласно Стандартам, компилятор их может проигнорировать, и современные оптимизирующие компиляторы их, как правило, игнорируют. Сам компилятор решает, можно ли переменную разместить в регистре или встроить функцию, вес ручной разметки при принятии решения небольшой (читал на Хабре, вроде у d34df00d’а). Но их приходится поддерживать ради обратной совместимости.

Псевдокомментариями (см. #195 (comment)) имеет смысл оформлять пометки, которые одна версия может обработать и принять к сведению, а другая — проигнорировать (для неё это будут комментарии).

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

Реализация

Предлагается такой синтаксис:

OptMarkup ::= Keyword Name { ',' Name } [;]
Keyword ::= '*$OPT'

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

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

Если функция с именем, присутствующим в *$OPT, не определена, то выдаётся предупреждение, а пометка игнорируется. Следует обратить внимание на случай глобальной оптимизации — при объединении единиц трансляции в одну может появиться entry-функция с указанным именем. Поэтому чистка от избыточных *$OPT должна выполняться до объединения деревьев.

В дополнение к *$OPT предлагается реализовать другие псевдокомментарии с тем же синтаксисом: *$DRIVE, *$SPEC, *$NODRIVE, *$NOSPEC, *$NOOPT. Первые два псевдокомментария поддерживаются, однако реализуют несколько отличную семантику: игнорируются в классическом режиме, в расширенном полностью идентичны $DRIVE и $SPEC. Синтаксис и семантику следует унифицировать с *$OPT.

Пометки *$DRIVE и *$SPEC, соответственно, помечают функцию только для прогонки и только для специализации. Пометки *$NODRIVE, *$NOSPEC, *$NOOPT предназначены для режима -OA, запрещают соответствующие режимы оптимизации для соответствующих имён функций.

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

*$DRIVE Func
*$NOSPEC Func

имеет смысл: для режима -OA- функция помечается как прогоняемая (не специализируемая), для режима -OA+ запрещается специализация. В обоих случаях функция будет прогоняться (по возможности) и не будет специализироваться. Такая пометка совершенно осмысленна. Впрочем, для неё можно придумать ключевое слово *$DRIVEONLY. В отличие от основного синтаксиса синтаксис псевдокомментариев раздувать не так вредно.

А вот на пометки

*$DRIVE Func
*$DRIVE Func

*$DRIVE Func
*$NODRIVE Func

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