bmstu-iu9 / bmstu-iu9/refal-5-lambda

Анализ и оптимизация производительности Рефала-5λ

Open
#194 7 comments 0 reactions 1 assignee Claimed by @Mazdaywik View on GitHub
task
Dominant language
C++
Stars
97
Forks
40
PR merge metrics
No merged PRs in 30d

Description

Эта задача — подзадача для #185.

Выяснилось, что компилятор Рефала-05, собранный Рефалом-5λ, в три раза медленнее компилятора, собранного самим собой, и компилятора, собранного `refc`. И это не смотря на максимально доступные оптимизации (`-OdPRC`).

То, что обгоняет `refgo`, можно объяснить более оптимальным форматом языка сборки. Команды сопоставления функциональны, они не изменяют значения уже присвоенных ячеек стека, а инициализируют новые. В то время как в Рефале-5λ при каждом сопоставлении изменяется содержимое ячейки-диапазона.

Но при этом Рефал-05 вообще не содержит никаких оптимизаций и его идеология языка сборки совпадает с идеологией в Рефале-5λ.

Можно предположить следующие причины:
* В коде Рефала-5λ слишком много слоёв абстракций и используемый BCC 5.5 не может всё заинлайнить. Соответственно, нужно упрощать вручную. В частности, для функций и идентификаторов их указатель получается вызовом `vm->ref(descr)`.
* В Рефале-05 очень дешёвая функция `Mu` (в силу особенностей языка) и она активно используется. Например, в кодогенераторе инструкции формируются путём косвенного вызова их тегов в цикле. И, возможно, за счёт дешевизны `Mu` Рефал-05 обгоняет `refc`+`refgo`.
* Встроенные функции реализованы на Рефале, при этом для каждой из них корректируется виртуальный счётчик шагов функциями `<__Step-Start>` и `<__Step-End>`
* Используется неоптимальное построение результатных выражений, а именно, без учёта последовательного распределения строящихся элементов и с проверками успешности команд аллокации.

В Рефале-5λ `Mu` не оптимизирована. Мало того, что она написана на Рефале с условиями и несколькими вспомогательными функциями, так ещё и сам поиск имени достаточно тяжеловесен.

Что нужно сделать:
* [ ] Замерить время без использования функции `Mu` — конвертировать программу на Рефале-05 в Рефал-5λ, заменив все идентификаторы `Func` на указатели `&Func` и вызовы `` на непосредственный вызов ``. Для этого можно написать препроцессор на Рефале-05, тем более что Рефал-05 декларируется как язык для написания таких инструментальных средств.

В результате получится программа, семантически идентичная Рефалу-05, а значит, сравнение будет честнее.
* [ ] Попробовать исключить лишние слои абстракций.
* [ ] Посчитать количество, и, возможно, время выполнения вызовов каждой из функций программы для Рефала-05 и Рефала-5 и сделать выводы. Такие замеры уже делались (d6255fb10cf14418403ef9ff0a361bf9c8987111, 674963791fab8b6312b09186eeac03b2bc27ea23).
* [ ] Оптимизировать построение результатных выражений (#196).
* [ ] Пересмотреть и оптимизировать язык сборки, сделав команды сопоставления функциональными (#204).

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.