Mazdaywik
commented
4 years ago Про обход поля зрения
Поле зрения даже с замыканиями несложно обойти целиком. Доказательство: выдача отладочного дампа. Поле зрения в целом плоское, «неплоскими» являются только замыкания. Но для них есть механизм разворачивания/сворачивания.
При обходе сборщиком мусора пройденные узлы помечаются как используемые, замыкания развёртываются только в случае, если голова замыкания ещё не помечена. Таким образом, обход выполняется за линейное время от числа используемых узлов.
Про уплотнение и удаление чанков
При использовании алгоритма «пометить и подмести» можно освобождать неиспользуемые чанки. Если чанк не содержит помеченных узлов, то он удаляется естественным образом. Если чанк содержит «немного» помеченных узлов и все они «перемещаемые» — их можно переместить на другие чанки, а этот освободить.
Но вообще, базовый вариант — свободные узлы из чанков объединяются в новый список свободных узлов.
К перемещаемым узлам относятся узлы символов, круглых и квадратных скобок. Значение символа достаточно скопировать в другой узел и перевязать prev и next. Круглые и квадратные скобки содержат ссылки на парные скобки, которые содержат ссылки на них. Поэтому их тоже можно подкорректировать. А вот угловые скобки и головы замыканий не перемещаемые — на них имеются ссылки извне и простого способа их исправить нет.
Во время фазы подметания нужно будет обойти все чанки и
- у используемых узлов сбросить флаг,
- неиспользуемые объединить в новый список свободных узлов.
Во время фазы подметания можно также подсчитывать число неперемещаемых (x) и свободных (f) узлов. Если чанки отсортировать по возрастанию по метрике 〈x > 0 ? 1 : 0, −f〉, то в начале будут расположены пустые чанки 〈0, −SIZE〉, затем чанки только с перемещаемыми узлами 〈0, −f〉 в порядке возрастания заполненности, затем чанки с неперемещаемыми узлами 〈1, −f〉 в порядке возрастания заполенности.
Если отсортированные таким образом чанки разместить в двусвязный список, то можно перемещать узлы из левого конца в чанки на правом конце. Узел слева отбрасывается, если он пустой (и память освобождается), узел справа отбрасывается, если он целиком заполненный. Цикл уплотнения завершается либо когда список опустел, либо когда слева оказывается чанк с неперемещаемыми узлами 〈1, −f〉, либо когда остался один чанк вида 〈0, −f〉. Если список не опустел, все свободные узлы из чанков объединяются в список свободных узлов.
Таким образом можно организовать уплотнение.
Про перемещающую сборку мусора
Перемещающую сборку мусора можно организовать двумя способами — последовательным обходом поля зрения с одновременным копированием или алгоритмом Чени.
Алгоритм Чени описан в Книге дракона, дублировать мне его лень. В данном случае мы бежим по диапазону unscanned и для каждого из узлов обновляем поля next, prev и link_info (если оно актуально). Алгоритм надёжно скопирует всё поле зрения, но порядок будет весьма странным. Допустим, у некоторого узла поле next ссылается на открывающую скобку и она не была просканирована. Тогда процедура LookupNewLocation скопирует узел скобки. Когда сканирование дойдёт до неё, обновятся prev (на ранее скопированный узел), next (на следующий узел) и link_info (на парную скобу). Два последних обновления скопируют в новую кучу следующий узел и парную скобку. Следующий узел (допустим, простой символ) просто скопирует своего соседа по next, а парная скобка — скопирует next и prev. Далее будут чередоваться последующие узлы после левой скобки, узлы после правой скобки, и узлы до правой скобки в обратном порядке.
Будет ли такой вариант оправдан — можно понять только экспериментально. Потому что по соседству со скобкой окажется и парная скобка, а от парной скобки сканирование может выполняться и вглубь, и вправо. В общем, локальность обеспечивается.
Копирование последовательным проходом потребует обновления ссылок link_info. Как это решить? Узлы элементов, на которые бывают ссылки (скобки, головы замыканий) в старой куче превращаются в «заместители» (placeholders). Заместитель имеет тег «заместитель» и ссылку на узел в новой куче.
Когда копируется открывающая круглая (квадратная) скобка, для неё создаётся заместитель. Когда копируется закрывающая скобка, её link_info ссылается на заместителя, который ссылается на новую открывающую скобку. Они тривиально провязываются.
Когда копируется угловая скобка — для неё просто создаётся заместитель, ссылка в скобке сохраняется. После обхода поля зрения стек принимает причудливый вид: «заместитель <» → «<» → «заместитель >» → «>» → … Понятно, что в этом списке нужно удалить каждый второй элемент.
Если узел-замыкание ссылается на голову замыкания — развёртываем его, копируем, свёртываем и превращаем голову в заместителя. Если замыкание ссылается на заместитель — в копии ссылаемся адресом из заместителя. При копировании головы замыкания устанавливаем признак «уникальный». Если копируется узел замыкания, ссылающийся на заместитель, устанавливаем признак «скопированный».
Если признак «уникальный»/«скопированный» находится в голове замыкания — всё просто. Если в самом узле-замыкании, то заместитель должен хранить не только ссылку на новую голову, но и обратную ссылку на исходный узел.
Да, в сборщике Чени все скопированные узлы переинициализируются в заместители.
Так что «пометить и подмести» проще копирующего сборщика.
Кратко
Возможно, замена счётчиков ссылок для замыканий на сборку мусора способна поднять быстродействие программ на Рефале-5λ.
Обоснование
В поле зрения узлов замыканий не так много, но накладные расходы на них могут быть велики. А именно, при выделении памяти для новых узлов поля зрения требуется проверка, является ли узел замыканием. Если является, то нужно декрементировать его счётчик и т.д.
https://github.com/bmstu-iu9/refal-5-lambda/blob/f4e56e653f21232a60374ba6a998f3f4d42fb7de/src/srlib/refalrts-vm.cpp#L562-L577
Конечно, условие здесь почти всегда не выполняется, а значит затраты на ветвление будут сравнительно малы (предсказатель будет угадывать). Но тем не менее они будут (около двух тактов, см. здесь).
При копировании переменных проблема выражена не так явно, поскольку там всё равно требуется ветвление для провязывания скобок при копировании.
Конечно, если «в лоб» выкинуть счётчик ссылок и ввести сборку мусора, эту ветку из
alloc_node()можно будет удалить. Но возникнет другая проблема.Счётчик ссылок для замыканий выполняет две важные задачи:
1, поэтому при его вызове контекст можно переместить вместо копирования.Случай единственного замыкания не редкий. Как блоки и присваивания неявно представляются как вложенные функции, для них, строится замыкание и тут же вызывается — их выполнение требует константного времени. Устаревшая функция
Fetch(которая сейчас используется только вместе сPipe) свой аргумент тоже не копирует, поэтому конструкция<Fetch … { … }>тоже должна вычисляться за константное время.Прямолинейный переход к сборке мусора приведёт к тому, что контекст при вызове придётся копировать всегда. А значит, возможно, потребуется менять кодогенерацию, и вызовы вроде
<Fetch … { … }>и<Fetch … <Pipe {…} {…} …>>будут выполняться совсем не эффективно.Наблюдение: если замыкание скопировалось один раз, то оно скорее всего будет копироваться неоднократно. Например, в функции
Mapзамыкание применяется к каждому элементу последовательности.Поэтому можно счётчик ссылок заменить булевским флагом, который при копировании узла устанавливается в истину.
Можно избежать ветвления и при копировании. В этом случае булевский флаг вынести на уровень самого узла поля зрения. Он будет актуален для узлов замыканий, для остальных узлов (символы и скобки) смысла не несёт. При копировании он устанавливается в истину как для копии, так и для оригинала. Операция записи согласно этому материалу выполняется менее чем за такт, поскольку выполняется параллельно с другими вычислениями.
Но будет ли этот трюк оправдан, нужно определять экспериментально. Потому что, опять же, при копировании t- и e-переменных и так требуется ветвление для перепровязывания скобок, а копирование s-переменной само по себе имеет накладные расходы (целая команда на копирование одного узла).
Размышления о сборке мусора
Какую сборку мусора сделать: пометить-и-подмести или копирующую?
Первая, скорее всего, будет выполняться быстрее, поскольку требует просмотра поля зрения, а не его копирования. При обходе поля зрения или содержимого очередного замыкания потребуется обращать внимание лишь на тег узла, игнорируя содержимое. Копирующий сборщик мусора будет вынужден делать запись в новый узел и для тега, и для данных.
Преимуществом копирующего сборщика будет локализация данных — соседние узлы поля зрения в копии будут располагаться в смежных ячейках. Это может положительно сказаться общей скорости выполнения программы. Также копирующий сборщик мусора позволит программе уменьшать занятую память. Новые узлы распределяются в свежевыделенной памяти, а старые чанки можно скопом удалить.
По видимому, нужно реализовать тот вариант, который проще (а проще, вроде, пометить-и-подмести), и вообще решать вопрос экспериментально.
Динамические ящики и дескрипторы функций
Сборка мусора позволяет реализовать и динамические ящики. Реализовывать динамические ящики при помощи счётчиков ссылок не стоит, поскольку в этом случае возможны утечки памяти из-за кольцевых структур. А с нормальным сборщиком мусора никаких препятствий нет.
Кроме того, можно решить проблему освобождения дескрипторов функций после выгрузки модуля. Сначала дескрипторы использовали счётчик ссылок (#101, #100), но это пагубно сказывалось на быстродействии. Потом они стали вообще освобождаться при завершении программы (#203). Со сборкой мусора их можно чистить при, собственно, сборке мусора. Более того, можно чистить память идентификаторов, созданных при помощи
Implode.