Недостаточная глубина оптимизации при поочерёдном выполнении прогонки и специализации

[Mazdaywik]

Задача блокирует задачи #260, #252, #253.

Проблема

Рассмотрим следующую программу:

$INLINE I;

I { = }

Test {
  s.X e.Y = <I> <S s.X e.Y 1> <D s.X>;
}

$SPEC S t.X e.y t.Z;

S {
  t.X e.Y t.Z = t.X t.Z;
}

$DRIVE D;

D {
  A = A;
  B = B;
  s.X = s.X;
}

Функция S может специализироваться по первому и последнему терму. Функция D сужает переменную s.X, которая входит в аргумент S. Рассмотрим построенное оптимизированное дерево:

Test {
  A e.Y#1 = <S@1 A e.Y#1> A;

  B e.Y#1 = <S@1 B e.Y#1> B;

  s.X#1 e.Y#1 = <S@1 s.X#1 e.Y#1> s.X#1;
}

S@1 {
  s.X#1 e.Y#1 = s.X#1 1;
}

Функция S могла бы быть проспециализирована по символам A и B, в которые обращается s.X в ходе прогонки.

Уберём вызов <I> из функции Test:

Test {
  s.X e.Y = <S s.X e.Y 1> <D s.X>;
}

Оптимизированное дерево:

Test {
  A e.Y#1 = <S@1 e.Y#1> A;

  B e.Y#1 = <S@2 e.Y#1> B;

  s.X#1 e.Y#1 = <S@3 s.X#1 e.Y#1> s.X#1;
}

S@1 {
  e.Y#1 = A 1;
}

S@2 {
  e.Y#1 = B 1;
}

S@3 {
  s.X#1 e.Y#1 = s.X#1 1;
}

Вызов S проспециализирован полностью. Почему так вышло?

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

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

В первом случае проход прогонки встроил <I>, затем проход специализации инстанцировал S@1 для сигнатуры s.X ← t.X, 1 ← t.Z, затем выполнилась прогонка <D s.X>. Функция S@1 не специализируемая, уточнение её аргумента никак не помогло.

Во втором случае сначала выполнилась прогонка <D s.X>, потом специализация вызова S, что дало три оптимизированных экземпляра S@1, S@2, S@3.

Решение

Повторно специализировать функции Func@N

Этот вариант напоминает повторную прогонку Func*N.

При построении Func@N компилятор помечает новую функцию как специализируемую, статическими параметрами становятся переменные из статических параметров функции Func.

Преимущество:

• Не надо менять OptTree.ref, достаточно правок внутри OptTree-Spec.ref. Благодаря этому задача не конфликтует с задачей рефакторинга оптимизации Рефакторинг архитектуры древесного оптимизатора #259.

Недостаток:

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

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

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

Иначе говоря, оптимизацию можно описать примерно таким псевдокодом:

while not неподвижная_точка() and count < MAX:
    while not неподвижная_точка() and count < MAX:
        проход_прогонки()
        count += 1
    проход специализации()
    count += 1

Преимущества:

• Изменения локализованы в одном файле: не надо трогать OptTree-Drive.ref и OptTree-Spec.ref.
• Можно заметить, что после проходов прогонки до неподвижной точки и прохода специализации функция уже не может измениться. А значит, после специализации можно выполнять прогонку только вновь инстанцированных функций. Это снизит сложность оптимизации с квадратичной до линейной.
  Если не менять подход к разморозке, то функция может измениться. Рассмотрим выражение <I1 <S2 <I3 …>>>. Вызов I1 блокирован тёплым вызовом функции S2, поэтому неподвижная точка прогонки будет лишь раскрытием вызова I3. Затем, после специализации S2 аргумент I1 станет холодным, что разрешит её встраивание.
  Но специализация заменяет вызов на вызов, причём она не меняет порядок вложенных вызовов в аргументе. Поэтому на стадии прогонки можно вообще забыть о специализируемых функциях — считать непрогоняемые функции по умолчанию холодными. Но вообще, это тема рефакторинга Рефакторинг архитектуры древесного оптимизатора #259.

Недостаток:

• Трудности с рефакторингом древесной оптимизации (Рефакторинг архитектуры древесного оптимизатора #259).

Проход прогонки сам возвращает неподвижную точку

Вариант аналогичен предыдущему с той лишь разницей, что внутренний цикл переносится в OptTree-Drive.ref.

Преимущества:

• Не надо трогать OptTree-Spec.ref.
• Аналогично, после прогонки и специализации функция дальнейшим оптимизациям не подлежит, это можно учитывать.

Недостатки:

• Для того, чтобы избежать избыточных проходов по функциям, нужно править OptTree.ref. Так что изменения не будут локализованы в одном файле.
• Тот же, что и выше. Сложности с рефакторингом Рефакторинг архитектуры древесного оптимизатора #259.

Что же выбрать?

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

[Mazdaywik]

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

---

На верхнем уровне оптимизации дерева (OptTree.ref) вызовы размечаются как тёплые и холодные. Первые должны оптимизироваться, вторые — пропускаться. Смысл их в том, что холодные вызовы оптимизаторами уже не должны меняться. Во-первых, их повторно анализировать уже не надо. Во-вторых, можно оптимизировать вызовы с холодными активными аргументами, т.к. они при оптимизации больше меняться не будут.

Проходы специализации заменяют вызовы на другие вызовы, причём порядок вызовов в своих аргументах они не меняют. А значит, они «невидимы» для прогонщика. Действительно, вызов <S …> заменится на <S@1 …> и всё. Как уже сказано выше, прогонщик в идеале должен рассматривать все специализируемые вызовы как просто не оптимизируемые.

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

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

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

Поэтому «температуру» нужно перенести в проход прогонки. Из специализатора логику температуры можно просто выкинуть.

Вообще, разметка вызовов в OptTree.ref не нужна. Если прогонщик видит, что этот вызов оптимизируемой функции, то делается попытка прогонки/встраивания. Если нет — помечается холодным.

---

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

[Mazdaywik]

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

Были сделаны три замера производительности: до первого коммита по этой заявке (96fb33e), после предпоследнего коммита (8e38460) и после последнего (a5b0b5b).

Замер выполнялся стандартным бенчмарком, с ключами компиляции RLMAKE_FLAGS= (пустыми) и BENCH_FLAGS=-ODS, т.е. неоптимизированная версия компилятора делала тестовый прогон с оптимизацией. Использовался компьютер Intel® Core™ i5-2430M CPU @ 2.40 GHz, 8 Гбайт ОЗУ, Windows 10 x64.

Результаты:

1. Медиана: 85,497 секунд, доверительный интервал 85,233…85,779 секунд (замер).
2. 84,938 с, 84,231…85,758 с (замер), разница в 0,6 % объяснима статистической погрешностью.
3. 49,481 с, 49,220…49,826 с (замер), разница −42 % демонстрирует ускорение, связанное с пометкой холодных определений функций.