Построение результатных выражений как в Рефале-05

Эта задача — подзадача #185 (UPD: и #204 тоже). Процитирую параграф оттуда.

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

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

Функции выделения памяти всегда успешны.

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

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

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

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

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

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

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

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

Если использовать исключения и RAII-ресурсы, то на первый взгляд проблем нет. Кроме случая использования разных DLL с разными рантаймами Си++.

Поэтому по-прежнему остаются нужны API-функции создания элементов, которые могут возвращать признак успешности. А также нужно сохранить return …NO_MEMORY;. Кстати, признак успешности не обязательно должен быть кодом возврата. Функция может возвращать void, но при этом в API может быть и функция с именем вроде bool alloc_failed(), которая возвращает true, если один из предыдущих вызовов память выделить не смог.

Таким образом, можно выделить две подзадачи:

[x] Реализация API безотказного выделения памяти.
[ ] Генерация кода, учитывающая последовательное распределение узлов.

API рантайма Рефала-5λ используется только в библиотеках Library.ref и Hash.ref (и некоторых автотестах) и в библиотеке Модульного Рефала. Я проверил все вызовы функций refalrts::alloc_…, можно ли их заменить «безотказными» функциями, которые делают longjmp() при недостатке памяти.

В Library.ref так сделать можно — ни в одной из функций, вызывающих refalrts::alloc_…, не используются объекты Си++ с деструкторами. Замена будет совершенно безопасной и упростит код библиотеки.

В библиотеке Модульного Рефала всё немножко интереснее. В некоторых функциях, где выполняется распределение памяти, существуют переменные классов refalapi::CharArray и refalapi::AllocArray. Первый класс является обёрткой над std::vector<char>, второй не нужен.

Ряд функций писался в предположении, что порядок значений в списке свободных узлов не определён, поэтому в буфере refalapi::AllocArray сохранялись указатели на объединяемые фрагменты. Если переписать эти же функции в предположении, что значения распределяются последовательно, то refalapi::AllocArray станет не нужен.

А с refalapi::CharArray всё сложнее. Он хранит строку неизвестной длины, поэтому данная строка должна выделяться в динамической памяти. И её нужно освобождать при выходе из функции.

Значит, функции распределения, возвращающие bool, всё-таки нужны. Но, чтобы не дублировать каждую из функций, можно пойти двумя путями.

Можно написать функцию распределения памяти с переменным числом параметров. В «форматной строке» будут задаваться типы распределяемых элементов, в хвосте — их атрибуты. Функция будет возвращать истину или ложь.

Можно пойти ещё гибче, написать функцию-обёртку. Для Си она будет иметь тип

FnResult checked_alloc(FnResult (*func)(void *data), void *data);

Соответственно, она вызывает функцию func, передавая ей указатель на что-то. Если вызванная функция завершилась успешно — возвращается её код возврата. Иначе возвращает cNoMemory. На Си++ можно использовать шаблонные обёртки.

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

Нюанс или «а слона-то я и не приметил».

Выше в комментарии я написал, что библиотека Library.ref не создаёт локальных переменных с нетривиальными деструкторами.

Но создаёт их сам рантайм! Причём — в самой функции main_loop(), где и предполагается использовать setjmp():

https://github.com/bmstu-iu9/refal-5-lambda/blob/210ab9731372a3bfcbec2a6e35e1249aba71badb/src/srlib/refalrts-vm.cpp#L603-L610

Я попробовал перехватывать ошибки памяти при помощи setjmp(), думал, что пронесёт. Но тест limit-memory.FAILURE.sref стал глючить.

https://github.com/bmstu-iu9/refal-5-lambda/blob/210ab9731372a3bfcbec2a6e35e1249aba71badb/autotests/limit-memory.FAILURE.sref#L1-L5

(Коммит пока в локальной ветке, не на сайте GitHub.)

Так что нужно избавляться от локальных объектов. Тем более, что отладчик внутри цикла совершенно неуместен — для условий в нативном коде рекурсивно вызывается main_loop() и экземпляр отладчика будет создаваться каждый раз новый. Что неправильно.

Для последнего коммита был сделан замер стандартным бенчмарком. Уменьшение цикла самоприменения (медиана) составило ≈0,05 секунд:

до: 14,223 секунды, 14,194–14,471 замер,
после: 14,158 секунды, 13,982–14,601 замер.

Так что прирост производительности недостоверный. Во втором замере были заметные выбросы, перемеривать лень.

Для последнего коммита сделан анализ производительности — до него (90101b3003df10045c99e689b7fecf7b9683bf67) и на нём (e39b8b6635d4ae5cded350fbdb45a3b66a8bc339). Прирост оказался меньше, чем я ожидал: 1–2 %.

Выполнялся 21 замер стандартным бенчмарком, компилятор BCC 5.5.1 (без ключей оптимизации), процессор Intel® Core™ i5-5200U CPU @ 2.20 GHz, кэши L1/L2/L3 128 Кбайт/512 Кбайт/3 Мбайта. ОС Windows 10 x64, памяти достаточно (8 Гбайт), жёсткий диск жёсткий.

Замер не совсем точный, поскольку изменилась кодогенерация. В частности, из-за этого число шагов уменьшилось на 0,05 %.

Замер режима интерпретации

Ключи компилятора

set SREFC_FLAGS=-F-DREFAL_5_LAMBDA_USE_QPC
set SRMAKE_FLAGS=-X-F-DREFAL_5_LAMBDA_USE_QPC
set SCRIPT_FLAGS=

Результаты замера:

Интерпретация:

Чистое время выполнения Рефала ускорилось на 1,5 %. Было 16,34371 секунд (16,17016–16,67371), стало 16,09517 секунд (16,03071–16,25355). Доверительные интервалы пересекаются мало, медианы в них не попадают. Результат условно достоверен.
Время копирования контекста — ускорение 4 %. Было 0,21645 секунд (0,21360–0,22358), стало 0,20777 секунд (0,20567–0,21127). Доверительные интервалы не пересекаются, результат статистически достоверен. Только вот сама метрика занимает 1,1 % от общего времени выполнения.
Линейное время построения результатных выражений — ускорение 2,4 %. Было 8,36804 секунды (8,28338–8,56564). Стало 8,16317 секунд (8,14068–8,26381). Результат достоверен, доверительные интервалы не пересекаются. Время от общего времени выполнения ≈43 %.
Копирование t- и e-переменных — ускорение 3,2 %. Было 0,82497 секунды (0,81338–0,83402), стало 0,79868 секунды (0,79485–0,81323). От общего времени выполнения ≈4,2 %.

Остальные метрики ничего интересного не дают, да и давать не должны.

Замер режима прямой кодогенерации

Ключи компилятора

set SREFC_FLAGS=-F-DREFAL_5_LAMBDA_USE_QPC -Od
set SRMAKE_FLAGS=-X-F-DREFAL_5_LAMBDA_USE_QPC -X-Od --runtime=refalrts-diagnostic-initializer
set SCRIPT_FLAGS=--scratch

Результаты замера:

Интерпретация:

Чистое время выполнения Рефала ускорилось на 2,0 %. Было 13,00247 секунд (12,72187–13,06396), стало 12,73657 секунд (12,70870–12,93647). Результат условно достоверен, поскольку доверительные интервалы пересекаются мало (а медианы в них не попадают).
Время копирования контекста — ускорение 2,8 %. Было 0,21725 секунд (0,21465–0,22129), стало 0,21106 секунд (0,20869–0,21370). Ускорение достоверно. Цифры близки к аналогичному замеру выше, что не удивительно. Копирование контекста и копирование переменных выполняется внутри рантайма.
Линейное время построения результатных выражений — ускорение 1,6 %. Было 6,74231 секунда (6,61511–6,78951). Стало 6,63075 секунд (6,61108–6,70361). Доверительные интервалы пересекаются, вторая медиана попадает в первый доверительный интервал. Результат недостоверен.
Копирование t- и e-переменных — ускорение 2,8 %. Было 0,82672 секунды (0,80914–0,84438), стало 0,80331 секунда (0,79303–0,82402). Результат условно достоверен, первая медиана попадает на границу второго доверительного интервала.

Получается, замеры на прямую кодогенерацию мне не удалось сделать также чисто, как на интерпретацию.

Резерв оптимизации

На сколько можно ускорить код, оптимизируя построение результатных выражений в духе Рефала-05? Очевидно, быстрее оптимизации результатных выражений (-OR) не получится.

Сделал дополнительные замеры с ключами

Первый

set SREFC_FLAGS=-F-DREFAL_5_LAMBDA_USE_QPC
set SRMAKE_FLAGS=-X-F-DREFAL_5_LAMBDA_USE_QPC

Второй

set SREFC_FLAGS=-F-DREFAL_5_LAMBDA_USE_QPC -OR
set SRMAKE_FLAGS=-X-F-DREFAL_5_LAMBDA_USE_QPC -X-OR

Для чистого времени Рефала ускорение составляет 23 %, от 16,20416 секунд (84 %) до 12,44449 секунд (81 %). Доверительные интервалы понятно что не пересекаются.

Для линейного времени построения результатных выражений — 49 %, от 8,22838 секунд (43 %) до 4,19436 (27 %).

Полное время выполнения программы ускоряется на 20 %, от 19,21300 секунд до 15,36468 секунд.

Вывод

Получен измеримый прирост быстродействия. Но очень маленький, что немного обидно. Манипуляции с построением результатных выражений не смогут ускорить программу более чем на 20 %, чистое время Рефала — на 25 %, линейное построение результатных выражений — на 50 %. Время копирования контекста и te-переменных в стандартном бенчмарке составляет в сумме ≈5 % от общего выполнения программы. Так что его оптимизация тоже мало что даёт.

Предыдущий коммит ускорил время работы программы на 10 % (Total refal time), хотя является чистым рефакторингом!

Компьютер, ОС и компилятор Си++ те же, что и выше. Переменные SREFC_FLAGS, SRMAKE_FLAGS и SCRIPT_FLAGS пустые.

Вывод: BCC 5.5.1 не догадывался заинлайнить даже такие тривиальные функции. Урок для моего компилятора — встраиваемые функции также нужно уметь выделять синтаксически.

Прикреплю замеры времени на память.

Исходя из логики, следующий коммит, оптимизирующий link_adjacent, тоже должен дать измеримый прирост.

Действительно, есть измеримый прирост по сравнению с предыдущим коммитом. Но численно чуть меньше — всего 7,8 %. Может быть, из-за того, что я компилировал BCC 5.5.1 без оптимизаций и он не встроил этот вызов. Но не суть, главное — ускорение.

Для истории — замер.

Пояснение. Почему цифры меньше, чем в подробном замере выше? Потому что тогда использовался QueryPerformanceCounter() ради большей точности результатов, а он медленный. Здесь результаты заметны без точных часов, поэтому QPC не использовался.

Предыдущий коммит содержит замеры производительности. Они выполнялись на машине Intel® Core™ i5-2430M CPU @ 2.40 GHz, оперативная память 8 Гбайт, стандартным бенчмарком, 9 замеров.

Вот замеры (пустые строки были добавлены для удобства чтения):

Эта задача — подзадача для #204, а та назначена на ВКР.

Задача не была выбрана в качестве темы ВКР.

bmstu-iu9 / refal-5-lambda