Чайник из Юты

futex2, Wine и WaitForMultipleObjects()

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

Я упоминал WaitForMultipleObjects() в NT. Естественно, с фьютексом, который абсолютный примитив, его семантику повторить не так просто. Что, в целом, не то, чтобы кого-то ебало в программировании под Линукс. Но ебало контрибьюторов Wine, потому что без нормального способа эмулировать поведение перф местами был в жопе.

Поэтому в Линуксе с 5.14 по 5.16 зашелестел ветер перемен. Изначально был гигантский пропозал с кучей нововведений, включая variable-sized futex word. Но решили сделать проще и адаптировать ключевые моменты под существующее ABI. А что не смогли, то в отдельные семейства сисколлов унесли. Правда, шрамы древних споведаний всё равно остались:

FUTEX2_SIZE_U8
FUTEX2_SIZE_U16
FUTEX2_SIZE_U64
These are defined, but not supported (EINVAL).

По итогу, futex2 так и остался наречием, эгидой. Но под этой эгидой добавили FUTEX_WAIT_PI2, который от обычного (не 2) отличался только лишним аргументом - теперь таймер явно указывается. До этого правда делалось то же самое, методом включения битфлага в случае, если реалтайм захотелось. Честно говоря, и сам не ведаю, на кой хуй они это сделали.

Однако!

Винишко своё таки пролоббировало, и в конце концов добавили один, но самый важный сисколл - futex_waitv. Теперь можно спать не на одном фьютексе, а сразу на куче аж до 128 штук. Воистину перемога!

Собственно, именно об этом и кричали в 2021 "ЛИНУКС ГЕЙ МИНГ ПОДНИМАЕТСЯ С КОЛЕН!!"


А, и помните ещё, я говорил, что чтобы поток заснул, нужно, чтобы val в сисколле соответствовал тому, что стоит за *uaddr? Если кому-то не похуй, то вот зачем:

If the futex value does not match val, then the call fails immediately with the error EAGAIN.

The purpose of the comparison with the expected value is to prevent lost wake-ups. If another thread changed the value of the futex word after the calling thread decided to block based on the prior value, and if the other thread executed a FUTEX_WAKE operation (or similar wake-up) after the value change and before this FUTEX_WAIT operation, then the calling thread will observe the value change and will not start to sleep.

Поэтому вокруг фьютекса всегда надо ставить гарды от EAGAIN. В сниппете с мьютексом эту роль на себя взял do..while.

В общем, Go выполняет роль местного Хаскелла, только в целом хуже. Если Хаскелл - это прикладной лямбда-калькулюс, то Go - это прикладной CSP, но с минусом в виде дорогих каналов. Основополагающих блять!!

Короче, не нравится он мне.

How-To: mutex в юзерспейсе, часть II

Как вы заметили, я люблю попиздеть. И ещё реже по делу, как то диктуют святые мужские традиции.

Futex и WaitOnAddress - это просто удобный механизм уходить в ожидание. Именно поэтому просто навесить какой-нибудь CAS на существующий мьютекс было идеей ниже среднего - удачи придумать, как нормально спать с примитивами, на то не рассчитанными.

The futex() system call provides a method for waiting until a certain condition becomes true. It is typically used as a blocking construct in the context of shared-memory synchronization. When using futexes, the majority of the synchronization operations are performed in user space. A user-space program employs the futex() system call only when it is likely that the program has to block for a longer time until the condition becomes true. Other futex() operations can be used to wake any processes or threads waiting for a particular condition.

То есть вызываешь FUTEX_WAIT, говоришь "за этим поинтером лежит 0хА". Если там 0хА, то поток уходит в сон. Просыпается, когда кто-то другой вызывает FUTEX_WAKE. В котором, кстати, ещё можно указывать, сколько спящих будить.

Сам мьютекс делается примерно так:

/* Simplified pthread mutex */

// 0 = unlocked,
// 1 = locked,
// 2 = locked with waiters
int mutex_word = 0;

void pthread_mutex_lock(int *mutex_word)
{
    // Fast path: try to take the lock with an atomic CAS
    if (atomic_cmpxchg(mutex_word, 0, 1) == 0)
        return; // got it, no kernel call

    // Slow path: there's contention, call into the kernel
    do {
        // Mark that there are waiters
        atomic_set(mutex_word, 2);
        // Sleep until value != 2
        futex(mutex_word, FUTEX_WAIT, 2, NULL, NULL, 0);
    } while (atomic_cmpxchg(mutex_word, 0, 2) != 0);
}

void pthread_mutex_unlock(int *mutex_word)
{
    // Fast path: no waiters
    if (atomic_xchg(mutex_word, 0) == 1)
        return; // just clear, no kernel call

    // Slow path: there are waiters, wake one
    futex(mutex_word, FUTEX_WAKE, 1, NULL, NULL, 0);
}

В лучшем случае - мы просто дрочим mutex_word из 0 в 1, и наоборот. Потому что locking is only expensive when there's contention (это цитата а не выебон). Когда возвращаем, смотрим, не нужно ли оно кому, если нужно - будим его.

Кстати фанфакт: у фьютексов ещё есть режим с приоритетами. Если поток с высоким приоритетом спит, пока локом владеет поток с низким приоритетом, то последнему на время приоритет повышается. Чтобы съебал побыстрее.

Фокус в том, что вообще все мьютексы устроены буквально идентично. Даже в Go, хотя там они не удержались и всё-таки наебнули CAS дважды. В NetBSD, FreeBSD и Dragonfly тоже есть futex, в Винде эквивалентный WaitOnAddress - редкий момент унификации. Даже я переизобрёл свой мьютекс, когда нужно было по-честному мультиплексировать записи в сокет. Прям буквально 1 в 1.

Ну, а на правах инжирнера, существование одного фундаментального примитива приносит мне просто эстетическое удовольствие. The less the kernel knows, the better. А это уже выебон.

Но про Go я бы поговорил поподробнее. У них мьютекс интересный такой: есть starvation mode, когда кто-то дольше миллисекунды не может забрать себе лок, тогда владение мьютексом напрямую переходит к этому бедняжке. Правда, пока эта миллисекунда не прошла, происходит что-то очень близкое к busy loop. Просто потому, что запарковать горутину очень, очень дорого, а локи обычно долго не живут.

А ещё, сам sync.Mutex состоит из state int32 и sema uint32. Они двое разделяют семантику mutex_word из сниппета - state для атомарного счётчика, sema как уникальный идентификатор для рантайма. Ну, точнее, его адрес, в самом sema обычно лежит просто 0. В рантайме есть своя субсистема семафор, которая как раз и использует фьютексы и WaitOnAddress, когда можно (а когда нельзя, то фоллбэк к обычным семафорам по сисколлам). Этот sema и используется, как "якорь", на котором futex будет засыпать.

How-To: mutex в юзерспейсе, часть I

Кто не любит блокировать мьютексы? Поднимите руки. Я их пожму.

Начнём с истории. История - это не только интересно, но ещё и важно. Потому что я так сказал.


В Линуксе и в Винде до 2000х примитивы (и не очень) синхронизации были впаяны в ядро. Общаться с ними приходилось сисколлами, а это дороговато. Самое обидное, когда за ресурсом редко конкурентно обращаются (а это частый кейс), и ты перфомансом за воздух платишь. В какой-то момент это преодолело критический порог, таки постоянно контексты дрочить и планировщику по хуйне мозги ебать - экспириенс ниже среднего. Тогда-то к 2003-му в Линукс и завезли futex, в честь fast userspace mutex.

Была такая ОС, Solaris называлась, Sun её породили. Поскольку ребята ещё с 80х вкладывались в многоядерные и многопроцессорные машины, к концепту futex'а они пришли ещё в 1990х. Всё-таки приятнее, когда синхронизация съедает чуть меньше, чем всё. Сам концепт прост как три пизды - атомарный флаг "занято", если нет - выставляем, а сами пользуемся. К ядру с унылым еблом идём, только когда гонка проиграна и флаг оказался выставлен до нас. Собственно, это и есть наш happy-path в uncontended locks.

BSD делала примерно так же в то время, потому что на ней тогда ещё часто крутились базы данных и вебсервера. Ну, а ещё её трогали университеты. Чего ещё ожидать от грязных лап ак*демиков.

Линукс, как и Винда, в те времена целились на потребительский же сегмент, а там редко возникала проблема многоядерности. Поэтому они и явились столь поздно на сей праздник перфоманса.

Только вот у Windows NT был обширный (реально сука обширный!) арсенал объектов синхронизации (такое примитивом называть - что Христа предать), который представлял из себя ядерные объекты. Ну, то есть, в Линуксе это просто int value, а в Винде прям полноценные объекты, с кучей дополнительного контента. Главный фокус - ты можешь кинуть сразу несколько объектов в WaitForMultipleObjects(), и ядро переварит их. Это буквально как select в Go, можно сразу из нескольких источников ждать. Только если Go ограничивается каналами, то в винде это могли быть пайпы, файлы, ивенты, таймеры, потоки, процессы - что угодно. Яж говорил, арсенал солидный.

Только в Windows 8 микрософты допёрли, что люд просит легковесных примитивов. Тогда-то и появился WaitOnAddress, который абсолютно тот же futex. Теперь у нас два мьютекса ебать. Один старый-добрый со всем багажом контента, а второй лёгкий на WaitOnAddress.

Почему рандомный шум несжимаемый?

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

Возьмём все битстроки какой-нибудь длины n, да. Если это рандомный шум, то распределение униформное - вероятность встретить любую из строк 1/2^n. А компрессия это что?

Блять, вопрос вообще-то хороший. Если зайти интуицией, то вот можно представить, что строка несёт какую-то информацию. Допустим, строку можно удлинить (как тот url longener), и при этом не потерять в информативности. Размазать информацию, короче. Но тогда логично предположить, что можно пойти и в обратную сторону? Тогда для одной и той же информации можно представить целый бесконечный спектр всех строк, которыми она может быть представлена. Хотя скорее это даже луч, как нам на математике в 3 классе рассказывали, потому что у этого спектра явно есть начало. Если пустая строка и может быть дохуя информативной, то вот с отрицательной длиной как-то лыжи уже не едут.

Собственно, компрессия и есть - переместиться ближе к началу луча. Желательно.

Нижний предел длины, или же начало луча, можно оценить по среднему количеству информации в строке - оно же 2^n - оно же энтропия строки, как однажды сказал мой кумир Шеннон.

Возвращаясь к нашим строчечкам, как и было сказано - вероятность каждой составляет 1/2^n, это и есть наша энтропия. Значит, каждая битстрока длины n несёт в себе ровно столько информации, сколько в ней собственно бит. Если взять какую-нибудь одну рандомную из них и попытаться урезать ей один битик, тогда вдруг окажется, что эта урезанная строка является префиксом для второй битстроки. Это не очень приятно, особенно если мы захотим потом передавать эту информацию. Ну а как понять-то ёпта, ты получил полную n-1 строку, или нам всё-таки хотели следующим битом донести другую истину? Короче однозначность декодирования пропадает. Опыт ниже среднего.

Хорошо, от неоднозначности можно избавиться. Из всех битстрок можно построить одно большое бинарное дерево, которое сможет однозначно их определять. Напоминаю, у n-1 и n битстрок будет общий последний бит, поэтому чтобы в дереве не проебать n строку, нам придётся перейти на соседний узел от n-1 строки. Но он и так уже определяет третью битстроку. Но! Не стена, подвинется. Из терминального тот соседний узел магическим образом превращается в обычный и теперь ведёт к двум новым узлам: один для n строки, второй для той самой неудачливой третьей битстроки, которая там изначально сидела (жертва обстоятельств!). Эти два новых узла, выходит, лежат уже на n+1 глубине, а значит - теперь они кодируются n+1 битами.

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



Ремарка: сложность Колмогорова* здесь роли не играет - общая тенденция 2m новых бит для m убранных. ВСЕГДА. Даже если взять строку, состояющую полностью из нулей и сократить её до одного нуля, мы всё равно получим 2(n-m) бит оверхеда.

Сложность Колмогорова* - длина наименьшей программы (обычно машины Тьюринга), способной описать некую строку. В целом, она и классическая энтропия - две стороны одной монеты. Только эта более прикладная в контексте компрессоров.

А ещё лучше посмотрите 3b1b.

Channel name was changed to «Чайник из Юты»

А вот с деревьями уже поинтереснее. С eml мы имеем обычное бинарное, то есть должно быть проще и быстрее находить оптимальное - в теории. Ну, а ещё символьная регрессия часто работает на уменьшенном наборе операторов, рискуя тем, что их не хватит для описания датасета. Зато арность поменьше. С eml, который бинарный, так ещё и де-юре универсальный, такой проблемы якобы нет. Я правда так до конца и не разобрался, какой из двух аргументов весомее - всё-таки на практике не сильно-то и меньше то дерево выходит. Требуется 19 узлов, чтобы выразить x+y. Для числа -2/3 нужны все 45 узлов. На синус там вообще сотни пойдут, почти так же, как и на π. log2(n) для 45 узлов - дерево глубиною минимум в 6 узлов, а это только базовая арифметика. Так ещё и главное преимущество символьной регрессии на деревьях - интерпретируемая формула на выходе - теряется. Чёрт ногу в том нагромождении exp и ln сломит, не слишком-то оно и сокращается. С таким же успехом можно просто обучить нейросеть, она не сильно хуже будет: практически та же чёрная коробочка, которая тоже аппроксимирует какую-нибудь функцию, только хуй знает какую. Всё-таки на матрицах не сильно погадаешь.

Ну короче классно, но очень-очень нишево. И не очень-то и революция. Хотя логический гейт EML Sheffer для аналоговых схем в бумаге уже предложен. А губа не дура!

EML - All elementary functions from a single binary operator

В научном калькуляторе у нас много кнопок. Корни, степени там, синусы-косинусы. А теперь давайте поиграем в Сломанный калькулятор: у нас есть несколько "сломанных" кнопок, которые мы не можем использовать, и есть какое-нибудь число, которое нам нужно ввести. Проблема - в числе встречаются "сломанные" цифры. Придётся как-нибудь ухищраться. Например, с поломанными цифрами 1 и 2, чтобы ввести 21 - мы можем написать просто 7*3. Или 9*3-6. Способов много разных, в целом. Можно дополнительно запретить некоторые арифметические операторы, чтобы ещё сверху жизнь усложнить.

А сколько кнопок можно сломать, пока калькулятор не станет бесполезным?

Вот возьмём косинус. Его можно выразить, как sin(x+π/2). То есть, если у нас есть деление и π, то косинус можно исключить из набора минимально-необходимых функций. Корни - вообще частный случай степени. Если есть "вселенная", то набор "атомов", из которых её можно построить - называется функционально-полным множеством. Суть та же, что и у векторного пространства с его базисом.

В логике вот функционально-полное множество порождает пара {AND, OR} (из них выражаются все остальные операции). И таких множеств из пар на самом деле много, с десяток точно наберётся. Ну, немного ещё потому, что всё разнообразие операторов тоже через AND и OR выражается. Но вот две самых крутых операции - это NAND (NOT AND) и NOR (NOT OR). Если просто отрицать результат AND или OR, то тогда каждый по отдельности создаёт функционально-полное множество. В одно рыло! И вот таких вот однорыльных называют универсальными (бинарными операторами, но пока других универсальных ино-арных ещё не придумали; хотя по поводу тернарных задумались). NAND в логике, кстати, называется Sheffer operator/stroke/etc, много имён у него. Правда, Шеффер был вторым, кто доказал его универсальность, и третьим, кто его вообще описал. Просто все потом немного запутались, и все лавры отошли ему одному.

7 апреля 2026, Andrzej Odrzywolek из Jagiellonian University, что в Кракове (кстати, основан в 1364, старейший в Польше и один из старейших в мире) выпускает бумагу, в которой заявляет, что нечестно это как-то: в логике есть оператор Шеффера, а у нас в вещественной математике - нет. Посидел, повтыкал, и пришёл к умозаключению, что всё прекрасно выражается через eml(a,b) = e^a - ln(b) и константу 1 (чтобы можно было логарифм убрать). Собственно, exp minus log. А "всё" - это вещественные числа, весь набор тригонометрических функций, константы e, π, логарифмы, ну и так далее. Конечно, это всё ещё не NAND, которому даже константы не нужно, но и такая универсальность одной функции с константой - уже круто, учитывая, что изначально там было 36 элементов. Вольфрам у себя использует вот множество из 7 операторов. А ещё круто потому, что грамматика сводится просто к S -> 1|eml(S,S).

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

В нейросеть eml, в общем-то, можно всунуть разве что как функцию активации. Какой-нибудь ln(x) оно идеально выучивает и предсказывает. Что, конечно, просто невероятное достижение - функция активации с логарифмом смогла повторить логарифм. А вот для чего-нибудь посложнее обучить уже не получится: с ln(e−ln(e^x−ln(y))) функцию распидорасило настолько, что обучение просто сломалось. Чего и стоило ожидать от экспоненты, которую единственное, что пытается сдерживать - это какой-то там логарифм. Ещё и вычитанием. EML очень быстро "взрывается", а возле нуля ещё и фактически неопределена (дроби слишком малы). Крайне нестабильна, короче.

https://days-since-openclaw-cve.com/

Days since last OpenClaw CVE - 0

A new CVE was published in the last 24 hours.
Because who needs security when you have vibes?

Best CVE-less streak - 12 days


Можно было на чьём-угодно OpenClaw-хосте утвердить себе права админа. Просто вписав /pair approve. Вместо админа. Это не проверялось. Ты получал полный доступ вообще ко всему.

Ебать

Один из приколов в 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)

#находки

Compressing AMT in XZB style

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

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

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

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

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


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

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

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


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. Звучит круто, правда? А это по факту круто. Вот прям очень. Когда-нибудь и я углублюсь в такое.

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

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] (на что заголовок, собственно, и отсылает). Сам документ я оставил в комментариях.

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 байт. Старая-добрая дилемма: либо быстро, либо компактно.