Недавно мною (@Mazdaywik) был разработан минималистичный компилятор Рефала, совместимый с Рефалом-05 — https://github.com/Mazdaywik/Refal-05. Компилятор разрабатывался мною ради интереса и стремления к минималистичности, разрабатывался на основе древних коммитов Простого Рефала.

По итогам этой работы назрел ряд выводов.

Производительность (#194)

Самый важный вывод — Рефал-5λ медленный! Рефал-05 быстрее Рефала-5 PZ Oct 29 2004, а Рефал-5λ — существенно медленнее.

Одним из результатов разработки Рефала-05 стала программа, которую можно собрать тремя разными Рефалами со списковой реализацией: Рефалом-05, Рефалом-5 и Рефалом-5λ. Одинаковое списковое представление гарантирует, что стиль на быстродействие программы влияет одинаковым образом, а значит, оценка получается более объективной.

Тестировались следующие реализации:

Рефал-05 версии 3.0-12-g81d952b,
Рефал-5 PZ Oct 29 2004,
Рефал-5λ версии 2.2.4 (установленной из дистрибутива). Использовалась сборка по умолчанию (srrmake -o… refal05c.ref) и с максимальной оптимизацией (srmake --scratch -X-OdPRC -o… refal05c.ref), используемый компилятор Си — BCC 5.5 (без оптимизаций).

В качестве тестовых данных использовались исходники Рефала-05 упомянутой версии, указанные в командной строке шесть раз. Компилятор языка Си не вызывался, чтобы в полное время не попадал вызов функции System.

Выполнялось 9 замеров, определялась медиана (5-й замер) и два квартиля (3-й и 7-й замер). Для Рефала-5λ и Рефала-05 мерилось полное время работы.

Процессор Intel® Core™ i5-5200U CPU @ 2.20GHz, 8 Гбайт ОЗУ, процесс не свопился. ОС Windows 10 x64.

Для замеров использовался скрипт benchmark.bat, положенный в папку src репозитория Рефала-05.

В общем, результаты:

Реализация	Медианное время	Доверительный интервал	%
Рефал-05	2,891	2,875…2,906	84 %
Рефал-5 PZ Oct 29 2004	3,448	3,411…3,463	100 %
Рефал-5λ, без оптимизаций	10,312	10,250…10,422	299 %
Рефал-5λ, `-OdRPC`	7,625	7,578…7,672	221 %

За 100 % принята классическая реализация. Что можно сказать… Рефал-05 незначительно быстрее классической реализации, Рефал-5λ существенно медленнее — в три раза! Оптимизация -OdRPC даёт прирост в скорости 26 %, но это не может компенсировать общие тормоза.

Рефал-05 компилируется в чистый Си, не поддерживает никаких оптимизаций, собран простым BCC 5.5. Модель промежуточного кода принципиально оставлена той же, что и в Простом Рефале и сейчас (2019-02-12) в Рефале-5λ (описание в официальном руководстве). Никаких оптимизаций в компиляторе не заложено.

Рефал-5 PZ компилируется в интерпретируемый код, собран старой версией Visual C++ с максимальными оптимизациями. Использует интерпретируемый код Романенко. Используется оптимизация выделения общих префиксов для образцов.

И не смотря на менее эффективный промежуточный код, Рефал-05 обогнал Рефал-5 PZ за счёт легковесности и прямой компиляции в C89.

Рефал-5λ, не смотря на оптимизации, включая генерацию в код на Си++, оказался медленнее. Почему? Предстоит выяснить.

Число шагов: Рефал-05 — 4 674 763, Рефал-5 PZ — 4 686 439 (не знаю, почему больше), Рефал-5λ — 15 245 979. В четыре раза больше. Очевидно, дело в реализации встроенных функций — они написаны на Рефале, их вызовы окружаются функциями __Step-Start и __Step-End.
Неэффективные функции на Рефале. Относительное время в 05 — около 50 % (лень считать медианы), в лямбде — 66 % без оптимизаций и 53 % с оптимизациями. Почему?
Время линейного сопоставления с образцом сопоставимо, соответственно, ≈12 %, ≈18 % и ≈15 %.
Время линейного построения результата — ≈25 %, ≈43 % и ≈33 %. Здесь можно улучшить.
Нелинейные компоненты малы, аналога оверхеду рантайма в Рефале-05 нет.

Поэтому нужно понять, откуда берётся в 4 раза большее количество шагов и что с этим можно (и нужно) сделать.

Что можно улучшить в построении результата. Рефал-05 не проверяет успешность распределения памяти (как, кстати, и Рефал-5 PZ). Именно это нужно прежде всего исследовать.

Ещё можно предположить, что проблема низкой производительности в функции Mu: в Рефале-05 она дешёвая (просто вызывает функцию по указателю), в то время, как в Рефале-5λ она довольно навороченная:

https://github.com/bmstu-iu9/refal-5-lambda/blob/c48cf0179b66c407a5932c03cd8bf38958a8c477/src/srlib/common/refal5-builtins.srefi#L6-L31

https://github.com/bmstu-iu9/refal-5-lambda/blob/c48cf0179b66c407a5932c03cd8bf38958a8c477/src/srlib/Library.sref#L28-L59

Это тоже предстоит исследовать.

Псевдокомментарии (#195)

Рефал-05 не поддерживает символы-слова, вместо них используются символы-функции. Пустые функции определяются при помощи ключевого слова $ENUM. При этом Рефал-05 совместим с Рефалом-5. Противоречие разрешается благодаря псевдокомментариям — комментариям вида

*$ENUM True, False

которые эквивалентны

 $ENUM True, False;

Если однострочный комментарий начинается с *$, то знак * в начале заменяется на пробел, в конец дописывается ; и полученная строка считается обычной строчкой программы.

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

*$INLINE Foo, Bar, Baz
*$ Oof, Rab, Zab

Если следующая строка после псевдокомментария начинается на *$ (звёздочка, доллар, пробел), то она считается продолжением псевдокомментария.

Вообще, псевдокомментарии в языке частично есть — *$CLASSIC и $EXTENDED — значит, имеющуюся функцию нужно расширить и углубить.

Построение результатных выражений (#196)

Компиляция результатных выражений в Рефале-05 отличается от Рефала-5λ двумя новшествами:

Используется допущение о последовательном распределении памяти в списке свободных узлов.
Функции выделения памяти всегда успешны.

Допущение о последовательном распределении узлов для меня (@Mazdaywik) не ново — я так делал и в Модульном Рефале.

Суть его состоит в том, что следующие друг за другом операции распределения памяти создают в списке свободных узлов значения, располагающиеся последовательно в том же порядке. После чего в специально заготовленные места (в список свободных узлов) переносятся значения переменных и в результате там получается образ результатного выражения. Образ переносится в поле зрения командой splice_from_freelist, которая размещает его перед открывающей угловой скобкой. Затем остаток от вызова функции переносится в список свободных узлов командой splice_to_freelist.

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

В текущей реализации Рефала-5λ функции распределения памяти возвращают булевское значение: истину, если память распределить удалось, и ложь, если памяти оказалось недостаточно. В корректных программах истина возвращается всегда, а значит, всегда выполняется избыточная проверка. Если на стадии распределения памяти памяти оказалось недостаточно, то функция возвращает признак ошибки cNoMemory, в ответ на который рантайм выводит дамп и аварийно останавливает программу.

В Рефале-05 операции распределения памяти выполняются всегда успешно — в API не предусмотрено никакой проверки на недостаток памяти. Если операция аллокации память выделить не смогла, то она сама прерывает программу с выводом аварийного дампа.

Этот подход разумно перенести на Рефал-5λ. Останавливать ли программу в самой функции распределения или использовать нелокальный переход (исключение или longjmp()) — следует решить.

Язык Си (#197)

Рантаймом Рефала-05 и целевым кодом был выбран Си89, и это оказалось неплохим выбором. По мнению автора (@Mazdaywik), язык Си менее, чем C++, способствует к написанию большого числа слоёв абстракций, что разумно для компактного компилятора Рефала-05. Кроме того, такой выбор способствует переносимости — коллега @Barburator заинтересовался языком, поскольку на Plan-9 доступен только компилятор Си.

Поэтому стоит рассмотреть вопрос о переходе от Си++ к Си как в рантайме, так и в генерации кода.

Документация

Рефал-05 — единственный мой (@Mazdaywik) диалект Рефала с полной пользовательской документацией:

https://mazdaywik.github.io/Refal-05/

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

Так что вывод: документация Рефала-5λ потребует много много времени.

Синтаксический анализ

В компиляторе Рефала-05 опробован новый метод синтаксического анализа — гибрид рекурсивного спуска с элементами переноса-свёртки (Mazdaywik/Refal-05#29). Метод удобен для Базисного Рефала, но более многословен и менее эффективен. Стоит рассмотреть его применение после реализации глубоких оптимизаций (#91).

Совместимость с Рефалом-05

Этот пункт немножко не в тему. У Рефала-05 и Рефала-5(λ) есть общее подмножество, хорошей практикой является программирование на этом подмножестве. Пути поиска исходников Рефала-05 записываются в переменную окружения R05PATH. Поэтому следует рассмотреть возможность подключать исходники из этой папки, например, ключом --r05-path.

Можно также рассмотреть поддержку front-end’а Рефала-05, включаемого, например, псевдокомментарием *$REFAL05.

Единообразная обработка символов в синтаксическом дереве (#198)

В синтаксическом дереве компилятора Рефала-05 символы представлены как

(Symbol Char s.CHAR)
(Symbol Number s.NUMBER)
(Symbol Name e.Name)

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

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

Итоги

[ ] Анализ производительности — почему же Рефал-5λ на столько медленнее Рефала-05, оптимизация компилятора (#194).
[ ] Поддержка псевдокомментариев в духе Рефала-05 (#195).
[ ] Оптимизация построения результатных выражений (#196).
[ ] Рассмотреть использование языка Си (#197).
[ ] Рассмотреть другой подход к синтаксическому анализу.
[ ] Совместимость с Рефалом-05 — определить её глубину.
[ ] Единообразная обработка символов в дереве (#198).

bmstu-iu9 / refal-5-lambda

Анализ опыта разработки Рефала-05 #185