Оптимизация результатных выражений

[Mazdaywik]

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

Выполнение функции условно можно разбить на два этапа: анализ аргумента и построение результата. Анализ осуществляется путём последовательного перебора левых частей предложений на предмет соответствия аргумента одному из образцов (анализ в настоящей задаче не рассматривается). Построение результата — формирование возвращаемого значения функции — представляет собой создание нового фрагмента двусвязного списка, который будет замещать список-вызов функции в поле зрения.

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

В данном случае есть две причины потери производительности:

1. Размещаемые элементы переносятся из списка свободных узлов в поле зрения по одному за раз. То есть, для каждого нового узла перепровязываются ссылки «предыдущий»/«следующий» при изъятии из списка свободных узлов и вставке в поле зрения.
2. Для построения результата не всегда требуется строить новые узлы в списке свободных узлов. Часто можно заново использовать фрагменты из вызова функции, а в отдельных частных случаях создание нового результатного выражения требует лишь небольшой правки вызова (даже без распределения новых узлов в списке свободных).

Примечание. Данное исследование уже проводилось в 2010 году (коммит 6af96b3, не в master’е). В ходе исследования удалось выяснить, что уйма времени тратится на перевязывание отдельных узлов, если переносить созданные элементы целыми фрагментами, то производительность резко повышается. Также исследование показало, что если сохранять ссылки на отдельные узлы аргумента и вместо нового создания в списке свободных узлов использовать такие же из аргумента, то статистически значимого прироста производительности это не даёт. Алгоритм, который позволяет минимальным числом правок преобразовать вызов функции в результат, не разрабатывался.

Минимизация числа переносов уже была реализована в Модульном Рефале, прирост производительности составил порядка 13 %. В основной ветке Простого Рефала такой оптимизации на данный момент нет, код из исследования 2010 года не применялся в основной ветке, поскольку написан относительно грязно и содержит кучу артефактов исследования.

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

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

Диссертация Романенко:

• Отсканированная (pdf)
• Переписанная в LaTeX (pdf)

[Mazdaywik]

Соображение

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

Сейчас

Сейчас (в состоянии без оптимизации) фрагментами, которые могут (и должны быть!) заимствованы из вызова функции — это переменные. Часть переменных в результатном выражении берутся из аргумента, часть должны быть скопированы. Информация о том, какие переменные должны быть скопированы (и какие не должны были сопоставляться) определяется уже после (!) анализа образцового и результатного выражений. Операции сопоставления с образцом фильтруются на предмет избыточных сопоставлений с закрытыми переменными (ранее они приводили к предупреждениям компилятора C++). Операции построения результата дополняются командами копирования.

Что надо сделать

Чтобы реализовать оптимизацию, нужно изменить подход. Возможны два варианта.

Либо функция сопоставления с образцом (GenPattern в HightLevelRASL.sref) должна на выходе возвращать (помимо последовательности команд) позиции всех элементов вызова функции (= < + имя функции + аргумент + >), при этом команды сопоставления должны будут сохранять позиции всех элеменов. После чего отдельная новая функция будет анализировать помеченный образец и результат, выдавая на выходе помеченный результат, на основе которого функция GetResult (там же) будет формировать команды построения результата, зная какие фрагменты результата уже в готовом (или полуготовом) виде присутствуют в образце.

Либо сначала отдельной функцией обходится и образец, и результат, при этом в том и другом помечаются, соответственно, сохраняемые и переиспользуемые фрагменты, а затем функции GenPattern и GenResult будут формировать, соответственно, команды сопоставления и команды построения. GenPattern сможет генерировать команды, сохраняющие позиции, только для тех фрагментов, которые будут переиспользоваться (следствие: могут даже не сохраняться позиции некоторых переменных).

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

[Mazdaywik]

Результаты (кратко):

• Использовался алгоритм жадного строкового замощения.
• Оптимизация порядка 8…15 % (компонент «Linear result time» может уменьшаться даже двукратно).

Детали — в записке.