Компактное списковое представление Рефала

[Александр Коновалов a.v.konovalov87_AT_mail.ru]

Добрый вечер всем!

Я опять нахожу что-то интересное в других языках программирования и натягиваю это на Рефал.

Сегодня я напишу про CDR-кодирование списков в Лиспе и адаптацию этой идеи для спискового представления Рефала. Заранее прошу прощения за лонгрид.

 

В языках семейства Лисп (дальше я для краткости буду просто писать «Лисп») основной структурой данных является однонаправленный список, представленный при помощи т.н. cons-пар или cons-ячеек — звеньев списка. Cons-пара — кортеж ‹голова, хвост›, первый элемент может хранить произвольное значение, второй — как правило, хранит либо указатель на следующую cons-ячейку списка, либо особое значение «пустой список». Некоторые языки семейства позволяют хранить во втором элементе не только список, а вообще произвольное значение — получаются т.н. «неправильные списки».

Создание cons-ячейки выполняется операцией (cons x xs), получение головы и хвоста традиционно называются (car xs) и (cdr xs), соответственно.

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

Для оптимизации хранения было предложено т.н. CDR-кодирование (применялось, например, в лисп-машинах):

https://en.wikipedia.org/wiki/CDR_coding

Идея следующая. По умолчанию в cons-ячейке второй компонент представлен как указатель, который ссылается на следующее звено. Но есть и сжатый вариант — по смещению второго компонента находится не указатель на следующее звено, а непосредственно само следующее звено!

Это не очень очевидно, но разобраться надо, иначе вторая часть письма про Рефал будет непонятна.

Изобразить на языке Си такое невозможно (непросто и непонятно), поэтому попытаюсь объяснить словами. Пусть интерпретатор хранит в указателе *p адрес текущей cons-ячейки и он хочет выполнить операцию cdr — перейти к следующему звену списка. Если cons-ячейка обычная, то нужно к указателю прибавить смещение хвоста (обозначим его как CDR_OFFSET), по смещению будет находиться указатель, хранящий адрес следующей ячейки, его необходимо будет разыменовать:

p = *(p + CDR_OFFSET);

Если cons-ячейка сжатая, то следующее звено будет непосредственно по смещению p + CDR_OFFSET:

p = p + CDR_OFFSET;

Т.е. сжатый список представляется как размещённые в памяти «встык» cons-ячейки, у которых «обрезан» второй указатель.

Если список сжатый, то мы получаем два преимущества:

1. Указатели на следующие звенья не хранятся, что даёт экономию памяти ⅓ или ½ в зависимости от реализации.
2. Полезная нагрузка звеньев хранится в памяти по соседству — данные располагаются рядом, проход по списку реализуется инкрементом указателя — это позволяет эффективнее использовать кэш процессора.

Недостатки:

1. Хвост списка может входить только в один сжатый список: если выполним (cons 1 xs), (cons 2 xs) и (cons 3 xs), то сжатое звено создаст максимум первый вызов — припишет обрезанную cons-ячейку с головой 1 перед списком xs, остальные вызовы вынуждены будут создать обычные cons-ячейки, где вторым компонентом будет указатель.
2. Список должен быть неизменяемым, т.к. присвоить новое значение хвосту сжатого звена невозможно.

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

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

 

Этот абзац можно пропустить. Остановлюсь поподробнее, почему экономия памяти может составлять ½ или ⅓ — это полезно для иллюстрации, позволит лучше понять перенос идеи на Рефал.

Лисп — динамически типизированный язык, тип значения определяется во время выполнения. Если набор типов данных фиксирован, то данные представляются в виде размеченного объединения — кортежа ‹тег, значение›, где тег хранит номер типа, и определяет содержимое поля «значение», его размер равен размеру наибольшего из типов. Поскольку тип и головы, и хвоста может быть любым, то cons-ячейку можно представить кортежем кортежей:

‹‹тег, значение›, ‹тег, значение››

Значением может быть либо примитивное значение (вещественное или целое число ограниченной разрядности, код символа), либо указатель (на другую cons-ячейку, на функцию, на строку символов). Для простоты можно предположить, что память хранит только cons-ячейки и таким образом выглядит как массив чётной длины пар ‹тег, значение› (по чётным — головы, по нечётным — хвосты, нумерация с 1):

‹тег, значение›, ‹тег, значение›, …, ‹тег, значение›, ‹тег, значение›

Для представления сжатой cons-ячейки нужно в поле тега добавить битовый флаг «это голова», который у головы всегда установлен, а для «обычного» хвоста — никогда. Обычная cons-ячейка будет выглядеть как

‹тег¹, значение›, ‹тег°, значение›

Если мы хотим выполнить операцию cdr, то мы должны посмотреть на второй компонент.

1. Если там флаг не установлен — значит, пара ‹тег°, значение› и является хвостом (как правило тег является тегом указателя на пару и значение, соответственно, указателем, либо тег является особым значением «пустой список», а поле значения игнорируется, но для неправильных списков там может быть что угодно).
2. Если флаг установлен, то хвостом будет пара ‹ТЕГ_СПИСКА, адрес второго компонента›.

Сжатый список в памяти будет выглядеть так:

‹тег¹, значение›, ‹тег¹, значение›, ‹тег¹, значение› … ‹тег°, значение›

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

В таком представлении списка экономия памяти для сжатого списка составит 50 %.

 

Однако, представлять cons-ячейку как пару пар ‹‹тег, значение›, ‹тег, значение›› не всегда целесообразно. Например, если мы разрабатываем для 64-разрядной архитектуры и должны поддерживать вещественные числа (тип double в Си), то поле значения должно занимать целое машинное слово (64 бита — размер указателя и double) и должно быть выровнено по границе машинного слова. Тогда кортеж ‹тег, значение› должен будет занимать аж 2 машинных слова, т.е. на тег придётся потратить 8 байт, хотя по факту в нём будут использоваться только полдюжины битов! В этом случае целесообразнее представлять cons-ячейку тремя машинными словами: ‹‹тег, тег›, ‹значение›, ‹значение››, храня в первом слове теги для каждого из значений. Сжатая cons-ячейка будет представлять собой «обрубок» ‹‹тег, тег, 1›, ‹значение››, которое приписывается перед другой cons-ячейкой, несжатая — ‹‹тег, тег, 0›, ‹значение›, ‹значение›› (здесь я добавил в первое слово к тегам признак сжатости). Сжатый список будет тогда выглядеть вот так:

‹тег, тег, 1›, ‹значение›, ‹тег, тег, 1›, ‹значение›, … ‹тег, тег, 0›, ‹значение›, ‹значение›

Т.к. полная ячейка здесь занимает 3 слова, а сжатая — 2, то экономия памяти будет составлять 33 %. Кстати, если значение хвоста определяется только тегом (например, это константа «пустой список» или булевская константа), то его тоже можно представлять сжатой cons-ячейкой, функция cdr будет для него просто возвращать синглетон.

В этом представлении переход к следующему звену у обычной cons-ячейки будет соответствовать прибавлению к указателю смещения в 2 слова и разыменованию (по этому адресу лежит значение-указатель), у сжатой — просто прибавлению смещения в 2 слова.

 

Теперь переходим к Рефалу.

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

(Если значение не помещается в одно слово, например, нужно поддерживать double на 32-разрядной платформе, то тоже можно влезть в 4 слова — для этого нужно использовать NaN-упаковку. Что это такое, можно прочитать, например, здесь: https://piotrduperas.com/posts/nan-boxing#is-it-madness).

О чём это я. На хранение одного элемента поля зрения уходят 4 слова, 2 из которых — указатели! Т.е. половина памяти уходит на связи между звеньями, локальность данных ужасная. Я делал замеры для Рефала-5λ и Рефала-05, самая медленная операция — инициализация очередного звена из списка свободных узлов, сплошные промахи кэша. Это из-за связных списков.

Леонид Константинович Эйсымонт когда-то создал реализацию Рефала, использующую односвязные списки ради экономии памяти на 25 %. Платить за это приходится стилем программирования — сопоставление справа налево выполняется с линейной сложностью.

Ниже предлагается оптимизация по памяти списковой реализации Рефала, позволяющая экономить до 50 % — сделать указатели вперёд и назад опциональными.

Идея та же, что и в Лиспе — на месте указателя размещать полезную информацию.

Полезная нагрузка — эта пара слов «тег» и «значение». Далее будем обозначать слово тега — T, значения — V, указатель вперёд — N, назад — P. Тогда полезную нагрузку можно изобразить кортежем ‹T, V›. Обычное несжатое звено изобразим так:

‹P, T, V, N›

Обратите внимание — указатели расположены по краям. Так мы можем заменять каждый из них на полезную нагрузку независимо. При этом указатель на звено будет являться указателем на слово тега T: смещение T равно 0 (здесь и далее смещения в словах), смещение V — +1, смещение N — +2, смещение P — −1 (отрицательное смещение). Несжатое звено в памяти будет выглядеть так:

…, P, T°°, V, N, …

Для перехода к следующему звену нужно к адресу звена прибавить 2 и разыменовать — пройти по указателю N. Для перехода к предыдущему — вычесть 1 и разыменовать — пройти по указателю P.

Если два звена примыкают друг к другу, то у левого звена нет указателя N — на его месте полезная нагрузка второго звена, у правого — P — там содержимое первого звена:

… P, T°¹, V, T¹°, N, …

Если несколько звеньев примыкают друг к другу, то указатели сохраняются только у крайних звеньев, получается своего рода «макрозвено» (далее будем писать этот термин без кавычек):

… P, T°¹, V, T¹¹, V, T¹¹, V, T¹°, V, N, …

В случае, если следующее звено примыкает, то для перехода на него нужно к указателю на текущее (т.е. указателю на его слово тега T) нужно просто прибавить 2. Если примыкает предыдущее, то для перехода назад — вычесть 2.

Длиной макрозвена будем называть количество пар ‹T, V› между указателями P и N. Обычное несжатое звено — макрозвено длины 1, его флаги 00. У сжатого макрозвена (длины 2 и более) флаги крайних звеньев 01 и 10, средних — 11.

 

Основные операции с двусвязным списком: итерация в обоих направлениях и перенос (трансплантация, slice) части списка в другую позицию. Последняя операция делится на рассечение списка в соответствующих местах и последующую склейку.

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

Пусть у нас есть следующее макрозвено:

… P, Ta°¹, Va, Tb¹¹, Vb, Tc¹¹, Vc, Td¹¹, Vd, Te¹°, Ve, N, …

и нам его нужно рассечь между ‹Tb, Vb› и ‹Tc, Vc›. Слова в памяти располагаются последовательно, поэтому воткнуть пару указателей N’, P’ между ними невозможно. Но можно перезаписать какие-либо имеющиеся слова. Выделим в свободной памяти обычное несжатое звено и скопируем в него ‹Tc, Vc›:

… P, Ta°¹, Va, Tb¹¹, Vb, Tc¹¹, Vc, Td¹¹, Vd, Te¹°, Ve, N, …, …, ?, Tc°°, Vc, ?, …

Теперь на место слов Tc¹¹ и Vc можно записать указатели с адресом свежевыделенного звена и наоборот (внимание на флаги Tb и Td):

… P, Ta°¹, Va, Tb¹°, Vb, Ac, Ac, Td°¹, Vd, Te¹°, Ve, N, …, …, Ab, Tc°°, Vc, Ad, …

Здесь Ac — адрес слова Tc°°, Ab — адрес Tb¹°, Ad — адрес Td°¹. Т.е. мы разбили одно макрозвено на три — сначала разбили на два, превратив одно из звеньев в две ссылки, для затёртого звена выделили в памяти новое несжатое звено, и вставили его между двумя исходными.

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

 

Принцип вот такой. Дальше уже детали реализации:

• Подход применим и к плоским спискам (Рефал-2, Рефал-5), и к подвешенным скобкам (FLAC, Рефал-6).
• При создании новых звеньев для правой части можно сразу распределять их сжатыми, за исключением тех мест, куда нужно будет вставить значения e-переменных (для плоских списков — и t-переменных). В частности, копирование e-переменных (t-переменных) может сразу порождать копии из целиковых макрозвеньев.
• При переносе e-переменной (t-переменной) может потребоваться «освободить» и первое, и последнее звено, если концы переменной попадают в середины макрозвеньев.
• Одна из оптимизаций: если край переносимой переменной попадает в середину макрозвена и граничит с ненужным элементом, то этот элемент можно превратить в пару указателей (например, в таком предложении e.X A e.Y = e.Y e.X; ненужным элементом будет символ «A»). Первыми кандидатами на удаление (превращение в пару указателей) могут быть скобки активации.
• В процессе работы макрозвенья часто будут рассекаться, память будет фрагментироваться, периодически нужно будет выполнять уплотнения.
• Самый простой вариант уплотнения — использовать алгоритм копирующей сборки мусора Чени, немного адаптированный под задачу. Недостаток: нужно выделить новую кучу того же размера и в неё всё скопировать, старую кучу удалить.
• Возможны более сложные и более медленные варианты уплотнения поля зрения, требующие меньше дополнительной памяти — их можно использовать, когда памяти недостаточно.
• В любом случае, полное уплотнение всего поля зрения очень накладно, нужны стратегии частичного уплотнения, сжимающие недавно изменённые участки поля зрения. Можно делать что-то похожее на запомненное множество в сборке мусора по поколениям.
• В списке свободных узлов могут находиться смежные участки памяти в произвольном порядке — нужна процедура обхода, которая смежные участки конкатенирует в «пустые» макрозвенья, её сложность можно сделать линейной от числа звеньев в списке свободных узлов.
• Это компактное представление является прозрачной оптимизацией двусвязного списка — на сложность базовых операций Рефала не влияет: итерация в обе стороны и перенос за O(1), как и для обычных списков, уплотнения поля зрения и списка свободных звеньев амортизируются.
• Экономится память и повышается локальность данных, что благоприятно для кэша. Но реализация заметно усложняется — оправдывается ли это?

 

В общем, хорошая задача для исследования. Подходит на курсовую по компиляторам и ВКР бакалавра.

 

С уважением,
Александр Коновалов