Подумать о сборке мусора

Кратко
====
Возможно, замена счётчиков ссылок для замыканий на сборку мусора способна поднять быстродействие программ на Рефале-5λ.

Обоснование
=========
В поле зрения узлов замыканий не так много, но накладные расходы на них могут быть велики. А именно, при выделении памяти для новых узлов поля зрения требуется проверка, является ли узел замыканием. Если является, то нужно декрементировать его счётчик и т.д.

https://github.com/bmstu-iu9/refal-5-lambda/blob/f4e56e653f21232a60374ba6a998f3f4d42fb7de/src/srlib/refalrts-vm.cpp#L562-L577

Конечно, условие здесь почти всегда не выполняется, а значит затраты на ветвление будут сравнительно малы (предсказатель будет угадывать). Но тем не менее они будут (около двух тактов, см. [здесь](https://habr.com/ru/company/otus/blog/343566/)).

При копировании переменных проблема выражена не так явно, поскольку там всё равно требуется ветвление для провязывания скобок при копировании.

Конечно, если «в лоб» выкинуть счётчик ссылок и ввести сборку мусора, эту ветку из `alloc_node()` можно будет удалить. Но возникнет другая проблема.

Счётчик ссылок для замыканий выполняет две важные задачи:
1. Осуществляет контроль памяти — это понятно.
2. Оптимизирует вызов единственного замыкания. Если в поле зрения замыкание существует в единственном экземпляре, то его счётчик ссылок равен `1`, поэтому при его вызове контекст можно переместить вместо копирования.

Случай единственного замыкания не редкий. Как блоки и присваивания неявно представляются как вложенные функции, для них, строится замыкание и тут же вызывается — их выполнение требует константного времени. Устаревшая функция `Fetch` (которая сейчас используется только вместе с `Pipe`) свой аргумент тоже не копирует, поэтому конструкция `` тоже должна вычисляться за константное время.

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

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

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

Можно избежать ветвления и при копировании. В этом случае булевский флаг вынести на уровень самого узла поля зрения. Он будет актуален для узлов замыканий, для остальных узлов (символы и скобки) смысла не несёт. При копировании он устанавливается в истину как для копии, так и для оригинала. Операция записи согласно [этому материалу](https://habr.com/ru/company/otus/blog/343566/) выполняется менее чем за такт, поскольку выполняется параллельно с другими вычислениями.

Но будет ли этот трюк оправдан, нужно определять экспериментально. Потому что, опять же, при копировании t- и e-переменных и так требуется ветвление для перепровязывания скобок, а копирование s-переменной само по себе имеет накладные расходы (целая команда на копирование одного узла).

Размышления о сборке мусора
=====================
Какую сборку мусора сделать: пометить-и-подмести или копирующую?

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

Преимуществом копирующего сборщика будет локализация данных — соседние узлы поля зрения в копии будут располагаться в смежных ячейках. Это может положительно сказаться общей скорости выполнения программы. Также копирующий сборщик мусора позволит программе уменьшать занятую память. Новые узлы распределяются в свежевыделенной памяти, а старые [чанки](https://github.com/bmstu-iu9/refal-5-lambda/blob/f4e56e653f21232a60374ba6a998f3f4d42fb7de/src/srlib/refalrts-dynamic.h#L294-L316) можно скопом удалить.

По видимому, нужно реализовать тот вариант, который проще (а проще, вроде, пометить-и-подмести), и вообще решать вопрос экспериментально.

Динамические ящики и дескрипторы функций
===============================
Сборка мусора позволяет реализовать и динамические ящики. Реализовывать динамические ящики при помощи счётчиков ссылок не стоит, поскольку в этом случае возможны утечки памяти из-за кольцевых структур. А с нормальным сборщиком мусора никаких препятствий нет.

Кроме того, можно решить проблему освобождения дескрипторов функций после выгрузки модуля. Сначала дескрипторы использовали счётчик ссылок (#101, #100), но это пагубно сказывалось на быстродействии. Потом они стали вообще освобождаться при завершении программы (#203). Со сборкой мусора их можно чистить при, собственно, сборке мусора. Более того, можно чистить память идентификаторов, созданных при помощи `Implode`.