Оптимизация образцовых выражений

[Mazdaywik]

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

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

И здесь есть серьёзная проблема производительности. На практике левые части отдельных предложений имеют сходную форму. Причин на то несколько:

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

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

Примечание. Данную задачу уже начинал решать @PavelBatusov (Павел Батусов, ссылка на репозиторий), однако по ряду причин до конца не довёл.

[Mazdaywik]

Переоткрываю задачу

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

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

[Mazdaywik]

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

Задача переносится на следующий осенний семестр.

[Mazdaywik]

Задача ветвления успешно выполнена, поэтому задачу закрываю.

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

Осталось нереализованным переупорядочивание переменных, но для этого я, наверное, сделаю отдельную задачу.

[Mazdaywik]

В предыдущем коммите добавил отчёт о производительности в репозиторий. Продублирую его в комментарии.

Небольшой отчёт о величине ускорения с новой оптимизацией

На момент написания этого документа в компиляторе имеется алгоритм оптимизации
совместного сопоставления с образцом, реализованный Павлом Батусовым
и Иваном Скрыпниковым (2016), активируется опцией -OP, и алгоритм
оптимизации, реализованный Павлом Савельевым (2017), включаемый опцией -OQ.

Я на своей машине (Intel® Core™ i5-2430M CPU @ 2.40 GHz, кэши 128 Кбайт,
512 Кбайт и 3,0 Мбайт, ОЗУ 8 Гбайт, Windows 10 Pro 1803, сборка 17134.165)
сделал несколько замеров. Использовался компилятор Borland C++ 5.5.1 for Win32
для сборки рантайма.

Рантайм специально не оптимизировался, т.е. использовался собранный
с дефолтными параметрами.

Время будет указываться как MMM [LLL…HHH], где MMM — медианное время
в секундах, LLL и HHH — соответственно нижний и верхний квартили, образующие
доверительный интервал.

Стандартный встроенный бенчмарк benchmark.bat

Был выполнен 21 замер в режиме интерпретации. Измерялось чистое время Рефала
(Total refal time).

Режим	Время	Прирост
Без оптимизации:	13,928 [13,824…14,239]
-OP	12,598 [12,489…12,701]	−9,5 %
-OQ	11,982 [11,891…12,135]	−14,0 %

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

Бенчмарки из simple-refal-benchmark.git

Далее приводятся результаты бенчмарков из репозитория
simple-refal-benchmark.git, коммит 44fa25744401.

1-random.bat

Генератор случайных программ на Рефале. Автор: Немытых А. П.

Было выполнено 13 замеров.

Режим	Время	Прирост
Без оптимизации:	8,993 [8,898…9,058]
-OP	8,874 [8,754…8,985]	−1,6 %
-OQ	8,926 [8,877…8,982]	−0,7 %
-Od	7,323 [7,229…7,410]
-OdP	7,329 [7,239…7,436]	≈0,0 %
-OdQ	7,472 [7,358…7,523]	+2,0 %

Доверительные интервалы существенно накладываются друг на друга, разница
в производительности едва заметна, для оптимизации -OdQ наблюдается даже
незначительная деградация производительности. Я затрудняюсь этот факт
объяснить.

Очевидно только ускорение при использовании опции -Od: результат более
чем достоверен и прирост составляет 18,6 %.

2-dfagen.bat

Генератор конечного автомата для распознавания набора слов. Автор:
Скоробогатов С. Ю.

Выполнялось 13 замеров.

Режим	Время	Прирост
Без оптимизации:	7,275 [7,130…7,328]
-OP	7,246 [7,173…7,327]	−0,4 %
-OQ	7,295 [7,129…7,359]	+0,3 %
-Od	6,574 [6,529…6,613]
-OdP	6,546 [6,470…6,580]	−0,4 %
-OdQ	6,564 [6,533…6,617]	−0,2 %

Доверительные интервалы практически совпадают, а значит результат
статистически недостоверен. Стало быть, для этого теста оптимизация
не даёт прироста производительности. Ускорение от ключа -Od
я комментировать уже не буду.

3-rmcc.bat

Генератор таблиц для LL(1)-анализатора. Автор: Скоробогатов С. Ю.

Выполнялось 13 замеров.

Режим	Время	Прирост
Без оптимизации:	11,047 [10,907…11,107]
-OP	10,922 [10,873…11,015]	−1,1 %
-OQ	11,001 [10,828…11,217]	−0,4 %
-Od	9,687 [ 9,641… 9,718]
-OdP	9,518 [ 9,499… 9,609]	−1,7 %
-OdQ	9,452 [ 9,406… 9,608]	−2,4 %

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

4-scp4-refal-machine.bat

Стадия суперкомпиляции SCP4. В качестве входных данных использовался
интерпретатор Рефала, который специализировался по нескольким примерам
функций. Автор: Немытых А. П.

Было выполнено 13 замеров.

Режим	Время	Прирост
Без оптимизации:	18,821 [18,753…18,855]
-OP	17,861 [17,746…18,111]	−5,1 %
-OQ	17,097 [16,983…17,159]	−9,2 %
-Od	16,751 [16,582…16,800]
-OdP	15,887 [15,840…16,037]	−5,2 %
-OdQ	15,861 [15,669…15,905]	−5,3 %

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

5-synthetic.bat

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

* E → E + T | T
ParseE {
  e.Expr s.Op e.Term
    , <ParseE e.Expr> : t.Expr
    , <OneOf s.Op '+-'> : True
    , <ParseT e.Term> : t.Term
    = (t.Expr s.Op t.Term);

  e.Term , <ParseT e.Term> : t.Term = t.Term;

  e.Other = /* пусто */;
}

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

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

ParseE$1?1?3 {
  (e.Expr_fix#1) e.Expr_var#1 s.Op#1 e.Term#1
    = <ParseE$1?1?0
        (e.Expr_fix#1 e.Expr_var#1) s.Op#1 (e.Term#1)
        <ParseE e.Expr_fix#1 e.Expr_var#1>
      >;

  (e.Expr_fix#1) e.Expr_rest#1
    = <ParseE$1?1?1 e.Expr_fix#1 e.Expr_rest#1>;
}

Автор: Коновалов А. В.

Режим	Время	Прирост
Без оптимизации:	6,856 [6,764…6,906]
-OP	6,735 [6,687…6,818]	−1,8 %
-OQ	6,798 [6,731…6,858]	−0,8 %
-Od	4,240 [4,169…4,327]
-OdP	4,295 [4,190…4,372]	+1,3 %
-OdQ	4,453 [4,405…4,515]	+5,0 %

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

6-sr-lexer.bat

Лексический анализатор из front-end’а Простого Рефала. Отличается наличием
автоматически сгенерированных автоматных функций такого вида:

SL-E-C2 {
  (e.Accum) '0' e.Text
    = (#TkLiteral-Code e.Accum '0') <StringLiteral () e.Text>;
  (e.Accum) '1' e.Text
    = (#TkLiteral-Code e.Accum '1') <StringLiteral () e.Text>;
  (e.Accum) '2' e.Text
    = (#TkLiteral-Code e.Accum '2') <StringLiteral () e.Text>;
  (e.Accum) '3' e.Text
    = (#TkLiteral-Code e.Accum '3') <StringLiteral () e.Text>;
  (e.Accum) '4' e.Text
    = (#TkLiteral-Code e.Accum '4') <StringLiteral () e.Text>;
  (e.Accum) '5' e.Text
    = (#TkLiteral-Code e.Accum '5') <StringLiteral () e.Text>;
  (e.Accum) '6' e.Text
    = (#TkLiteral-Code e.Accum '6') <StringLiteral () e.Text>;
  (e.Accum) '7' e.Text
    = (#TkLiteral-Code e.Accum '7') <StringLiteral () e.Text>;
  (e.Accum) '8' e.Text
    = (#TkLiteral-Code e.Accum '8') <StringLiteral () e.Text>;
  (e.Accum) '9' e.Text
    = (#TkLiteral-Code e.Accum '9') <StringLiteral () e.Text>;
  (e.Accum) e.Text
    = (#TkLiteral-Code e.Accum) <StringLiteral () e.Text>;
}

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

Автор: Коновалов А. В.

Режим	Время	Прирост
Без оптимизации:	3,279 [3,248…3,343]
-OP	2,611 [2,592…2,657]	−20,4 %
-OQ	2,560 [2,485…2,625]	−21,9 %
-Od	2,328 [2,266…2,405]
-OdP	1,860 [1,830…1,872]	−20,1 %
-OdQ	1,765 [1,703…1,797]	−24,2 %

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

Выводы

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