Тестирование, рефакторинги, оптимизации и исправления после ВКР

[Mazdaywik]

Только что завершились две выпускные квалификационные работы:

• @Apakhov, реализовавший построение ациклического графа суперкомпиляции путём задержки рекурсивных вызовов (Прогонка, которая не зацикливается #340),
• @VladisP, реализовавший Расширенный алгоритм обобщённого сопоставления #322 и Специализация без шаблона #251.

Эти расширения станут основным новшеством версии 3.4. Однако, прямо сейчас создавать новую версию преждевременно по следующим причинам.

1. @Apakhov и @VladisP намеренно работали с очень ограниченным объёмом кода (в смысле, я ограничил их работу). Работа @Apakhov’а была ограничена файлом OptTree-Drive-Expr.ref, работа @VladisP’а — файлами GenericMatch.ref и OptTree-Spec.ref. Однако, полноценная реализация новых функций требует изменения куда большего объёма кода (например, скрипта в OptTree.ref).

   Ограниченность поля для работы @Apakhov’а и @VladisP’а была намеренной, т.к. этого было достаточно для выполнения содержательной части задачи.

2. Ациклическая прогонка @Apakhov’а делает ненужной авторазметку прогоняемых функций в том виде, в каком она сейчас есть. Исходно разметка была призвана не допускать пометки $DRIVE для рекурсивных функций. Сейчас рекурсивные функции могут иметь метку $DRIVE, их прогонка не зациклится.

3. Со специализацией без шаблона @VladisP’а становятся ненужными шаблоны в абстрактном синтаксическом дереве. Но, чтобы их удалить, нужны более глубокие правки.

4. Да, авторазметка для специализации тоже становится ненужной.

5. Основные компоненты для Универсальная древесная оптимизация $OPT #314 уже реализованы (#251, #322, #340). Фактически в Универсальная древесная оптимизация $OPT #314 нужно реализовать поддержку псевдокомментариев так, как она описана (и в следующем релизе удалить старый синтаксис).

6. Написанный студентами код может быть неоптимальным, т.к. у них нет опыта в оптимизации Рефала.

7. Новые оптимизации работают глубже, из-за чего могут выявиться проблемы в других частях системы. В частности, обостряются проблемы с раздуванием программ (Древесные оптимизации раздувают программы #332). На данный момент проблема купирована в 54c28cad9921556d208bc43dc88f55943d7885cb.

8. Хотя все автотесты выполнились, включая и случайные, тестовое покрытие, выполненное студентами неполное. Требуется более тщательное тестирование.

9. Автотесты проверяют корректность. Содержательную сторону нужно тестировать вручную.

10. Даже если обе оптимизации в отдельных ветках работали порознь, при работе вместе возможны проблемы.

11. Можно удалить ObjectMatch.ref, т.к. новый алгоритм сопоставления покрывает этот случай.

---

В первую очередь нужно

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

[Mazdaywik]

(комментарий не сворачивать, на него есть ссылка)

Функция GrowDriveTree скрылась с экранов радаров:

Total time: 583.17200 s
Total semisteps (function calls and closure unwraps): 346741271
Mean semistep time: 1.681865 us

Solve-Clashes (5826) -> 59036.0 ms (10.12 %, += 10.12 %)                               rel step time 6.54
ApplyContraction-toExpr (5826) -> 33258.0 ms (5.70 %, += 15.83 %)                     rel step time 1.27
OutlineStrings (3824) -> 17141.0 ms (2.94 %, += 18.77 %)                              rel step time 7.56
ExtractVariables-Expr (0000) -> 15008.0 ms (2.57 %, += 21.34 %)                       rel step time 0.66
ClearCoordinates (5826) -> 10479.0 ms (1.80 %, += 23.14 %)                            rel step time 0.81
IsSVarSubset (5826) -> 10393.0 ms (1.78 %, += 24.92 %)                                rel step time 0.75
IsTerm (5826) -> 9410.0 ms (1.61 %, += 26.53 %)                                      rel step time 0.67
SimplifyCoordinates-Expr (5826) -> 8961.0 ms (1.54 %, += 28.07 %)                    rel step time 0.85
SimplifyCoordinates-Expr-Inner (5826) -> 8435.0 ms (1.45 %, += 29.51 %)              rel step time 1.15
Map@11 (5826) -> 7725.0 ms (1.32 %, += 30.84 %)                                      rel step time 0.76
Add (0000) -> 7315.0 ms (1.25 %, += 32.09 %)                                         rel step time 0.67
Solve-Clashes$2?1 (5826) -> 7027.0 ms (1.20 %, += 33.30 %)                           rel step time 1.33
Solve-Clashes$4?1 (5826) -> 6469.0 ms (1.11 %, += 34.41 %)                           rel step time 1.60
Solve-Clashes$3?1 (5826) -> 6367.0 ms (1.09 %, += 35.50 %)                           rel step time 1.22
DoGenSubst (2951) -> 6021.0 ms (1.03 %, += 36.53 %)                                  rel step time 14.18
__Step-Drop (0000) -> 5803.0 ms (1.00 %, += 37.53 %)                                 rel step time 0.29
Unique (0000) -> 5770.0 ms (0.99 %, += 38.52 %)                                      rel step time 1.45
Solve-Clashes$9?1 (5826) -> 5624.0 ms (0.96 %, += 39.48 %)                           rel step time 1.40
Solve-Clashes$8?1 (5826) -> 5612.0 ms (0.96 %, += 40.44 %)                           rel step time 1.39
Solve-Clashes$1?2 (5826) -> 5567.0 ms (0.95 %, += 41.40 %)                           rel step time 1.75
Solve-Clashes$12?1 (5826) -> 5490.0 ms (0.94 %, += 42.34 %)                          rel step time 1.36
Solve-Clashes$13?1 (5826) -> 5448.0 ms (0.93 %, += 43.27 %)                          rel step time 1.36
Solve-Clashes$7?1 (5826) -> 5311.0 ms (0.91 %, += 44.18 %)                           rel step time 1.32
Solve-Clashes$5?1 (5826) -> 5248.0 ms (0.90 %, += 45.08 %)                           rel step time 1.30
Solve-Clashes$1?1 (5826) -> 5094.0 ms (0.87 %, += 45.96 %)                           rel step time 0.96
Solve-Clashes$6?1 (5826) -> 5012.0 ms (0.86 %, += 46.82 %)                           rel step time 1.24
AddContraction-Spec (5826) -> 4891.0 ms (0.84 %, += 47.66 %)                         rel step time 1.87
DoAddCoordinateLabels (5826) -> 4870.0 ms (0.84 %, += 48.49 %)                       rel step time 0.82

---

Что дальше нужно оптимизировать и как? Рассмотрим построчно.

• Solve-Clashes — >10,12 %. Время её выполнения составляет 6,54 средних шага, т.к. в ней есть полиномиальная сложность — открытые переменные. Функция описана как набор из правил, каждое из которых ищет в системе применимый к нему терм при помощи открытой переменной.

  Заметим, в функции есть условия, и если условие не выполнилось, то последующее время выполнения профилировщик припишет не Solve-Clashes, а Solve-Clashes$k?m, что мы и видим в профиле. Заметим, что этих «условий» много и каждое из них отъедает около процента времени. Таким образом, Solve-Clashes по факту потребляет гораздо больше 10 %.

  Как её оптимизировать?

  • Можно собрать статистику, какие правила выполняются чаще и переместить их вверх.
  • Можно ввести частные случаи правил. Вместо, например, правила для e.X E : Pt P ввести отдельные правила для e.X E : X P, e.X E : s.X P, e.X E : (P′) P″, e.X E [X P′] P″, e.X E : t.Y P. Это позволит сократить число итераций за счёт удлинения самой итерации.
  • Можно поменять порядок итераций, перебирая не сначала правила, а потом клэши, а наоборот. Для первого клэша последовательно проверить все правила, выполнить применимое. Если применимо только правило для открытой переменной — положить в карман и перейти к следующему. Какой эффект смена итераций окажет на производительность — не понятно. Возможно, наоборот снизит быстродействие.

• ApplyContraction-toExpr — 5,7 %. В текущей реализации при построении каждого нового сужения оно применяется (а) к предыдущим сужениям, (б) к уравнениям, (в) к присваиваниям. Это избыточно для ветвей, которые усекаются. Альтернативный вариант: сужения складывать по очереди в карман, в процессе решения применять их только к уравнениям. К набору параметров они будут применяться только при получении решения, к присваиваниям — перед построением симметричных клэшей.

• OutlineStrings — 2,94 %. Функция в back-end’е, сейчас нас не интересует.

• ExtractVariables-Expr — 2,57 %. Подозреваю, что это извлечения новых переменных из сужений в алгоритме прогонки. Эти вызовы можно устранить, если научить функцию Solve-Drive возвращать модифицированный список используемых переменных.

• ClearCoordinates — 1,8 %. Функция эффективная, выполняется за 0,81 среднего шага. Все точки вызова по делу. Никак не оптимизируешь.

• IsSVarSubset — 1,78 %, IsTerm — 1,61 %. Варианты:

  • Компилятор не способен оптимизировать вызовы этих простых функций, т.к. они вызываются из условий. Вопрос: имеет ли смысл встроить их вручную, размножив правила?
  • Добавление таксономии: термы и символы оборачивать, соответственно, в (T …) и (S …):
    • (Var 't' e._) → (T (Var 't' e._))
    • (Brackets e._) → (T (Brackets e._))
    • (ADT-Brackets e._) → (T (ADT-Brackets e._))
    • (Symbol e._) → (T (S (Symbol e.)))
    • (Var 's' e._) → (T (S (Var 's' e._)))
    • (ClosureBrackets e._) → (T (S (ClosureBrackets e._)))

  Преобразование применяется к обоим частям уравнения (либо только к левой?). В этом случае функции IsSVarSubset и IsTerm станут не нужны, т.к. эта же информация будет обретаться из образца. Но введение таксономии заметно усложнит применение подстановок.

• SimplifyCoordinates-Expr — 1,54 %, SimplifyCoordinates-Expr-Inner — 1,45 %. Они вообще не нужны. Скопления координат вида … {a} {b} {c} … могут возникнуть при применении нескольких стирающих подстановок на смежные e-переменные, что довольно редко. Кроме того, эти скопления никак не мешают работе алгоритма. Поэтому нужно устранять скопления, возникающие на границах на верхнем уровне. А это уже не требует сканирования всего выражения в глубь.

• Map@11 — 1.32 %. Надо по логу смотреть, что это. Но, судя по области видимости 5826, она из GenericMatch.ref.

Дальше разбирать не интересно.

[Mazdaywik]

Комментарий не сворачивать, на него ссылка из #332 (comment).

Ещё один из возможных путей оптимизации — учёт частных случаев вида

e.X : P
t.X : Pt

Если P/Pt — жёсткие выражения, то их решением будут, соответственно, сужения e.X → P′ и t.X → Pt′, где P′ и Pt′, соответственно, повторяют по своей структуре P и Pt, но все переменные в них новые. Для образца с открытыми переменными эти переменные нужно оставлять как отдельные клэши.

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

[Mazdaywik]

Увидел в логе странную картину (этап прогонки экземпляров, -OiADPRS). Было:

  GST\3 {
    ((e.Trash) (e.MarkedResult)) = (<Map@1 e.Trash>) (<Map@1 e.MarkedResult>);
  }

Стало:

  GST\3 {
    ((e.Trash) ((Num s.MarkedResult2 t.MarkedResult3) e.MarkedResult0))
      = (<* &Map@1 e.Trash*>) (t.MarkedResult3 <* &Map@1 e.MarkedResult0*>);

    ((e.Trash) (RemovedTile e.MarkedResult0))
      = (<* &Map@1 e.Trash*>) (RemovedTile <* &Map@1 e.MarkedResult0*>);

    ((e.Trash) ((Tile e.MarkedResult2) e.MarkedResult0))
      = (<* &Map@1 e.Trash*>)
        ((Tile e.MarkedResult2) <* &Map@1 e.MarkedResult0*>);

    ((e.Trash) (t.MarkedResult e.MarkedResult0))
      = (<* &Map@1 e.Trash*>)
        (<* &DeEnum\1*3 t.MarkedResult*> <* &Map@1 e.MarkedResult0*>);

    ((e.Trash) ()) = (<* &Map@1 e.Trash*>) ();

    ((e.Trash) (e.MarkedResult))
      = (<* &Map@1 e.Trash*>) (<* &Map@0 &DeEnum\1@0 e.MarkedResult*>);
  }

Такое впечатление, что не сработало отношение Хигмана-Крускала.

[Mazdaywik]

Сборка коммита a145f6c сломалась:

https://github.com/bmstu-iu9/refal-5-lambda/runs/3369437105

Причина, конечно же, распухание программы. Но какое это распухание! Смотрите, было:

  Go=11 {
    ('AA') ('BB') ('CC') ('DD') = <Go=12 <F ('AABBAACC' 9 'DD') ()>>;
  }

Стало:

  Go=11 {
    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AAB') ('BAACC' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AABB') ('AACC' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AABBA') ('ACC' 9) 'DD'>*>;

    …
  }

Полностью

  Go=11 {
    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AAB') ('BAACC' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AABB') ('AACC' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AABBA') ('ACC' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AABBAA') ('CC' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AABBAAC') ('C' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD') = <* &Go=12 <S?1?3 () ('AABBAACC') (9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 () ('A') ('BBAACC') ('DD') 'A'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('ABB') ('A') ('ACC') ('DD') 'A'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('ABBA') ('A') ('CC') ('DD') 'A'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('BB') ('AA') ('CC') ('DD') 'AA'>*>;

    ('AA') ('BB') ('CC') ('DD') = <* &Go=12 <S*1 'AABBAACC' 9 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AABB') ('AACC' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AABBA') ('ACC' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AABBAA') ('CC' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AABBAAC') ('C' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD') = <* &Go=12 <S?1?3 () ('AABBAACC') (9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 () ('A') ('BBAACC') ('DD') 'A'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('ABB') ('A') ('ACC') ('DD') 'A'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('ABBA') ('A') ('CC') ('DD') 'A'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('BB') ('AA') ('CC') ('DD') 'AA'>*>;

    ('AA') ('BB') ('CC') ('DD') = <* &Go=12 <S*1 'AABBAACC' 9 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AABBA') ('ACC' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AABBAA') ('CC' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?3 () ('AABBAAC') ('C' 9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD') = <* &Go=12 <S?1?3 () ('AABBAACC') (9) 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 () ('A') ('BBAACC') ('DD') 'A'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('ABB') ('A') ('ACC') ('DD') 'A'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('ABBA') ('A') ('CC') ('DD') 'A'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('BB') ('AA') ('CC') ('DD') 'AA'>*>;

    ('AA') ('BB') ('CC') ('DD') = <* &Go=12 <S*1 'AABBAACC' 9 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?2 () ('AABBAA') ('CC') 9 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABBAAC') () ('C') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABBAACC') () () ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD') = <* &Go=12 <S?1?6 () 'AABBAACC' 9 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABBAA') () ('CC') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABBAAC') () ('C') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABBAACC') () () ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD') = <* &Go=12 <S?1?6 () 'AABBAACC' 9 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AA') () ('BBAACC') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AAB') () ('BAACC') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABB') () ('AACC') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABBA') () ('ACC') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABBAA') () ('CC') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABBAAC') () ('C') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABBAACC') () () ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD') = <* &Go=12 <S?1?6 () 'AABBAACC' 9 'DD'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('A') () ('ABBAACC') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AA') () ('BBAACC') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AAB') () ('BAACC') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABB') () ('AACC') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABBA') () ('ACC') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABBAA') () ('CC') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABBAAC') () ('C') ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('AABBAACC') () () ('DD')>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 () ('A') ('BBAACC') ('DD') 'A'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('ABB') ('A') ('ACC') ('DD') 'A'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('ABBA') ('A') ('CC') ('DD') 'A'>*>;

    ('AA') ('BB') ('CC') ('DD')
      = <* &Go=12 <S?1?0 ('BB') ('AA') ('CC') ('DD') 'AA'>*>;

    ('AA') ('BB') ('CC') ('DD') = <* &Go=12 <* &S*1 'AABBAACC' 9 'DD'*>*>;
  }

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

• Первое же решение без сужений экранирует все последующие. Так делать пока можно, поскольку в оптимизируемом предложении нет условий. С условиями всё хитрее и пока многое непонятно — Разметка неразменных аргументов для прогонки #231, Прогонка условий #248, Прогонка вызовов функций в условиях #283. Но такого варианта недостаточно, т.к. экранировать могут и ветвления с эквивалентными наборами сужений (с точностью до имён переменных).
• После построения набора новых предложений, проверить их на экранирования. Для проверки достаточно использовать обычное сопоставление с образцом, т.к. образцы заведомо L-выражения.