xor eax, eax?

Мэтту Годболту яйца зачесались выпустить свой Advent of, но только про компиляторные ну немного анальные, да эквилибристики.

Ровно эта штука, о которой он в первом дне у себя рассказывает, мне попадалась вот здесь. Как оказалось, фокус xor'ить регистр с самим собой - имеет как практичный, так и побочный эффекты:
а) инструкция xor на х86 занимает 2 байта, когда как обычный mov eax, 0 пирует на все 5. Потому что надо ж ещё саму константу операндом хранить. Это практичная часть.
б) во всё том же х86, процессор прекрасно знает, зачем оно такое. И сама инструкция фактически даже не выполняется - просто подкапотное причёсывание с переименованием регистров. Это камню удобнее. А нам - приятнее.

Фанфакт - GCC применяет сию гимнастику, начиная лишь с -О2. А вот Clang не стесняется и тулит безусловно даже на -О0. Технически, шланг это даже за оптимизацию не воспринимает. Высокомерно!

Fast and Space Efficient Trie Searches

Деревья, безусловно, важны. Они из углекислого газа карбон выцепляют, а нам чистый кислород возвращают. Так они ещё и сами по себе красивые.

Но я всё же о тех, которые частный случай ацикличного направленного графа. Как только люди обманом заставили песок думать посредством нанесения наноскопических рун, появилась и нужда в массивах. Статические и динамические, конечно, хороши, но далеко не представляют такого же интереса, как ассоциативные. Когда как статический/динамический массив сопоставляет значения с их порядковым номером (индексом), ассоциативный инкапсулирует порядок и сопоставляет значения не индексу, а произвольному значению из фиксированного множества всех возможных ключей. Так мы, например, можем Хонде сопоставить Цивик, а von - Pavlo.

В общем случае, с этим прекрасно справляются хэшмапы. О которых я, к слову, писал здесь и здесь. А современный SwissMap ещё и показывает, как поиск может утилизировать SSE инструкции. Но не просто так существуют и древовидные структуры данных. Если в сердце хэшмап лежит проблема присвоения ключу его (желательно) уникального номера, то деревья - это скорее про уникальный путь ключа. Они как BlackRock: может, в повседневной разработке особо и незаметны, но неявно присутствуют вообще везде. Файловые системы - это практически всегда деревья. Базы данных - абсолютно RB Tree, как и Epoll в линуксе. Full text search (elastic и ему подобные) - сплошные префиксные деревья. Автокомплит, проверка правописания, IP routing, DNS, LZxx компрессоры - вообще всё на них основано. Даже мне для динамического роутинга в индиге пришлось имплементировать.

Основной принцип у деревьев виртуально прост: стоя у развилки, нам необходимо выбрать, по какому пути дальше идти. Функция выбора и определяет вид. Основных их есть несколько, и о них собственно речь и пойдёт.

Fast and Space Efficient Trie Searches

Решая задачу по физике, gpt-oss:20b допустил ровно ту же ошибку в вычислениях, что и я. Таким образом, эмпирически я пришёл к выводу, что интеллекта у меня с AMD RX9070XT.


Binary tree
Нормализированные данные в принципе вкусные, да и на ощупь приятные. Всегда, сужая общий случай до частного, в процессе у более ограниченного подмножества всплывает всё больше свойств и оголяется структура, из которой могут следовать интересные заключения.

Так и с упорядоченными массивами. Как только оная гарантируется, сложность поиска резко падает с линейной до логарифмической, за счёт возможности применения бинарного поиска вместо линейного. К сожалению, выигрыш в поиске за счёт вставки: теперь, для поддержания гарантии, вставка работает в среднем за линейную сложность. Всё-таки место в массиве само себя не освободит - все элементы правее нужного места должны быть смещены вправо на одну позицию, прямо как в отеле Гильберта. Представьте, какого это: участок на гигабайт переместить на 8 байт правее. Это ж блять чистая комедия.

Однако тривиальность переоценивать - обсёрами чревато. Как, например, в Java 9 лет таилось переполнение при взятии среднего арифметического. Rookie ass mistake. Зато в Go всё изначально в порядке - длина всегда представлена в int, а среднее арифметическое берётся в uint. Лишний бит гарантирует отсутствие переполнения.

А ещё не всегда учитывается субоптимальность обобщённого бинарного поиска по массиву строк. Имея L < key < R (где L, R - строки в массиве), беря их среднее арифметическое (строка в массиве между L и R), нам необязательно её сравнивать полностью с искомым ключом. Потому что ключ заведомо имеет общий префикс с L и R:

int prefix = lcp(L, R);
if (strcmp(key+prefix, mid+prefix) == 0)
  ...

(Где lcp(s1,s2) возвращает длину общего префикса двух строк, а key+prefix аналогичен key[prefix:] в других языках.)

То есть, мы можем опустить сравнение первых lcp(L, R) между искомым и средним арифметическим. А так можно чуть ли не пол строки скрутить. Правда, если строки в массиве всё-таки практически общих префиксов не имеют, то мы лишь расстратимся на лишнюю пару инструкций. Так что вслепую применять всё равно не стоит.

А сейчас - самое интересное. Бинарный поиск по упорядоченному массиву - частный случай бинарного дерева, схлопнутого к одномерному массиву, логично. Но тут сразу вырисовывается неприятное заключение: если на нашем множестве ключей такая оптимизация с отсеканием префикса из сравнения действительно работает, то это означает лишь то, что мы тратим пространство неэффективно. Если столько байт пропускаются, то хули они там вообще забыли?

Fast and Space Efficient Trie Searches

"Сопротивление бесполезно!" Крикнули 40000 вольт. А теперь представьте, какие были остальные варианты вступления, если в конце я выбрал именно этот.


Radix trie, оно же префиксное дерево
Арность (несмешно) - в общем случае описывает количество аргументов либо операндов, принимаемых функцией или оператором. (Технически, ранг матрицы тоже сюда косвенно относится, да.)

В случае деревьев, арность сообщает число исходящих рёбер из узла (не забываем, что узел есть дерево, дерево есть узел; играет роль только тот узел, который мы прямо сейчас воспринимаем за корень). В случае бинарных, логично, это фиксировано два исходящих ребра. Тернарных - три. Можно произвольно много тоже, такое называется variable-arity, или же просто variadic (откуда оно и пошло в С). Но смысл здесь - с арностью можно весело играться. Например, взять дерево с арностью, равной размеру алфавита - и вот мы уже можем искать следующий узел, чей порядковый номер соответствует оному искомой литеры в алфавите. Такое дерево называется m-way trie.

Рассмотрим примитивный пример с деревом, определённом для английского алфавита в нижнем регистре:

struct Trie{
  char c;
  struct Trie* children[26];
}

bool search(struct Trie* trie, char* str) {
  for (; *str; str++)
    if ((trie = trie->children[*str-'a']) == NULL)
      return false;
  return trie->children[0] != NULL;
}

Поиск здесь отвечает лишь за существование строки в дереве и останавливается, либо когда у текущего узла нет наследников, соответствующих нужной букве в строке (вербозный иф), либо когда строка кончается (тогда у узла должен быть non-NULL наследник для 0, он же стандартный терминатор С-строки, он же в роли флага term). Чтобы ассоциировать значения, достаточно просто добавить атрибут с нужным типом, и возвращать его значение у терминальных узлов. Для обобщения поиска, дабы возвращать произвольное ассоциированное значение со строкой, а не просто проверять её вхождение - достаточно лишь добавить соответствующий атрибут к структуре, и возвращать в конце поиска именно его.

Вставка тривиальна: мы траверсим дерево до тех пор, пока в строке не встретится символ, для которого пути дальше уже нет, т.е. точку строки, в которой она отличается от всех остальных вхождений.

Но тут я бы остановился и сделал передышку. При такой вставке, я неявно предполагаю аллоцировать отдельно каждый отдельный узел. Если дерево динамическое (после построения ключи в него могут добавляться или удаляться), тогда такая вставка может быть крайне неприятной по производительности, особенно если нужно вставлять много новых символов. Тут сразу интуитивно приходит мысль аллоцировать сразу по 128-1024 узлов за раз, и потом их постепенно оттуда брать для вставки, коль уж дорог сам факт выделения памяти, а не её количество. Сразу развивая идею, приходим к тому, что дерево в принципе можно целиком всунуть в один большой массив. Всё, что изменится - это вместо struct Trie* у нас будет uint index, хранящий индекс на следующий узел в массиве. int/uint в С занимают фиксировано 32 бита что на х32, что на х64 архитектуре - а это значит, что с исчерпывающим потолком в 4.2млрд узлов в дереве, мы выигрываем лишние 4 байта. Размер структуры на х64 архитектуре, конечно, от этого не уменьшится, потому что выравнивание - но в них взамен можно хранить дополнительную информацию, которая в противном случае занимала бы дополнительное машинное слово. А для деревьев с бОльшим количеством ветвей, даже такая мелочь уже может срезать очень много потребления памяти.

Ещё из плюсов деревьев в массивах - узлы лежат в ОЗУ последовательно, благодаря чему они лучше умещаются в кэшлинии. Вот только, имея узел, в котором массив из 26 чисел - даже один такой в кэшлинию едва ли влезет. И тогда стоит задуматься о том, как хранить именно этот массив более эффективно, а не о том, как выиграть лишних 4-8 байт.

Имеем: статический массив, частично состоящий из нулей. Как потом окажется, очень многие будут состоять преимущественно из нулей. Это точно можно как-то соптимизировать.

Fast and Space Efficient Trie Searches

Конечно можем. Всё-таки и 2+2=5, если взять достаточно большой 2.


Radix trie, оно же префиксное дерево II
Спойлер - radix trie это compressed m-way trie.

Спойлер 2 - этот принцип прекрасно применим к вообще всем остальным описанным деревьям. Помимо, наверное, АСТ. Radix trie - это скорее обобщённый термин для сжатых деревьев в принципе.

Давайте предположим, у нас строки формируют нормальное распределение. Это хороший кейс, потому что в множестве ключей довольно много общих префиксов, следовательно - больше потенциальной экономии. А дополнительная сладость здесь - если строки в субдеревьях чаще имеют длинный общий префикс (от 4 символов), то мы можем сразу по нескольку символов за раз и сверять, что сильно уменьшает глубину. То есть - заменить char c на char* c. Это и меньше обращений к памяти, и меньше ветвлений, и АЛУ больше работы производят - больше байт за такт перелопачивается. Получится что-то вроде:

struct Radix{
  bool  term;
  char  clen;
  char* prefix;
  struct Radix* c[];
}

bool search(struct Radix* node, char* str) {
  loop: while (*str) {
    for (int i = 0; i < node->clen; i++)
      if (int p = lcp(str, node->c[i]->prefix)) {
        node = node->c[i];
        str = str[p:];
        continue loop;
      }
      return false;
    }
    // str isn't in the trie if the last-visited 
    // node isn't terminal.
    return node->term;
}

(Где lcp(s1,s2) - это старая-добрая длина общего префикса двух строк).

Кстати, то самое моё дерево для динамического роутинга в индиге примерно так же и устроено.

Поиск стал ещё обскурнее, но суть осталась прежней: спускаемся по дереву, откусывая общий префикс и беря субдерево из наследников (каждый наследник является самодостаточным корневым узлом для своего дерева). Но самое классное, что нам больше необязательно держать NULL'ы в children, теперь у нас есть просто динамический массив с линейным поиском по оному. Что, конечно, бьёт для "широких" деревьев, когда в массиве будут все 256 элементов (каждая строка начинается с уникального байта). Но если есть возможность держать массив упорядоченным, то мы обратно возвращаемся к бинарному поиску. Словно змея, поедающая саму себя.

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

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

Ternary Search Tree (TST)
Предикат в тернарном дереве, отвечающий за то, в какую сторону дальше идти, определён как "больше/равно/меньше" (в противовес просто "больше/равно" у бинарного). По аналогии с strcmp(s1,s2) в С, которая возвращает не логический двоичный флаг, а тернарный - {-1, 0, 1} для s1<s2, s1==s2, s1>s2 соответственно.

Весь фокус здесь - это взять наш исходный struct Trie, но заменить children на такое тернарное дерево. Пустые вхождения в children - это, следовательно, несуществующие пути в дереве - а, значит, и память на них расходоваться не будет. В этом случае тернарное дерево показывает себя идеально, потому что может составлять равенства символов - в дополнение к бинарному, которое предоставляет только неравенства. С бинарным пришлось бы заниматься не самой приятной разновидностью акробатики.

Fast and Space Efficient Trie Searches

Концепт префиксных деревьев впервые был описан в 1959м году, а назван в 1960м - retrieval, из information retrieval systems. Они считаются одними из самых распространённых структур данных, потому любое улучшение в производительности или пространстве крайне интересует индустрию. Масштабы, как никак.

Возьмём тот же автокомплит слов в английском языке. Это примерно 150,000 уникальных слов, и при алфавите в 26 символов, согласуясь с законом больших чисел, каждое слово прокладывает уникальную путь в дереве уже в среднем после ⌈log₂₆150000⌉ = 4 символов. То есть, узлы уже на четвёртом уровне в дереве часто будут иметь по всего 1-2 исходящих узла. Что и прекрасно видно на таблице с распределением количества деревьев к количеству узлов в них (заметьте, как стремительно падает их число!). Таким образом, брать префиксы не вариант, их относительно мало.

Однако! Автокомплит использует абсолютно статичное дерево. Новые слова всё-таки редко добавляются. Значит, можем плевать на стоимость вставки - в таких объёмах, гораздо важнее смотреть на занимаемое пространство. Довольно эффективно его использует как раз ACT.

Fast and Space Efficient Trie Searches

У людей в среднем менее двух ног.


Array Compacted Tree (ACT)
Для освежения памяти: Look-Up Table (LUT) - это обычный статический массив, но с его элементами в таком порядке, чтобы их значение ассоциировалось с конкретным индексом. То есть, чтобы вело себя, как хэшмапа. ASCII символы, например, это самые обычные числа 0..255, которыми массив на 256 вхождений спокойно индексируется, и даже без bound checks. Да и места обычно тоже не сильно много занимает. Похожим образом я у себя в indigo hex-значения декодирую: в таблице из 256 восьмибитных чисел для ASCII-символов 0-9, a-f и A-F лежат соответствующие заранее рассчитанные значения. На валидацию я, естественно, хуй клал. А ещё с ними можно очень хорошо оптимизировать декомпрессор кода Хаффмана, что для HTTP/2 и 3 очень даже полезно.

Ближе к делу. ACT - это просто все субдеревья (узлы) размазали на плоские LUT, и сплавили вместе так, чтобы на пустующих местах одного LUT были размещены узлы другого. Так и называются - overlaid tries, потому что налазят друг на друга. Различают они их по тэгу Parent, чтобы понимать, чьему субдереву этот узел приходится. Если Parent совпадает - отлично, такой вариант развития событий в дереве заложен. Тогда мы берём от него XBase - корневой узел следующего интересующего нас субдерева, и индексируем наш следующий LUT, но уже относительно этого XBase. Вы ничего не поняли, но не переживайте, сейчас я попробую всё подробнее разъяснить.

Дадим же наконец определение:

struct ACTNode{
  int XBase;
  int Parent;
}

typedef ACTNode ACT[N]; // N is to be specified

bool search(ACT trie, char* str) {
  for (int base = trie[0].XBase; *str; str++) {
    struct ACTNode node = trie[base + (*str-'a')];
    if (node.Parent != base)
      return false;
    base = node.XBase;
  }
  return base == NULL;
}

Атрибуты структуры именованы в соответствии с таблицей. Столбец Letter там добавлен для удобства, а Node это просто индекс узла в массиве.

Fast and Space Efficient Trie Searches

Разберём поиск построчно:
1. Нулевой элемент - это абсолютный корень. Из него мы берём наш первичный XBase.
2. Получаем численное значение буквы, эксплуатируя факт, что в ASCII алфавит идёт по порядку. Прибавляя его к имеющемуся XBase, получаем индекс нужного нам следующего узла.
3. Если Parent у полученного узла не совпадает с нашим base, относительно которого мы искали - значит, этот узел принадлежит другому субдереву. Следовательно, это место пустовало - наша строка не входит в дерево. В противном же случае - берём XBase этого узла как наш новый "якорь".
4. Повторяем цикл до тех пор, пока строка не кончится. Когда строка кончилась - у последнего выбранного узла XBase обязан быть NULL, что указывает на то, что такой узел - терминальный.

Рассмотрим на конкретном примере ср строками BEAR и BEG.
1. Первая буква в BEAR - B, первая буква по порядку (счёт идёт с нуля). Начинаем с нулевого узла. Его XBase - 1. Складываем 1+1=2. Узел под номером 2 действительно соответствует букве B. Его Parent=0, что соответствует нашему XBase=1. Пока всё правильно.
2. У узла под номером два XBase=4. Вторая буква в слове - E - четвёртая по порядку. Складываем, получаем узел под номером 8. Его Parent=2, значит, тут тоже всё правильно.
3. Новый XBase=9, "А" нулевая буква по счёту. У 9го узла Parent=8, правильно.
4. 9й узел даёт нам XBase=1. R - 17ая по счёту, складываем и оказываеся на узле 18. Parent=9, всё совпадает. Слово кончилось, смотрим - у 19го узла XBase=NULL, значит, строка полностью входит в дерево. Возвращаем истину.

С BEG мы повторяем первые два шага. Но теперь, мы складываем G (шестая буква по счёту) с XBase=9. У 15го узла вообще нет Parent, что явно не совпадает с Parent=8. Следовательно, такой строки в дереве нет.

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

Но такое дерево очень экономно в расчёте на размер узла: int в С всегда занимает 32 бита, и потому структура в моём примере будет весить восемь байт, что на 64-битной архитектуре - одно машинное слово. Правда, присутствует крайне весомый минус: моё дерево не умеет одновременно хранить две строки, где одна целиком является префиксом другой. То есть, узел не может хранить одновременно и EOL, и продолжение. Это можно решить либо однобитным флагом Term, либо, если всё-таки дерево сопоставляет строкам произвольные значения, выбрать из множества наш местный NULL (или одолжить у множества один бит). Но вне зависимости от выбора, выравнивание докинет ещё одно машинное слово, а это уже суммарно 16 байт (или 3 машинных слова = 12 байт на 32х битной архитектуре). Что, в прочем, всё ещё весьма экономно. Да и для ускорения вставки можно добавить дополнительных пару полей. Ну, или всё-таки уговорить компилятор не выравнивать, хотя я бы тогда уже использовал новое пространство с честью.

Fast and Space Efficient Trie Searches

Эмпирическим путём доказано, что практика отличается от теории.


Array Mapped Tree (AMT)
Вернёмся к нашему самому первому, неоптимальному дереву. Мы (в общем случае) не можем свести стоимость пустых вхождений к нулю. Но можем свести к одному биту.

Идея проста и стара (описана в 1977), как мир: каждому символу сопоставляется один бит. Бит отвечает за то, что путь валидный и существует. То есть, если соответствующий бит включён - то ветвь с таким символом существует и находится в children. А поскольку наш массив - плотный (вмещает только non-NULL указатели), то для получения нужного индекса считаем, сколько битов включено перед ним:

struct AMT{
  uint term:1;
  uint bitmap:26;
  struct AMT* c[];
}

bool search(struct AMT* node, char* str) {
  for (; *str; str++) {
    uint b = 1 << (*str-'a');
    if ((node->bitmap & b) == 0)
      return false;
    uint next = __builtin_popcount(node->bitmap & (b-1));
    node = node->c[next];
  }
  return node->term;
}

(uint term:1 говорит компилятору, что использоваться будет только 1 бит - и тогда он сам подставит нужные битшифты/маски, и даже грамотнее структуру упаковать сможет - не придётся руками возиться. b-1 в popcount делается вот зачем.)

Разберём все действия при поиске:
1. Смотрим, есть ли такая буква в c: сдвигаем 1 на порядковый номер буквы и проверяем, что такой бит в битмаске включён.
2. Чтобы получить индекс нужного нам узла в массиве, считаем, сколько узлов в массиве предшествуют ему. То есть - считаем, сколько единиц в битмаске включено ДО нашего узла.
3. Когда строка кончилась, возвращаем флаг term у последнего узла.

Заметьте: атрибуты term и bitmap, скорее всего, будут храниться в одном uint32, а variable-length поле c представляет из себя обычный указатель. Длину массива хранить нам тоже не надо, ведь она уже заключена в количестве единиц в bitmap целиком. Итого - вся структура с выравниванием весит два машинных слова (вне зависимости от архитектуры), что пока что сопоставимо с ACT. Но отличительная черта - для вставки не нужно решать вычислительно-трудную проблему, а при сжатии дерево идеально занимает всё пространство в массиве без пропусков.

К сожалению, аргумент перестаёт работать с увеличением кардинальности алфавита. Чем больше символов мы учитываем - тем больше бит необходимо хранить. В ACT же кардинальность нигде не хранится, и, следовательно, оно агностично к мощности. Для полного алфавита в 256 символов таблица ACT никак не поменяется, когда как каждый узел AMT будет содержать 32 байта только битмап. Суммарно - 40-48 байт на узел, и это без наследников. Напоминаю, что ACT даже не экономя не вылазит за пределы 16 байт. Старая-добрая дилемма: либо быстро, либо компактно.

Fast and Space Efficient Trie Searches

Домашние животные мне строго противопоказаны. Как-то раз у меня жил ручной камень. Он умер.


Unary Search Tree (UST)
Деревья тем прекрасны, что для решения одной проблемы дерева, мы используем другое дерево.

Имея, что AMT сильно страдает от увеличения кардинальности алфавита, мы можем обменять быстрое нахождение ветви через popcount на старый добрый бинарный поиск. Тогда нам больше не нужна битмапа, заместо неё остаётся только uint8 clen. Вот мы и получаем:

struct UST{
  int term:1;
  int symb:8;
  int clen:8;
  struct UST* c[];
}

bool search(struct UST* node, char* s) {
  for (; *s; s++)
    if (!(node = binsearch(node->c, node->clen, *s)))
      return false;
  return node->term;
}

(Где symb - символ, который ведёт к узлу.)

Мои поздравления - мы совершили кругосветное путешествие и вернулись к старому доброму бинарному поиску! Поиск узла, конечно, больше не O(1) (принимая сложность popcount за константу; кстати благодаря SSE - до него это было либо медленно, либо вообще отсутствовало), но O(log m) (m - кардинальность алфавита). Но это всё ещё максимум 8 сравнений в худшем случае, для узла со всеми 256 ветвями. А вот из преимуществ - узел UST влазит в одно 64-разрядное машинное слово, если уместить его в массив (4 байта индекс ветви + 1 байт длина массива + 1 байт символ узла + 1 байт (выровненный) терминальный флаг = 7 байт). Узел, весом с указатель - это абсолютный рекорд. Абсолютно компактно, совершенно не быстро.

Унарным оно, кстати, и называется потому, что структура номинально содержит лишь один-единственный указатель.


В заключение.
С деревьями можно играться нескончаемо. В эквиваленте 13 страниц А4 я лишь вкратце рассказал про основополагающие вариации, и только лишь для сопоставления строк - словно капля в море. В работе, на которую я опирался, префиксные деревья как compressed m-way trie упоминаются очень вскользь, и то только в конце, хотя компактность представляет центральный интерес бумаги. Потому и желаю вам вырабатывать должную интуицию и не полагаться на заучивание. Человека умнее делает не слово, а контекст.



—
Большая часть материала и целых два скрина были взяты из [Bagwell 2000] (на что заголовок, собственно, и отсылает). Сам документ я оставил в комментариях.

Прочие вкусные разновидности деревьев

Я не договорил.


Judy array
Как я и говорил, если дерево не устраивает - его нужно привить с другим, чтобы устроило. Селекция, ёпта. А Judy array - это как раз буквально такая ядерная смесь:
— Обычное 256-арное дерево (покрывает все значения одного байта).
— Префиксное (сжатое) 256-арное дерево - когда путь состоит из нескольких узлов подряд с единственным наследником. Я бы здесь вставил картинку, но мы в телеграмме, а поэтому могу визуализировать только так: дерево {"Х"} -> {"У"} -> {"Й"} скукоживается до кондиции {"ХУЙ"}.
— AMT - когда префиксов особо нет (тогда хранить строку на порядок дороже, чем просто символ), но и наследников тоже немного. Dense array - массив из только non-NULL узлов, рядом всегда битмапа, всё как я и рассказывал ранее. Кстати, можно сказать, что это не столько самостоятельный концепт, сколько оптимизация для sparse arrays.

Тип узла помечается соответствующим енумом. Из интересного - Judy array скорее вполне конкретная реализация, потому что там ещё думают про кэшлинии, чтобы всё красивенько лежало. Штука, правда, очень ситуативная, да и заточена под чтение, а не вставку, и потому андерграунд.

Hash Array Mapped Trie (HAMT)
Абсолютно тот же AMT, только вместо строк хранятся их хэши. Это круто, потому что хэш всегда одинаковой длины, а значит, и глубина дерева - константная. Тогда и ресайз довольно дешёвый, растёт-то только в ширину - просто побольше слотов массиву докинуть надо.

Идея не поменялась: имея n-арное дерево, берём от числа-ключа log(n) нижних бит и индексируем ими следующую ветвь. Например, обычно берут n=32, и теперь мы храним по 5 бит хэша в каждом узле. Меняем char sym на char bits:5. Ну и битмапа 32-битная, соответственно. Поиск будет выглядеть примерно так:

struct HAMT{
  char bits:5;
  uint32 bitmap;
  struct HAMT* c[];
}

bool search(struct HAMT* node, char* s) {
  return search_(node, strhash(s));
}

bool search_(struct HAMT* node, uint64 hash) {
  for (int i = 0; i < 13; i++) {
    uint32 b = 1 << (hash & 0b11111);
    if (node->bitmap & mask == 0)
      return false;
    uint preceding = node->bitmap & (mask-1);
    uint next = __builtin_popcount(preceding);
    node = node->c[next];
    hash >>= 5;
  }
  // if reached, the hash is in the trie.
  return true;
}

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

И даже терминальный флаг не нужен! Глубина-то константная, с n=32 любой узел на ⌈64 / log32⌉ = 13 уровне будет сам по себе терминальным. И поэтому, если мы не успели сделать возврат в цикле, то после него мы точно знаем, что в node у нас лежит терминальный. Если бы мы добавили что-нибудь полезное туда, тогда после цикла было бы просто return node->value;

И сейчас я ещё до кое-чего допёр: если в структуре будет ещё лежать какое-нибудь значение (чтобы search был полезным), тогда в терминальном узле нам не нужен массив наследников. Можно сделать а-ля:

union{
  struct HAMT* c[];
  SomeType   value;
} 

А если ещё и значение тоже размером с указатель, тогда фактически вообще бесплатно храним! Ну не прелесть ли?

Кстати, применимо вообще ко всем деревьям. Сумтип - сила.

Но главная прелесть - число итераций константно, компилятор даже может развернуть цикл. Так ещё и по скорости сопоставимо с хэшмапами, при том используя память гораздо более экономно (не надо держать кучу лишних слотов). Даже Clojure и Scala его используют для своих дефолтных мап. Правда, персистентную версию - т.е. просто иммутабельную, при вставке возвращается целое новое дерево. Даже есть Ctrie - thread-safe lock-free вариация HAMT. Звучит круто, правда? А это по факту круто. Вот прям очень. Когда-нибудь и я углублюсь в такое.

В общем, это пока самое практичное дерево среди всех ранее перечисленных.

Compressing AMT in XZB style

XZ бэкдор нашумел. Не только потому что нагло, а ещё и потому, что технически интересно. Пускай в конце концов всё равно обосрались из-за непонимания фундамента. Я его тоже не понимаю, кстати.

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

Бэкдор загрузился раньше других, и теперь ему нужно ждать, когда линкер подыщет всю вкусноту. Бэкдор для этого добавляет хук, который вызывается для каждого нового символа, и ему нужно понять, нужный ли это символ (например, функция загрузки RSA ключа). Проблема: условная строка [email protected] в бинаре появиться не должна. Это было бы банально слишком подозрительно. Решение? Построить дерево.

С деревом строки больше нигде явно не встречаются. Тех строк вообще номинально нет, дерево служит эдакой таинственной коробочкой "Это нужная строка? Да/Нет". Мои примеры с поиском, возвращающим true/false - не такие уж и бесполезные, как оказалось.

Места не так уж и много, поэтому китаец взял наш любимый array mapped trie. (Про китайца я, правда, выражаю сомнения. Легко на них всё сбросить.) Только там вместо того, чтобы хранить все узлы полностью в одном массиве, вынесли битмапы в отдельный, второй массив. Всё для того, чтобы можно было там хранить только уникальные битмапы (а узлы на них, соответственно, ссылаются). Такое дерево может спокойно похудеть на 20-30%. Правда, я не уверен, сработает ли такое на бОльших масштабах (при сохранении арности): всё-таки фокус такой LZ-style компрессии в том, что индекс на битмапу меньше размера самой битмапы.


Если интересно почитать более общий обзор, то прекрасная статья здесь. Ещё неплохой материал у herm1t с канала @ruheight конкретно про дерево и почему китаец начал хорошо, а кончил... Ну, как кончил, в общем.

Один из приколов в XZ-бэкдоре я пропустил. Бэкдором можно управлять, послав ему зашифрованную и подписанную цифровой подписью команду. И она зашита в модуль N RSA-ключа (они передаются как ASN.1 или PEM). Сперва я подумал, что ключ используется просто как контейнер, но на самом деле можно сгенерировать работающую ключевую пару с вшитым значением. Есть и статья Ленстры о том, как готовить такие ключи ("Generating RSA Moduli with a Predetermined Portion"), и работающий код от Райана Кастеллучи. Небольшой пример, как вшить константу:

from sympy import randprime, nextprime, isprime
import os, math

x = b"\x80\x00\x00\x00\x00\x00\x00\x01"
j = 0
while True:
  j += 1
  p = randprime(0, (1 << 256))
  l = int.from_bytes(x + os.urandom(56), "big")
  q = l // p # nextprime(l // p);
  if isprime(q):
    break
n = q * p;
print(str(l.bit_length()) + ":" + hex(l >> 256) + "...")
print(str(n.bit_length()) + ":" + hex(n >> 256) + "...")
print(str(p.bit_length()) + ":" + hex(p))
print(str(q.bit_length()) + ":" + hex(q))
# check key, textbook RSA
f = (p - 1) * (q - 1)
e = 65537
d = pow(e, -1, f)
m = 0xDEADBEEFCAFEBABE
c = pow(m, e, n)
t = pow(c, d, n)

#находки