Оптимизатор зацикливается на комбинаторе неподвижной точки

[Mazdaywik]

Введение

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

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

Также полезно встраивать/прогонять присваивания и блоки. Присваивание пассивного выражения e-переменной при оптимизации просто имеет нулевую стоимость. Блоки тоже бывает полезно прогонять.

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

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

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

Воспроизведение проблемы

В комментариях к #160 затесался офтопик — пример написания комбинатора неподвижной точки на Рефале: #160 (comment). Возьмём оттуда пример кода и немножко его адаптируем:

$ENTRY Fact {
  s.N
    = <FakeInc s.N> : s.N^
    = <
        <Fix
          {
            s.Rec = {
              s.M s.N = s.M;
              s.M s.K = <s.Rec <FakeMul s.M s.K> <FakeInc s.K>>;
            };
          }
        >
        1 1
      >;
}

* http://www.wikiznanie.ru/ru-wz/index.php/Комбинатор_неподвижной_точки
*
* Версия комбинатора Y, которая может быть использована в вызовах-по-значению
* (определяется при помощи η-редукции):
*
*     Z = λf.(λx.f(λy.xxy))(λx.f(λy.xxy))
Fix {
  s.Func
    = <
        { s.F1 = <s.Func { e.A1 = <<s.F1 s.F1> e.A1> }> }
        { s.F2 = <s.Func { e.A2 = <<s.F2 s.F2> e.A2> }> }
      >;
}

$DRIVE Fix;

* Имитация intrinsic’ов
$INLINE FakeMul, FakeInc;

FakeMul {
  1 1 = 1;             1 2 = 2;             2 3 = 6;             6 4 = 24;
  24 5 = 120;          120 6 = 720;         720 7 = 5040;        5040 8 = 40320;
  40320 9 = 362880;    362880 10 = 3628800;

  s.X s.Y = <* s.X s.Y>;
}

FakeInc {
  0 = 1;    1 = 2;    2 = 3;    3 = 4;
  4 = 5;    5 = 6;    6 = 7;    7 = 8;
  8 = 9;    9 = 10;   10 = 11;

  s.X = <+ 1 s.X>;
}

$EXTERN Add, Mul;

Скачать: fixpoint.ref.txt.

Компиляция осуществлялась командой

rlc-core -C -OD fixpoint.ref --log=fixpoint.log

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

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

Присваивание в функции Fact преобразуется во вспомогательную функцию:

Fact=1 {
  s.N#2 = < <Fix {{&Fact\1 s.N#2}}> 1 1>;
}

$ENTRY Fact {
  s.N#1 = <Fact=1 <FakeInc s.N#1>>;
}

Функция Fact=1 принимает число и вычисляет факториал числа, на единицу меньшего. Если посмотреть на результат трансформации этой функции, получим такую красоту:

Fact=1 {
  1 = 1;
  2 = 1;
  3 = 2;
  4 = 6;
  5 = 24;
  6 = 120;
  7 = 720;
  8 = 5040;
  9 = 40320;
  10 = 362880;
  11 = 3628800;

  s.N#2 = <Fix\2\1 {{&Fix\2 {{&Fact\1 s.N#2}}}} <Mul 3628800 11> <Add 1 11>>;
}

Вычисления остановились на 11, поскольку дальше FakeMul и FakeInt вручную не просчитаны. При реализации интринсиков (#260) вычисления продолжались бы дальше.

Вот так это выглядит

Fact=1 {
  s.N#2 = <<Fix {{&Fact\1 s.N#2}}> 1 1>;
}

Fact=1 {
  s.N#2 = <<{{&Fix\1 {{&Fact\1 s.N#2}}}} {{&Fix\2 {{&Fact\1 s.N#2}}}}> 1 1>;
}

Fact=1 {
  s.N#2 = <<{{&Fact\1 s.N#2}} {{&Fix\1\1 {{&Fix\2 {{&Fact\1 s.N#2}}}}}}> 1 1>;
}

Fact=1 {
  s.N#2 = <{{&Fact\1\1 s.N#2 {{&Fix\1\1 {{&Fix\2 {{&Fact\1 s.N#2}}}}}}}} 1 1>;
}

Fact=1 {
  1 = 1;

  s.N#2 = <{{&Fix\1\1 {{&Fix\2 {{&Fact\1 s.N#2}}}}}} <FakeMul 1 1> <FakeInc 1>>;
}

Fact=1 {
  1 = 1;

  s.N#2 = <Fix\1\1 {{&Fix\2 {{&Fact\1 s.N#2}}}} 1 <FakeInc 1>>;
}

Fact=1 {
  1 = 1;

  s.N#2 = <Fix\1\1 {{&Fix\2 {{&Fact\1 s.N#2}}}} 1 2>;
}

Fact=1 {
  1 = 1;

  s.N#2 = <<{{&Fix\2 {{&Fact\1 s.N#2}}}} {{&Fix\2 {{&Fact\1 s.N#2}}}}> 1 2>;
}

Fact=1 {
  1 = 1;

  s.N#2 = <<{{&Fact\1 s.N#2}} {{&Fix\2\1 {{&Fix\2 {{&Fact\1 s.N#2}}}}}}> 1 2>;
}

Fact=1 {
  1 = 1;

  s.N#2 = <{{&Fact\1\1 s.N#2 {{&Fix\2\1 {{&Fix\2 {{&Fact\1 s.N#2}}}}}}}} 1 2>;
}

Fact=1 {
  1 = 1;
  2 = 1;

  s.N#2 = <{{&Fix\2\1 {{&Fix\2 {{&Fact\1 s.N#2}}}}}} <FakeMul 1 2> <FakeInc 2>>;
}

Fact=1 {
  1 = 1;
  2 = 1;

  s.N#2 = <Fix\2\1 {{&Fix\2 {{&Fact\1 s.N#2}}}} 2 3>;
}

Fact=1 {
  1 = 1;
  2 = 1;

  s.N#2 = <<{{&Fix\2 {{&Fact\1 s.N#2}}}} {{&Fix\2 {{&Fact\1 s.N#2}}}}> 2 3>;
}

Fact=1 {
  1 = 1;
  2 = 1;

  s.N#2 = <<{{&Fact\1 s.N#2}} {{&Fix\2\1 {{&Fix\2 {{&Fact\1 s.N#2}}}}}}> 2 3>;
}

Fact=1 {
  1 = 1;
  2 = 1;

  s.N#2 = <{{&Fact\1\1 s.N#2 {{&Fix\2\1 {{&Fix\2 {{&Fact\1 s.N#2}}}}}}}} 2 3>;
}

Fact=1 {
  1 = 1;
  2 = 1;
  3 = 2;

  s.N#2 = <{{&Fix\2\1 {{&Fix\2 {{&Fact\1 s.N#2}}}}}} <FakeMul 2 3> <FakeInc 3>>;
}

…

Полный лог

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

Возможные решения

Ничего не делать

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

• ❌ Проблема остаётся.
• ✔ Простота решения — пользователь просто не должен писать такие программы.
• ✔ Глубина оптимизации не страдает.

Вариант возможный и приемлемый. Если не найдётся решения лучше, оставим его.

Не назначать метки $DRIVE безымянным функциям

Простейшее решение, базовый вариант.

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

Вариант не рассматривается как решение, потому что есть варианты лучше.

Назначать метки $DRIVE только блокам и присваиваниям

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

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

<{ s.F = <s.F s.F> } { s.F = <s.F s.F> }>

Эта строчка кода, очевидно, зациклится.

• ✔ Зацикливание предотвращается.
• ✔ Тоже простое решение, хоть и несколько сложнее. При расстановке меток (Drive …) в рассахаривателе нужно различать сорта вложенных функций, например, по суффиксам.
• ❌ Снижение глубины оптимизаций. Основное исходное назначение прогонок и специализаций — оптимизации вызовов вида <Map { … } …>, а они пролетают.
  Спасти здесь может Автоматическая разметка оптимизируемых функций #252, обнаружить нерекурсивные вложенные функции и назначить им метку $DRIVE.

Приемлемое решение, но нужно мерять влияние на производительность.

Специализировать вложенные функции

Это решение близко к #160, оно будет побочным эффектом #160, но это не оно.

При условии реализации #251 любая функция, которую можно прогнать полностью (т.е. без непустого остатка Func*n), сможет быть и проспециализирована. Поэтому вызов вложенной функции частично оптимизируется — информация сможет распространиться глубже, где она учтётся оптимизатором. А специализация будет (#253) безопасной.

• ✔ Зацикливание предотвращается.
• ✔ Решение будет побочным эффектом Специализация замыканий #160, при условии Специализация без шаблона #251 можно будет и аргумент делать статическим. Кстати, интересный вопрос: если не удастся специализировать со статическим аргументом, то надо попробовать проспециализировать с динамическим аргументом, но статическим контекстом.
• ⁉ Оптимизация глубже, чем у решения выше. Но на сколько?
• ❌ Зависит от задач Специализация замыканий #160, Специализация без шаблона #251 и Останавливать специализацию по отношению Хигмана-Крускала #253.
• ❌ Автоматическая разметка (Автоматическая разметка оптимизируемых функций #252) спасает это решение не хуже, чем предыдущее.

Пересмотреть подход к древесной оптимизации

А именно, при реализации #251 и #252 имеет смысл все оптимизируемые функции сначала специализировать, а потом прогонять «транзитные» экземпляры специализированных функций.

• ✔✔ Зацикливание предотвращается не только для безымянных функций, но и вообще. Можно помечать $INLINE и $DRIVE любые функции, к зацикливанию это не приведёт. Т.е. это решение более общего случая.
• ✔ Упростится пользовательский интерфейс — $INLINE станет не нужна, можно вообще использовать одно ключевое слово $OPT для любых оптимизируемых функций.
• ✔ Задача Специализация замыканий #160 — лишь частный этого решения.
• ❌ Существенно зависит от Специализация без шаблона #251 и Автоматическая разметка оптимизируемых функций #252. И вообще, такое решение превращает компилятор в суперкомпилятор 😎, хоть и ограниченный.
• ❌ Оптимизация получается медленнее. Во-первых, прогонка осуществляется во время специализации согласно Специализация без шаблона #251. Во-вторых, эта же прогонка будет выполняться и при сворачивании транзитных вызовов. Плюс не забываем про анализ Автоматическая разметка оптимизируемых функций #252.

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

UPD: Задача #314 посвящена именно этому решению.

[Mazdaywik]

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

Предлагаемое решение

Предлагается модифицировать алгоритм автоматической разметки так, чтобы он не вешал новые метки $DRIVE, а только «лечил» существующие — удалял лишние. Разметка осуществляется обходом графа. Корнем графа должны быть все прогоняемые функции, которые вызываются из непрогоняемых + функции, на которые берутся указатели. Обход выполняется только для прогоняемых функций.

• ✔ Точно решает проблему — стирает метки $DRIVE для тех функций, которые могут зациклиться.
• ✔ Более того, решает проблему не только с безымянными функциями, но и с функциями, которым пользователь явно назначил метку $DRIVE — метки $DRIVE становятся полностью безопасными.
• ❌ Некоторая потеря производительности — выполняется дополнительный проход разметки. Интересно замерить, на сколько.

[Mazdaywik]

Логика, удаляющая опасные $DRIVE, по быстродействию занимает сравнительно немного времени. Для получения профиля был запущен стандартный бенчмарк с параметром BENCH_FLAGS=-OD. Получен следующий профиль:

• benchmark-08.11.2020-23-43-59,00_profile_time.txt

Вот время выполнения функций из OptTree-AutoMarkup-Drive.ref:

SetDifference (9032) -> 1065.0 ms (1.18 %, += 32.02 %)                               rel step time 7.46
<unwrap closure>: InlineInlineReferences-Pass\1 (9032) -> 938.0 ms (1.04 %, += 37.53 %)   rel step time 55.45
OptTree-AutoMarkup-CureDrives=3\1 (9032) -> 376.0 ms (0.42 %, += 63.01 %)           rel step time 74.13
DoBasicVertexes (9032) -> 361.0 ms (0.40 %, += 64.24 %)                             rel step time 29.58
AugmentReferences\1 (9032) -> 356.0 ms (0.40 %, += 64.64 %)                         rel step time 2.63
<unwrap closure>: OptTree-AutoMarkup-CureDrives=3\1 (9032) -> 344.0 ms (0.38 %, += 65.40 %)   rel step time 67.82
AugmentReferences\1$1?1 (9032) -> 328.0 ms (0.36 %, += 67.26 %)                     rel step time 2.43
. . .
FunctionReferences (9032) -> 15.0 ms (0.02 %, += 99.67 %)                          rel step time 2.96
        32. #9032 - OptTree-AutoMarkup-Drive.ref

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