Левоионные идеи в сфере программирования (50 стр)

Чтобы вы лучше поняли формат, опишу обратный процесс сериализации.

Фаза 1: поддеревья рекурсивно линеаризуются в списки токенов.
Пустое дерево (случай срабатывает только для корня)    ->    [ нулл ]
"ключ" ( нулл ; нулл )    ->    [ "ключ" ]
"ключ" ( нулл ; правое )    ->    [ "ключ", Р ] ++ лин правого
"ключ" ( левое ; правое )    ->    [ "ключ", Л ] ++ лин левого ++ [ У ] ++ лин правого
"ключ" ( левое ; нулл )    ->    [ "ключ", Л ] ++ лин левого ++ [ У, нулл ]

Умные ребята заметят, что порядок ключей, который получится в такой линеаризации — это depth-first preorder.

(на данном этапе пока что считаем, что ключ "У" и контрольный символ У это разные вещи)

Фаза 2: из полученного списка токенов, с конца удаляются все повторения [ У, нулл ].

Фаза 3: для всех ключей, заключённых между двумя У, производим Н-вложение:
    нулл — преобразуется в "" (пустую строку)
    "" — преобразуется в "Н"
    "Н" повторённая k раз — преобразуется в "Н", повторённый k+1 раз
    все остальные строки остаются как есть
Либо, если весь список состоит только из одного токена (у нас был только один голый рут, или вообще пустое дерево без нодов) — один этот токен тоже претерпевает Н-вложение.

На данном этапе, в списке токенов больше не должно оставаться никаких нуллов.

Фаза 4: экранирование. На этой фазе мы вводим понятие "глубины". Идя по списку токенов слева направо, начиная с глубины=0, на каждый Л — глубина++, на каждый У — глубина--. То есть Л и У — это своего рода такие скобочки.

Для токенов-ключей на глубине 0 — мы за "чувствительные символы" считаем набор "ЛР", на глубине от 1 и глубже — более широкий набор "ЛРУ".

(у нас по построению гарантируется, что из глубины 0 команд У никогда не будет и в минуса мы не уйдём)

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

Кроме того, если этот ключ не последний в списке токенов — то у него ещё удваиваются все подряд идущие "Э" на конце.

Например:
    [ "АЭБЭУЭФЭРЭСЭ", Л, "АЭБЭУЭФЭРЭСЭ" ]
экранируется в:
    [ АЭБЭУЭФЭЭЭРЭСЭЭ, Л, АЭБЭЭЭУЭФЭЭЭРЭСЭ ]

После экранирования — токены теперь можно сконкатенировать в одну итоговую строку.

Описанные выше декодер — просто прогоняет эти же преобразования в обратную сторону: сначала разделяет строку на токены, с учётом глубино-зависимого экранирования, разэкранирует ключи, а затем обратно собирает дерево по ЛРУ-командам, по ходу дела ещё разделывая Н-вложение там где оно было сделано.

Я пока твой алгоритм не смог вместить в голову (слишком уж неортогональный, части вываливаются из головы), но вот насчет сериализации - а при наличии на конце ключа букв ЭУ, ЭЭУ, ЭЭУУ, ЭЭУЭУ при наличии или отсутствии необходимости софрмировать команду У там точно все нормально и все случаи нормально покрываются?

Dmitry_Milk
> Я пока твой алгоритм не смог вместить в голову (слишком уж неортогональный, части вываливаются из головы), но вот насчет сериализации - а при наличии на конце ключа букв ЭУ, ЭЭУ, ЭЭУУ, ЭЭУЭУ при наличии или отсутствии необходимости софрмировать команду У там точно все нормально и все случаи нормально покрываются?
Там где по глубине У допускается как команда:
    (2*k)*"Э" + "У"    ->    означает k*"Э" ключевых, за которыми идёт команда У.
    (2*k+1)*"Э" + "У"    ->    означает все ключевые буквы, k*"Э" + "У".

Имбирная Ведьмочка, ты говоришь про десериализацию. Я спрашиваю про сериализацию, где на конце ключа могут быть любые количества букв ЭУРЛ, и после обратной десериализации они должны восстановиться (и надо посмотреть это в случаях, когда надо делать команду У и когда не надо, и при пустом/непустом стеке).

Dmitry_Milk
> Имбирная Ведьмочка, ты говоришь про десериализацию. Я спрашиваю про сериализацию, где на конце ключа могут быть любые количества букв ЭУРЛ, и после обратной десериализации они должны восстановиться (и надо посмотреть это в случаях, когда надо делать команду У и когда не надо, и при пустом/непустом стеке).
Фаза 4 выше описывает же всё, даже с примером. Там где изначально буква — делает так чтобы декодер прочитал букву, там где должна быть команда — делает так чтобы декодер прочитал команду. :)

Dmitry_Milk
Можно рассматривать мою схему экранизации как префиксное кодирование, где символами более бедного алфавита мы записываем строки из более богатого (в котором больше символов).

Например, если мы применим аналогичную схему, чтобы записать 4-ричные строки из "абв+" через 3-ичный алфавит "АБВ", используя В как экранирующий маркер и Б как контрольный символ, то это можно расписать таким деревом кодов:
А -> а
Б -> +
В$ -> в$ (где знак доллара — конец потока)
ВА -> ва
ВБ -> б
ВВ$ -> вв$
ВВА -> вва
ВВБ -> в+
ВВВ$ -> ввв$
ВВВА -> ввва
ВВВБ -> вб
ВВВВ$ -> вввв$
ВВВВА -> вввва
ВВВВБ -> вв+
ВВВ...

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

И конкретно в сериализации деревьев — мы используем то же самое построение, только с инкрементальными наворотами — контрольных символов больше одного, и ещё в зависимости от контекста кодировка переключается между (буквы+2) и (буквы+3) — где "контрольный Л", "контрольный Р" и "контрольный У" считаются отдельными символами алфавита от "ЛРУ" в ключах.

Имбирная Ведьмочка, с самим принципом экранирования вроде как понятно.

А вот с построением деревьев - все равно в голове не получается увидеть всей картины. С экранирование разных символов в разных контекстах (LR/LRU) и убиранием финальной цепочки U, закрывающей остатки дерева, еще более-менее понятно - мы избавляемся от неудобной ситуации соответствия "закрывашек" просто вообще их не записывая и не экранируя в нодах, лежащих на правом краю дерева.

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

Но вообще это ж Девилу решать, ему же требуется. Я бы пока на его месте не рискнул использовать, не имея гарантий корректности.

Рисуй пентаграмму, зажигай свечи :)

Вот вариант с интами - точно рабочий, т.к. там через мат.индукцию видно корректность решения. Но там другая беда - безразмерные инты растут как на дрожжах.

Что касается меня - слишком уж далеко зашло от "дай ка я пораскину мозгами над интересной задачкой".

Задачка подлая, кажется "вот-вот, нашел!" и затягивает, но всегда находится что-то обламывающее, а потом по кругу. Надо завязывать и признать, что я слил решить ее самостоятельно :(

Я придумал новый алгоритм для сборки мусора: "полифазная маркировка".

На очень высоком уровне абстракции, mark-and-sweep-мусорщика можно представить таким алгоритмом:

    1. Окрасить все объекты в "белое".
    2. Перекрасить корневое множество в "серое".
    3. Пока существует хотя бы один "серый" объект:
        3а. Взять произвольный "серый" объект.
        3б. Перекрасить взятый объект в "чёрный".
        3в. Для каждой ссылки внутри взятого объекта:
            3вв -> Если цель ссылки "белая" — перекрасить её в "серое".
    4. Итог: "чёрные" объекты живые, "белые" собираются в мусор.

Цикл в 3-3а может реализовываться по-разному. Самый распространённый вариант — это держать "серые" объекты фифо-стеком — тогда мусорщик по факту будет просто обходить граф в глубину. Но там могут быть и навороты понавороченнее, например — объекты с только одним полем-указателем брать вне очереди, чтобы не дать стеку вырасти слишком длинным.

А вот один чувак, назовём его Дейкстра, абсолютный мэдмэн, предложил сделать так: не делать для "серых" никаких отдельных контейнеров, а вместо этого просто писать цвет в самом объекте, а в главном цикле — тупо шпалировать по всей куче слева направо, обрабатывать объекты по мере как попадутся под руку, и так несколько раз пока на очередном проходе больше не останется никаких "серых".

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

И вот, собственно, теперь ключевая идея — а что, если не делать сразу все 15 проходов друг за другом, а только один проход за одну остановку мира, но зато сразу за несколько сборок одновременно?

То есть, на первой остановке — мы прошли один раз, покрасили какие-то объекты в "серый" — но повторные проходы делать не стали, а так и оставили, и вернули управление обратно мутатору. Когда пришло время второй мусоросборочной остановки — вот тогда сделали второй проход, "серые" с прошлого прохода теперь перекрасятся в "чёрные", а на смену им придут "серые второго поколения". Когда затем будет третья остановка — тогда сделаем третий проход, и фронт маркировки продвинется ещё на одну стадию дальше.

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

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

Хотя на самом деле, нам и не нужен полный вектор. Если объект подсвечен "серым" или "чёрным" на сборке номер Н — то его статус на прошлых сборках Н-1, Н-2 и так далее нам уже по факту и не важен — мы уже точно знаем, что это не мусор. Поэтому, на самом деле, для хранения стейта этой маркировки нам достаточно только одного целого числа — номер самой последней сборки, которая дошла до этого объекта, плюс один бит для различения "серого" и "чёрного".

Хотя на самом деле, нам и не нужен точный номер сборки, а достаточно обратной величины — минимальное число полных проходов по куче, чтобы долить краску от рут-сета до этого объекта. Для самого рут-сета — это, разумеется, ноль. Если объект А ссылается на объект Б, и при этом по направлению обхода Б идёт после А — то А и Б будут оба с одним номером (если только у Б нет более короткого пути от корня). Если же Б лежит раньше А — то это +1 к номеру.

В динамике, мутатор может переставить объект с маленьким номером на более длинный путь — тогда ему потребуется несколько итераций, чтобы "осесть" на свою законную глубину. То есть, если рассмотреть кратчайший путь от корня и по нему посчитать все +1-инверсии — то получится только верхняя граница, реальный номер у объекта может быть равен этой границе, а может быть и меньше. А вот если объект отсоединили от графа — то без обновлений от соседей, его номер будет расти и расти, пока не перерастёт за "границу мусора" — вот тогда мы его и соберём.

А в целом, алгоритм получается такой:

    extern let root_set: BPTree<Addr>;

    let phase_delay: ParallelMap<Addr, u32> = {};
    let garbage_threshold = 0
    let old_back_refs: Vec<(Addr, u32)> = {};

    fn alloc() -> Addr {
        let a = new_addr();
        phase_delay[a] = garbage_threshold;
        return a;
    }

    fn polyphase_mark_sweep() {
        let new_back_refs: Vec<(Addr, u32)> = {};
        let fwd_refs: HashMap<Addr, u32> = {};
        let gray_top = 0;

        let root_set_iter = root_set.begin();
        let old_back_ref_iter = old_back_refs.begin();
        let a = heap_start;
        while a != heap_end {
            if phase_delay[a] > garbage_threshold {
                free(a);
            } else {
                let new_pd = phase_delay[a] + 1;
                if root_set_iter && *root_set_iter == a {
                    new_pd = 0;
                    root_set_iter++;
                }
                while old_back_ref_iter && (*old_back_ref_iter).0 == a {
                    new_pd = min(new_pd, (*old_back_ref_iter).1);
                    old_back_ref_iter++;
                }
                if let Some(fpd) = fwd_refs.get(a) {
                    new_pd = min(new_pd, fpd);
                    fwd_refs.erase(a);
                }
                if new_pd <= phase_delay[a] {
                    gray_top = new_pd;
                }
                phase_delay[a] = new_pd;
                for each ra in object_refs(a) {
                    if ra < a {
                        new_back_refs.push( (ra, new_pd + 1) );
                    } else if ra > a {
                        fwd_refs.set_or_update(new_pd, \fpd -> min(fpd, new_pd));
                    }
                }
            }
            a = next_object(a);
        }

        garbage_threshold = gray_top;
        new_back_refs.sort();
        old_back_refs = new_back_refs;
    }

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

Рут-сет — это B+ Tree, внешний управляющий может добавлять и удалять руты за логарифмическое время, а сам сборщик — сканирует его вместе с самой кучей по порядку адресов.

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

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

Сами номера — хранятся отдельно от объектов по параллельным адресам, то есть, phase_delay[a] это на самом деле phase_delay_data[(a - heap_start) / allocation_granularity]. Сделано это затем, чтобы работа сборщика не загрязняла кэш-линии и страницы памяти с самими данными.

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

А ещё можно провести такую модификацию — делать обход кучи не по одному объекту, а перемежающимися окнами фиксированной ширины — при этом в back_refs и fwd_refs складывая только ссылки за пределы окна, а внутри него — всё красить и обходить сразу, как в классическом марк-и-свипе.

По идее, такой сборщик как раз должен хорошо подходить к игровым движкам — очень удобно вызывать такую сборку под конец фрейма. Так как он выполняет примерно фиксированное количество работы, по данным которые и так используются в гейм-логике — то это будет стабильная нагрузка на фпс, а не периодические фризы. А как известно, 50 стабильных фпс лучше, чем 100 лагающих.

Имбирная Ведьмочка
> так как он делает линейный проход по памяти, а не прыгает туда-сюда по указателям, это делает его более дружелюбным к кэшу.
Так при перекраске объектов по исходящим ссылкам всё равно придётся прыгать непредсказуемым образом.

> все 15 проходов
В наихудшем случае (линейный связный список из 100500 элементов, расположенных на куче в обратном порядке) - 100501 проход, в течение которых все объекты будут здравствовать. Так что не зря того чувака назвали Дейкстрой.

> if phase_delay[a] > garbage_threshold {
> free(a);
А правильно ли использовать тут garbage_threshold от предыдущего прохода, а не который должен получиться по результатам текущего?

Sbtrn. Devil
> Так при перекраске объектов по исходящим ссылкам всё равно придётся прыгать непредсказуемым образом.
>
> В наихудшем случае (линейный связный список из 100500 элементов, расположенных на куче в обратном порядке) - 100501 проход, в течение которых все объекты будут здравствовать. Так что не зря того чувака назвали Дейкстрой.
Ну а я вот взял и исправил оба недочёта. :)

В теории, можно ещё чередовать проходы вперёд и назад — это покроет 99% структур, реально встречающихся на практике. Я просто хочу компактификацию саму по себе ещё, поэтому мне наверно будет лучше дополнить её сортировкой по фазовым номерам, чем реализовывать свип задом наперёд.

Sbtrn. Devil
> А правильно ли использовать тут garbage_threshold от предыдущего прохода, а не который должен получиться по результатам текущего?
По результатам текущего мы понимаем, какие объекты точно отвалились — а на следующем проходе мы их собираем (переклассифицируем как фриспейс, компактификатор потом его вытолкнет наверх).

Мой алгоритм можно описать так: сначала мы вообще всем делаем phase_delay[a]++, а потом "подтягиваем" живые объекты обратно — сначала по обратным ссылкам с предыдущей сборки, до уровня родителя после инкремента, затем идёт подтяжка по прямым ссылкам, включая рут-сет, который работает как если б был объект по адресу ноль.

Я не совсем уверен, на самом деле, что это именно gray_top, а не там +1 к нему, но в целом идея такая — смотрим уровень, до которого успел опуститься самый дальний из серых объектов, если кто-то умудрился утонуть ещё глубже — это уже мусор.

Как минимум, тривиально доказывается такой факт — живые объекты занимают все номера последовательно, у тебя не может быть живой объект с номером Н со ссылкой на Н+2. Соответственно, если в общем распределении  номеров появляется пробел — то всё что глубже этого пробела, это уже прям точно мусор 100% ноу кап.

Имбирная Ведьмочка
> а потом "подтягиваем" живые объекты обратно — сначала по обратным ссылкам с предыдущей сборки, до уровня родителя после инкремента, затем идёт подтяжка по прямым ссылкам,
Вот тут как раз неочевидный момент - будет ли он гарантированно успевать подтягивать их обратно быстрее, чем будет накидываться phase_delay. За 1 проход ведь не гарантируется, что от какого-нибудь корневого узла пройдёт маркировка на всю глубину.
Или, иначе говоря, в исходном варианте алгоритма есть выделенный момент, когда точно понятно, что маркировка закончилась (список серых объектов опустел), и после этого шага - только сборка, а перед ним - только новые раунды маркировки. А тут не очень понятно, как гарантируется, что объект не умрёт раньше положенного времени.

Всё-таки нетривиальная задача, надо над этим подумать потщательнее.

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

Кажется, я привёл алгоритм в рабочую форму, как минимум, он теперь проходит рандомизированный тест: https://godbolt.org/z/ren6oj1z1

Каноническая форма прошедшего алгоритма:

Имбирная Ведьмочка
Кстати, интересно такой алгоритм попробовать модифицировать для SQL-базы, с таблицами наподобие Object { id, pd } и ObjectRefs { object_id_src, object_id_target }. Там честный поэлементный обход графа у глубину как раз очень печален, а если сделать что-нибудь с однократным проходом, может получиться поинтереснее.