Специализация замыканий

[Mazdaywik]

Если дословно выполнить задания #122 и #126, оптимизатор не будет давать того результата, который хотелось бы (а будет немного хуже). Поясню на примере

Пример

/* Листинг 1 */

$INLINE Inline;
Inline {
  s.A s.B = { s.A = s.B; s.X = s.X; };
}

WithInline {
  = <Inline 'AB'>;
}

$DRIVE Drive;
Drive {
  'AB' = 'CD';
  'EF' = 'GH';
}

WithDrive {
  s.A e.1 s.B = { s.A = s.B; s.X = s.X; } <Drive s.A s.B>;
}

$SPEC Spec s.A e.2 s.B;
Spec {
  s.A e.2 s.B = { s.A = s.B; s.X = s.X; } e.2;
}

WithSpec {
  e.3 = <Spec 'A' e.3 'B'>;
}

Хотелось бы получить вот такой результат:

/* Листинг 2 */

WithInline {
  /* функция Inline встроилась */
  = { 'A' = 'B'; s.X = s.X; };
}

WithDrive {
  /* функция Drive прогналась */
  'A' e.1 'B' = { 'A' = 'B'; s.X = s.X; } 'CD';
  'E' e.1 'F' = { 'E' = 'F'; s.X = s.X; } 'GH';
}

WithSpec {
  /* Создан экземпляр Spec¹ для функции Spec */
  e.3 = <Spec¹ e.3>;
}

Spec¹ {
  e.2 = { 'A' = 'B'; s.X = s.X; } e.2;
}

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

Обессахариватель преобразует программу на Рефале-5λ (или Простом Рефале) в программу на базисном Рефале с условиями (#17) и конструктором каррирования. Сейчас условия нас не интересуют, а вот конструктор каррирования играет первостепенную роль.

Каррированием в математике (лямбда-исчислении, комбинаторной логике и смежных дисциплинах) называется представление функции из N аргументов x₁, x₂, …, x_N как функции одного аргумента x₁, которая возвращает функцию одного аргумента x₂, которая возвращает функцию одного аргумента x₃, … , которая возвращает функцию аргумента x_N, которая уже возвращает возвращаемое значение исходной функции.

Конструктором каррирования в промежуточном представлении называется узел (#ClosureBrackets e.ClosureContext), который в скомпилированном коде превращается в операцию создания замыкания. e.ClosureContext обязан начинаться с имени глобальной функции, остальная часть контекста должна быть пассивной — может состоять только из переменных, структурных и абстрактных скобок и атомов (хотя вроде ничего не должно сломаться, если там окажется вызов функции, но я не гарантирую). В псевдокоде конструктор каррирования будем обозначать как {{ &Func контекст }}, где &Func — имя некоторой глобальной функции.

На выходе из обессахаривателя листинг 1 превратится в

/* Листинг 3 */

$INLINE Inline;
Inline {
  s.A s.B = {{ &Inline\1 s.A s.B }};
}

Inline\1 {
  s.A s.B s.A = s.B;
  s.A s.B s.X = s.X;
}

WithInline {
  = <Inline 'AB'>;
}

$DRIVE Drive;
Drive {
  'AB' = 'CD';
  'EF' = 'GH';
}

WithDrive {
  s.A e.1 s.B = {{ &WithDrive\1 s.A s.B }} <Drive s.A s.B>;
}

WithDrive\1 {
  s.A s.B s.A = s.B;
  s.A s.B s.X = s.X;
}

$SPEC Spec s.A e.2 s.B;
Spec {
  s.A e.2 s.B = {{ &Spec\1 s.A s.B }} e.2;
}

Spec\1 {
  s.A s.B s.A = s.B;
  s.A s.B s.X = s.X;
}

WithSpec {
  e.3 = <Spec 'A' e.3 'B'>;
}

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

После оптимизации программа приобретёт следующий вид:

/* Листинг 4 */

* $INLINE Inline;
* Inline {
*   s.A s.B = {{ &Inline\1 s.A s.B }};
* }

Inline\1 {
  s.A s.B s.A = s.B;
  s.A s.B s.X = s.X;
}

WithInline {
  = {{ &Inline\1 'AB' }};
}

* $DRIVE Drive;
* Drive {
*   'AB' = 'CD';
*   'EF' = 'GH';
* }

WithDrive {
  'A' e.1 'B' = {{ &WithDrive\1 'AB' }} 'CD';
  'E' e.1 'F' = {{ &WithDrive\1 'EF' }} 'GH';
}

WithDrive\1 {
  s.A s.B s.A = s.B;
  s.A s.B s.X = s.X;
}

* $SPEC Spec s.A e.2 s.B;
* Spec {
*   s.A e.2 s.B = {{ &Spec\1 s.A s.B }} e.2;
* }

Spec\1 {
  s.A s.B s.A = s.B;
  s.A s.B s.X = s.X;
}

WithSpec {
  e.3 = <Spec¹ e.3>;
}

Spec¹ {
  e.2 = {{ &Spec\1 'AB' }} e.2;
}

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

Что делать

Для этого случая вполне можно создать решение ad hoc — обнаруживая подстановку в конструктор каррирования, сразу же пытаться построить специализированный вариант каррируемой функции. Задача облегчается тем, что имя переменной в конструкторе совпадает с именем переменной в каррируемой функции.
Достоинство: не зависит от задачи #126, сохраняет разметку контекста для отладки.
Недостаток: частично дублирующаяся логика.

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

Нюанс

Каркас оптимизатора, построенный в задаче #155, уже содержит логику оптимизации — удаляет конструкторы каррирования после угловой скобки:

<{{ &Func контекст }} аргумент> → <Func контекст аргумент>

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

Изначально это было сделано для упрощения оптимизации встраивания и прогонки. Вложенные функции по умолчанию являются прогоняемыми. Если снимать с них скобки каррирования внутри скобок вызова, то прогонщику достаточно будет рассматривать только вызовы вида <F …>. Если не снимать, то прогонщик должен рассматривать и вызовы <F …>, и вызовы <{{&F …}} …>.

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

Чтобы облегчить задачу специализации, можно отказаться от снятия скобок между проходами оптимизаторов. Хуже не будет, если снимать их в самый последний момент. С другой стороны, сохранение конструктора каррирования может даже упростить прогонщик. В вызовах <{{&F …}} …> функция F будет считаться всегда прогоняемой, а значит не потребуется отдельная пометка вложенных функций прогоняемых.

Важность

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

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

/* Листинг 5 */
$DRIVE Regex;
Regex {
  ('.' e.Regex) s.Any e.Text = <Regex (e.Regex) e.Text>;
  (s.C e.Regex) s.C e.Text = <Regex (e.Regex) e.Text>;
  (/* empty */) /* empty */ = Success;
  (e.Regex) e.Text = Fails;
}

WithDriveAndAssing {
  e.Text = <Message <Regex ('A.B.') e.Text>> : s.Msg = <Prout s.Msg e.Text>;
}

// Специально не встраиваемая и не прогоняемая
Message {
  Success = "Matched:";
  Fails = "Not matched:";
}

$SPEC MapReduce s.FUNC t.acc e.items;

/*
  На самом деле определение MapReduce несколько другое,
  с вспомогательной циклической функцией DoMapReduce.
  Тут она описана так для краткости.
*/
MapReduce {
  s.Fn t.Acc t.Next e.Items
    = <s.Fn t.Acc t.Next> : t.Acc^ e.Res
    = <MapReduce s.Fn t.Acc e.Items> : t.Acc^ e.ItemsRes
    = t.Acc e.Res e.ItemsRes;

  s.Fn t.Acc /* пусто */ = t.Acc;
}

В WithDriveAndAssign вызов функции Regex полностью прогонится, но подстановки переменной e.Text за присваивание не протекут. В случае MapReduce всё ещё хуже: за первое присваивание не протечёт подстановка s.Fn — вызов во втором присваивании будет в общем положении и не будет специализирован.

План

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

  $SPEC 〈переменные контекста〉­ e.arg;
  

  Динамический параметр — аргумент замыкания должен остаться не завёрнутым в скобки.
• Добавить поддержку одновременно прогоняемых и специализируемых функций — одновременное указание $INLINE/$DRIVE и $SPEC больше не должно быть ошибкой.
• Специализатор должен уметь оптимизировать вызовы Func*M, если имя Func — специализируемое. Функция Func*M@N должна образовываться путём вычёркивания первых M предложений.
• Добавлять (Spec …) в рассахаривателе.
• Вызывать TrySpecCall для замыканий.

[Mazdaywik]

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

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

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

[Mazdaywik]

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

Пусть специализируемая функция имеет вид:

$SPEC F (e.STATIC) e.dynamic;
F {
  (e.Static) e.Dynamic1 = … <F (e.Static) …> …;
  (e.Static) e.Dynamic2 = …;
}

Тогда её специализацию можно свести к встраиванию функции F′:

$INLINE F′;

F′ {
  e.Static = {
    e.Dynamic1 = … <<F′ e.Static> …> …;
    e.Dynamic2 = …;
  };
}

При этом вызовы <F ([static]) [dynamic]> надо будет заменить на <<F′ [static]> [dynamic]>.

Но это вовсе не значит, что задача потеряла актуальность. Ведь F′ скомпилируется в каррирование некоторой другой функции (назовём её F′\1):

$INLINE F′;

F′ {
  e.Static = {{ &F′\1 (e.Static) }};
}

F′\1 {
  (e.Static) e.Dynamic1 = … <<F′ e.Static> …> …;
  (e.Static) e.Dynamic2 = …;
}

Вызовы <<F′ [static]> [dynamic]> встроятся в <{{&F′\1 [static]}} [dynamic]>, в которых придётся специализировать конструктор каррирования.

Т.е. от специализации всё равно не убежать.

[Mazdaywik]

Я просто оставлю это здесь (чтобы не потерялось):

$ENTRY Go {
  = <Prout <Fact0 10>>
    <Prout <Fact1 10>>
    <Prout <Fact2 10>>
    <Prout <Fact3 10>>;
}

Fact0 {
  s.N
    = <+ 1 s.N> : s.N^
    = <
        <Fix0
          {
            s.Rec = {
              s.M s.N = s.M;
              s.M s.K = <s.Rec <* s.M s.K> <+ 1 s.K>>;
            };
          }
        >
        1 1
      >;
}

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


Fact1 {
  s.N
    = <+ 1 s.N> : s.N^
    = <
        <Fix1
          {
            s.Rec s.M s.N = s.M;
            s.Rec s.M s.K = <s.Rec <* s.M s.K> <+ 1 s.K>>;
          }
        >
        1 1
      >;
}

Fix1 {
  s.Func
    = <
        { s.F1 = { e.Arg = <s.Func { e.A1 = <<s.F1 s.F1> e.A1> } e.Arg> } }
        { s.F2 = { e.Arg = <s.Func { e.A2 = <<s.F2 s.F2> e.A2> } e.Arg> } }
      >;
}


Fact2 {
  s.N
    = <+ 1 s.N> : s.N^
    = <Fix2
        {
          s.Rec s.M s.N = s.M;
          s.Rec s.M s.K = <s.Rec <* s.M s.K> <+ 1 s.K>>;
        }
        1 1
      >;
}

Fix2 {
  s.Func e.InitArg
    = <
        <
          { s.F1 = { e.Arg = <s.Func { e.A1 = <<s.F1 s.F1> e.A1> } e.Arg> } }
          { s.F2 = { e.Arg = <s.Func { e.A2 = <<s.F2 s.F2> e.A2> } e.Arg> } }
        >
        e.InitArg
      >;
}


Fact3 {
  s.N
    = <+ 1 s.N> : s.N^
    = <Fetch-Fix
        1 1
        {
          s.Rec s.M s.N = s.M;
          s.Rec s.M s.K = <s.Rec <* s.M s.K> <+ 1 s.K>>;
        }
      >;
}

Fetch-Fix {
  e.InitArg s.Func
    = <
        <
          { s.F1 = { e.Arg = <s.Func { e.A1 = <<s.F1 s.F1> e.A1> } e.Arg> } }
          { s.F2 = { e.Arg = <s.Func { e.A2 = <<s.F2 s.F2> e.A2> } e.Arg> } }
        >
        e.InitArg
      >;
}

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

[Mazdaywik]

Над задачей буду работать только я, поскольку Дарья ушла в академический отпуск. Соответственно, веху study spring 2018 снимаю.

[Mazdaywik]

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

Специализация делает функцию на Рефале многоместной — местность, во-первых, определяется числом параметров в объявлении $SPEC, во-вторых, уточняется подставляемыми значениями на место статических параметров. Их может быть и меньше — статический параметр константен, и больше — на место статического параметра подставляется несколько переменных.

При генерации кода требуется многоместную функцию вновь сделать одноместной. Способ известен — если есть N штук e-параметров, то достаточно (N−1) из них завернуть в скобки.

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

Конструктор замыкания вида

{{ &Func params }}

для оптимизатора представляется в виде фиктивного вызова

<Func params e.@>

где e.@ — placeholder для фактического аргумента в момент будущего вызова. Этот параметр по определению динамический (ибо статические параметры в конктексте, т.е. внутри конструктора). И он так и останется e-переменной после преобразований. Поэтому после преобразований будет построена новая функция Func′ с новым аргументом params′ e.@. Ей будет соответствовать фиктивный вызов

<Func′ params′ e.@>

Параметр e.@ не будет завёрнут в скобки, потому что мы заворачиваем в скобки все параметры, кроме последнего. Если мы его сотрём, и заменим угловые скобки на двойные фигурные:

{{ &Func′ params′ }}

то получим специализированный конструктор замыкания.

[Mazdaywik]

Исключил из вехи, в задачу диплома не входит.

[Mazdaywik]

Это не учебная задача. Снял метку «study».

[Mazdaywik]

Эту задачу имеет смысл выполнять вместе с #259 и #263.

[Mazdaywik]

Конкретные шаги:

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

   $SPEC 〈переменные контекста〉­ e.arg;
   

   Динамический параметр — аргумент замыкания должен остаться не завёрнутым в скобки.
3. Добавить поддержку одновременно прогоняемых и специализируемых функций — одновременное указание $INLINE/$DRIVE и $SPEC больше не должно быть ошибкой.
4. Специализатор должен уметь оптимизировать вызовы Func*M, если имя Func — специализируемое. Функция Func*M@N должна образовываться путём вычёркивания первых M предложений.
5. Добавлять (Spec …) в рассахаривателе, вызывать TrySpecCall для замыканий.

Забавно, что задачу решает только пункт 5, всё остальное — доработка окружения (как часто и бывает с правками больших систем). Пункты 1 и 2 обязательны — сделать сразу последний пункт без этих правок невозможно. Тупо или не будет работать (будут получаться имена функций с двумя SUF), или будет порождаться некорректный код при стирании не той призрачной скобки.

Пункты 3 и 4 технически избыточны, и без их выполнения всё будет работать. Разрешать одновременную прогонку и специализацию (3) имеет смысл, поскольку теперь уже это будет поддерживаться на back-end’е (замыкания ведь они неявно $DRIVE). Синтаксическое ограничение теряет смысл. А не выполнить пункт 4 просто некрасиво, ведь если можно специализировать функцию Func (или Func\K), то нет никаких препятствий к специализации Func*N (или Func\K*N) — по формату она подходит (ибо просто вычеркнуты несколько предложений), а распространение информации при специализации углубит оптимизацию программы.

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

[Mazdaywik]

Вопрос: что делать, если при специализации замыкания полностью исчезает контекст? Тут есть существует два варианта:

• генерировать указатель на глобальную функцию или
• создавать объект замыкания из одного указателя, без контекста.

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

В идеале все оптимизации должны быть прозрачны: оптимизированная и неоптимизированная программы различаются только быстродействием. Но оптимизация прогонки может удалять шаги рефал-машины, а значит, вызов <Step> позволяет различать оптимизированные и неоптимизированные программы. Специализация замыканий позволит различать оптимизированные и неоптимизированные программы посредством вызова <Type s.Fn>.

$ENTRY Test {
  = <S 'abc'>;
}

$SPEC S e.ARG;

S {
  e.X
    = <Type { = e.X }>
    : {
        'Fg' s.F = <Prout 'Global function'>;
        'Fc' s.C = <Prout 'Closure'>;
      }
}

Вывод программы будет меняться в зависимости от ключа -OS.

Кроме того, замена специализированного замыкания без контекста усложнит исправление #276 (см. #276 (comment)),

[Mazdaywik]

Нужно различать два случая:

• специализация функций, создаваемых рассахаривателем (\n, :n, =n),
• специализация объектов замыканий {{ &F arg }}.

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

---

Убрать ошибку одновременной прогонки и специализации тоже легко. Но без специализации Func*n делать её как-то некрасиво.

[Mazdaywik]

Вместо того, чтобы тянуть вола за хвост, решил добить эту задачу. Правки в OptTree-Spec.ref оказались достаточно небольшими. Ради упрощения основного кода OptTree-Spec.ref специализация остаточных функций Func*n была оформлена на стадии подготовки, а не на стадии анализа вызова. Вместе с каждой функцией Func запоминаются для оптимизации все возможные Func*n.

Альтернативный вариант: распознавать не только вызовы с совпадающими именами, но и вызовы функций с суффиксами *n, такими, что если их удалить, получится имя специализируемой функции. Но такой вариант усложнил бы основной код, а для #253 усложнять код не надо.

Замеры производительности

Был выполнен стандартный бенчмарк на коммитах 4833a73 (до правок), 4fa2160 (рефакторинг Reduce и MapAccum) и потом на 421f48a (Fetch).

Компьютер: процессор Intel® Core™ i5-2430M? 2,40 ГГц, ОЗУ 8 Гбайт, диск SSD. ОС Windows 10 x64. Компилятор C++ — BCC 5.5.1.

Выполнялось 13 замеров со следующими опциями:

set RLMAKE_FLAGS=-X-ODS
set BENCH_FLAGS=-ODPR

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

На первой паре замеров получился измеримый прирост производительности, преимущественно за счёт -OR.

Замеры до:

• benchmark-1-before-13.05.2020-21-51-27,37.time.txt
• benchmark-1-before-13.05.2020-21-51-27,37_profile_count.txt
• benchmark-1-before-13.05.2020-21-51-27,37_profile_time.txt

Вторые замеры:

• benchmark-2-after-13.05.2020-22-08-10,25.time.txt
• benchmark-2-after-13.05.2020-22-08-10,25_profile_count.txt
• benchmark-2-after-13.05.2020-22-08-10,25_profile_time.txt

Прирост производительности:

• (Total refal time): 40,495 [40,427…40,803] → 38,601 [38,454…38,852], ускорение достоверное, 4,6 %.
• Step count: 47 378 468 → 42 972 636, уменьшилось на 9,2 %.

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

FilterPatternPos (9295) -> 3109.0 ms (5.42 %, += 5.42 %)                  rel step time 1.20
FilterResultPos (9295) -> 3085.0 ms (5.38 %, += 10.80 %)                  rel step time 1.30
Apply (9295) -> 3015.0 ms (5.25 %, += 16.05 %)                            rel step time 0.59
Map@3 (9295) -> 2320.0 ms (4.04 %, += 20.09 %)                            rel step time 0.87
Map (9295) -> 2132.0 ms (3.72 %, += 23.81 %)                              rel step time 0.88

Apply (9295) -> 4281069 (8.92 %, += 8.92 %)                               rel step time 0.59
Map@3 (9295) -> 2220450 (4.63 %, += 13.54 %)                              rel step time 0.87
FilterPatternPos (9295) -> 2163791 (4.51 %, += 18.05 %)                   rel step time 1.20
Map (9295) -> 2036608 (4.24 %, += 22.29 %)                                rel step time 0.88
FilterResultPos (9295) -> 1979949 (4.12 %, += 26.42 %)                    rel step time 1.30

После оптимизации:

FilterResultPos (1514) -> 3092.0 ms (5.83 %, += 5.83 %)                   rel step time 1.28
FilterPatternPos (1514) -> 2942.0 ms (5.55 %, += 11.37 %)                 rel step time 1.12
Map@3 (1514) -> 2239.0 ms (4.22 %, += 15.60 %)                            rel step time 0.83
OverlapItem (1514) -> 1937.0 ms (3.65 %, += 19.25 %)                      rel step time 1.35
Map@4 (1514) -> 1847.0 ms (3.48 %, += 22.73 %)                            rel step time 0.74

Map@3 (1514) -> 2222760 (5.10 %, += 5.10 %)                               rel step time 0.83
FilterPatternPos (1514) -> 2165982 (4.97 %, += 10.06 %)                   rel step time 1.12
Map@4 (1514) -> 2038816 (4.67 %, += 14.74 %)                              rel step time 0.74
FilterResultPos (1514) -> 1982038 (4.54 %, += 19.28 %)                    rel step time 1.28

Видно, что сначала были не прооптимизированы вызовы Map и Apply, а затем они прооптимизировались. Вот «виновная» функция:

refal-5-lambda/src/compiler/GST.ref

Lines 260 to 278 in d809981

	RejectTile {
	(e.Tiles) e.HeavyTileItems =
	<UnBracket
	<Reduce
	{
	(e.Tiles^) (s.CurIndexP s.CurIndexR s.ItemWeight s.Ident) =
	<Fetch
	e.Tiles
	<Pipe
	(&Map (&FilterPatternPos s.CurIndexP))
	(&Map (&FilterResultPos s.CurIndexR))
	{ e.Tiles^ = (e.Tiles); }
	>
	>;
	}
	(e.Tiles) e.HeavyTileItems
	>
	>;
	}

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

  RejectTile {
    (e.Tiles#1) e.HeavyTileItems#1
      = <UnBracket <Reduce@1 (e.Tiles#1) e.HeavyTileItems#1>>;
  }

  Reduce@1 {
    (e.#0) (s.CurIndexP#2 s.CurIndexR#2 s.ItemWeight#2 s.Ident#2) e.Tail#1
      = <Reduce@1
          <Fetch
            <Map@3 s.CurIndexP#2 e.#0>
            {{Pipe$2\1
              (&Map (&FilterResultPos s.CurIndexR#2)) (&RejectTile\1\1)
            }}
          >
          e.Tail#1
        >;
  
    t.Acc#1 = t.Acc#1;
  }

  RejectTile\1\1 {
    e.Tiles#3 = (e.Tiles#3);
  }

Map@3 это проптимизированный (&Map (&FilterPatternPos s.CurIndexP)). Второй вызов Map остался не оптимизирован. В оптимизированной версии мы получили:

  RejectTile {
    (e.Tiles#1) e.HeavyTileItems#1
      = <UnBracket <Reduce@1 (e.Tiles#1) e.HeavyTileItems#1>>;
  }

  Reduce@1 {
    (e.#0) (s.CurIndexP#2 s.CurIndexR#2 s.ItemWeight#2 s.Ident#2) e.Tail#1
      = <Reduce$1=1@1
          (e.Tail#1)
          <Fetch <Map@3 s.CurIndexP#2 e.#0> {{&Pipe$2\1@2 s.CurIndexR#2}}>
        >;
  
    t.Acc#1 = t.Acc#1;
  }

  Pipe$2\1@2 {
    s.CurIndexR#2 e.Arg#2
      = <Fetch <Map@4 s.CurIndexR#2 e.Arg#2> &RejectTile\1\1>;
  }

  RejectTile\1\1 {
    e.Tiles#3 = (e.Tiles#3);
  }

Видно, что не смотря на то, что вызов Fetch оптимизировать не удалось (его аргумент активный, а это пока не поддерживается — #230), замыкание {{&Pipe$2\1 …}} оптимизировать получилось, благодаря чему проспециализировался второй вызов (&Map (&FilterResultPos s.CurIndexR)).

И тут я подумал: а может попробовать специализировать и Fetch? Что из этого получится? Получился коммит 421f48a, который измеримого прироста по времени не дал. Замеры:

• benchmark-3-fetch-13.05.2020-22-41-58,15.time.txt
• benchmark-3-fetch-13.05.2020-22-41-58,15_profile_count.txt
• benchmark-3-fetch-13.05.2020-22-41-58,15_profile_time.txt

Метрики:

• (Total refal time): 38,601 [38,454…38,852] → 38,339 [38,142…39,012], 0,6 %, недостоверно. На самом деле, если посмотреть не 10-й, а 9-й по порядку замер, то верхняя граница доверительного интервала стала бы 38,488, т.е. результат был бы условно достоверным. Но даже если и так, разница слишком мала.
• Step count: 42972636 → 42693427, уменьшение на те же 0,6 %.

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

  RejectTile {
    (e.Tiles#1) e.HeavyTileItems#1
      = <UnBracket <Reduce@1 (e.Tiles#1) e.HeavyTileItems#1>>;
  }

  Reduce@1 {
    (e.#0) (s.CurIndexP#2 s.CurIndexR#2 s.ItemWeight#2 s.Ident#2) e.Tail#1
      = <Reduce$1=1@1
          (e.Tail#1) <Fetch@3 <Map@3 s.CurIndexP#2 e.#0> s.CurIndexR#2>
        >;
  
    t.Acc#1 = t.Acc#1;
  }

  Fetch@3 {
    e.Argument#1 s.CurIndexR#2 = <Pipe$2\1@2 s.CurIndexR#2 e.Argument#1>;
  }

  Pipe$2\1@2 {
    s.CurIndexR#2 e.Arg#2 = <Fetch@6 <Map@4 s.CurIndexR#2 e.Arg#2>>;
  }

  Fetch@6 {
    e.Argument#1 = (e.Argument#1);
  }

Выводы

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

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

• Back-end допускал функции, которые можно и прогонять, и специализировать. Теперь это поддерживает front-end (не сообщает об ошибке). Если функция прогналась не полностью и может быть специализирована, то специализируется остаток.
• Если блок или присваивание невозможно прогнать, то информация о переменных контекста сквозь него всё равно распространяется дальше. Рефакторинг MapAccum и Reduce это показал.

Закрываю задачу.