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

На момент написания этого документа в компиляторе имеется алгоритм оптимизации
совместного сопоставления с образцом, реализованный Павлом Батусовым
и Иваном Скрыпниковым (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][1], коммит 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 %

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

# Выводы

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

[1]: https://github.com/Mazdaywik/simple-refal-benchmark.git
