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

Древесные оптимизации раздувают программы

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

Description

Проблема
=======
Опыт самоприменения с глубокими оптимизациями (`-OA` + древесные) показал, что компилятор склонен раздувать программы (много примеров в #319, в свёрнутых комментариях). Программы раздуваются по двум причинам:
* прогонка может мультипликативно увеличить количество предложений,
* специализация может строить огромное количество переспециализированных экземпляров.

Под переспециализированными экземплярами мы понимаем избыточное количество экземпляров, которые не способствуют каким-либо интересным нетривиальным преобразованиям. Как правило, это специализации по каким-либо аккумуляторным переменным.

Сейчас эта проблема решается ручным анализом причины каждого очередного распухания и купированием его ad hoc (много примеров — коммиты к #319, предлагается даже специальный инструмент для купирования — #331). Но это не дело.

Ожидаемое поведение
===============
Компилятор не должен существенно раздувать программу, раздутие в общем случае должно быть умеренным, не более чем в 10 раз. Но при этом допускать интересные преобразования вроде специализации (в широком смысле) простых интерпретаторов (вроде [скрипта древесных оптимизаций](https://github.com/bmstu-iu9/refal-5-lambda/blob/672af493555673016affb2eaa932cfec1b3555c0/src/compiler/OptTree.ref#L188-L307)).

Понятно, что обеспечить эту численную характеристику (×10) для нетривиальных символьных преобразований нельзя, речь идёт о том, что на наборе типичных программ (сам Рефал-5λ без ручных разметок, MSCP-A, SCP4, другие, которые найдутся) **среднее раздутие (размер RASL’а) должно быть не более, чем на порядок, чем при компиляции без древесных оптимизаций.**

Но при этом возможность интересных преобразований должна допускаться.

С точки зрения математики обе цели противоречивы: допускать нетривиальные преобразования и ограничивать объём преобразованной программы. Это, вроде как, следует из теоремы Райса-Успенского. Но с точки зрения практики можно найти приемлемый компромисс, когда можно писать и специализируемые интерпретаторы, и программы распухают не сильно.

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.