«Самые дешёвые, быстрые и надёжные компоненты — те, которых нет», — Гордон Белл
Оглавление
Глава 1: Разрыв в производительности
Глава 3: Бенчмаркинг и профилирование
Глава 4: Массивы и локальность кэша
Глава 5: Связанные списки — убийцы кэша
Глава 7: Хэш-таблицы и конфликты кэша
Глава 8: Динамические массивы и управление памятью
Глава 9: Двоичные деревья поиска
Глава 10: B-деревья и деревья, эффективно использующие кэш
Глава 11: Префиксные деревья и базисные деревья
Кошмар с автозавершением
Наше префиксное дерево было в 8 раз медленнее хэш-таблицы. И оно потребляло 128 МБ памяти, в отличие от хэш-таблицы с 24 МБ.
Такого не должно было произойти. Префиксные деревья — стандартное решение для автозавершения: поиск за O(k), где k — длина строки вне зависимости от размера датасета. Идеально подходит для сопоставления префиксов. Обычно всегда используется для автозавершения, проверки правописания и таблиц IP-маршрутизации.
Мой коллега предложил использовать префиксное дерево для функции автозавершения в нашем инструменте командной строки. Поиск в нём должен был выполняться по 50 тысячам команд и опций. Учебники говорили, что это правильный выбор.
Поэтому мы реализовали префиксное дерево. Результаты бенчмарка оказались ужасными:
$ perf stat -e cache-misses,cycles ./autocomplete_trie "git com" Performance counter stats: 125,000 cache-misses 4,800,000 cycles $ perf stat -e cache-misses,cycles ./autocomplete_hash "git com" Performance counter stats: 18,000 cache-misses 600,000 cycles
Префиксное дерево было в 8 раз медленнее простой хэш-таблицы. И оно использовало 128 МБ памяти, в то время как хэш-таблица — всего 24 МБ.
Где мы ошиблись?
Что нам рассказывают в учебниках
Префиксное дерево (trie) — это дерево, в котором каждое ребро обозначает символ. Вот префиксное дерево для слов «cat», «car» и «dog»:
root / \ c d | | a o / \ | t r g
Чтобы найти «car», мы двигаемся по рёбрам: root → 'c' → 'a' → 'r'.
Учебники говорят следующее:
Общие префиксы: «cat» и «car» имеют общий префикс «ca».
Поиск за O(k): зависит только от длины строки, а не от размера датасета.
Отсутствуют сравнения строк: просто следуем по указателям.
Идеально подходит для автозавершения: находим все слова с префиксом «ca», обходя поддерево.
Звучит замечательно, правда?
Проверка реальностью
Вот реализованная мной структура узла префиксного дерева:
typedef struct trie_node { struct trie_node *children[256]; // 2048 байт (256 × 8-байтных указателей) void *value; // 8 байт bool is_end; // 1 байт // Заполнитель: 7 байт // Всего: 2064 байта на узел } trie_node_t;
2064 байта на узел! Это 33 линии кэша (по 64 байта каждая).
Для наших 50 тысяч команд со средней длиной 8 символов:
Требуется узлов: около 400 тысяч (по одному на символ).
Память: 400000 × 2064 = 825 МБ.
Хэш-таблица: 50000 × 24 = 1,2 МБ.
Префиксное дерево занимало в 687 раз больше памяти, чем хэш-таблица.
Проблема с кэшем
Давайте рассмотрим поиск строки «hello»:
Шаг 1: root → children['h'] (промах кэша - загрузка узла root) Шаг 2: узел → children['e'] (промах кэша - загрузка узла 'h') Шаг 3: узел → children['l'] (промах кэша - загрузка узла 'e') Шаг 4: узел → children['l'] (промах кэша - загрузка первого узла 'l') Шаг 5: узел → children['o'] (промах кэша - загрузка второго узла 'l') Итого: 5 промахов кэша для слова из 5 символов
Каждый узел весит 2 КБ, поэтому они не могут все уместиться в кэше. Поиск каждого символа — это промах кэша.
Сравним это с хэш-таблицей: хэшируем строку (малозатратная операция), один промах кэша для получения бакета, готово. Итого: 1-2 промаха кэша.
Решение 1: базисные деревья (префиксные деревья Patricia)
Первая оптимизация — это сжатие цепочек узлов с одним дочерним элементом.
В стандартном префиксном дереве для «cat» и «car» мы получаем следующее:
root | c | a / \ t r
Узлы «c» и «a» имеют ровно один дочерний элемент. Можно сжать их в один узел с префиксом «ca»:
root | "ca" / \ "t" "r"
Это называется базисным деревом или префиксным деревом Patricia.
Вот реализация, которую я использовал:
typedef struct radix_node { char *prefix; // Префикс переменной длины int prefix_len; struct radix_node *children[256]; void *value; } radix_node_t;
Теперь поиск находит соответствие с префиксом, а затем спускается вниз:
void* radix_search(radix_node_t *node, const char *key) { while (node) { // Сопоставление префикса int i = 0; while (i < node->prefix_len && key[i] == node->prefix[i]) { i++; } // Префикс не совпал? if (i < node->prefix_len) { return NULL; } // Точное совпадение? if (key[i] == '\0') { return node->value; } // Спускаемся к дочернему элементу node = node->children[(unsigned char)key[i]]; key += i + 1; } return NULL; }
В случае нашего инструмента автозавершения это снизило объём используемой памяти на 60% ( 825 МБ до 330 МБ). Но и это всё равно было слишком много.
Решение 2: адаптивное базисное дерево (Adaptive Radix Tree, ART)
Базисное дерево помогло, но у нас всё равно оставалась проблема: каждый узел имел массив из 256 указателей (2048 байт), даже если у него было всего 2 дочерних элемента.
Я посмотрел на данные. Большинство узлов имело меньше 10 дочерних элементов. В этих массивах мы впустую тратили 98% пространства.
Решение: адаптивные типы узлов. Нужно использовать разные структуры узлов в зависимости от того, сколько дочерних элементов у них есть.
Типы узлов
Node4 (1-4 дочерних узла):
typedef struct { uint8_t num_children; uint8_t keys[4]; // 4 байта void *children[4]; // 32 байта // Всего: 40 байт } node4_t;
Node16 (5-16 дочерних узлов):
typedef struct { uint8_t num_children; uint8_t keys[16]; // 16 байт void *children[16]; // 128 байт // Всего: 152 байт } node16_t;
Node48 (17-48 дочерних узлов):
typedef struct { uint8_t num_children; uint8_t index[256]; // Map символ → индекс дочернего узла void *children[48]; // 384 байт // Всего: 640 байт } node48_t;
Node256 (49-256 дочерних узлов):
typedef struct { void *children[256]; // 2048 байт } node256_t;
Адаптивный рост
Стратегия: начинаем с Node4, увеличиваем структуру с добавлением дочерних узлов.
Вставка первого дочернего узла: Node4 Вставка пятого дочернего узла: Node4 → Node16 Вставка 17-го дочернего узла: Node16 → Node48 Вставка 40-го дочернего узла: Node48 → Node256
Экономия памяти:
Средний узел: 40-152 байта (а не 2048 байт)
Снижение объёма занимаемой памяти в 10-50 раз
Результаты бенчмарка
Я заново реализовал инструмент автозавершения на основе адаптивного базисного дерева. Вот сравнение:
Датасет: 50 000 команд (средняя длина 8 символов) Тест: 1 000 000 случайных операций поиска Стандартное префиксное дерево: Память: 825 МБ Такты на поиск: 4 800 Промахи кэша: 12,5 Базисное дерево: Память: 330 МБ Такты на поиск: 2 400 Промахи кэша: 6.8 Ускорение: 2,0× Адаптивное базисное дерево (ART): Память: 18 МБ Такты на поиск: 1 200 Промахи кэша: 3,2 Ускорение: 4,0× Хэш-таблица (точка отсчёта): Память: 1,2 МБ Такты на поиск: 600 Промахи кэша: 1,8
ART было в 4 раза быстрее стандартного префиксного дерева и занимало в 45 раз меньше памяти. Но хэш-таблица всё равно была в 2 раза быстрее.
Почему ART лучше стандартных префиксных деревьев:
Узлы меньшего размера: Node4/Node16 умещаются в 1-2 линии кэша вместо 32.
Меньше промахов кэша: 3,2 против 12,5 на одну операцию поиска.
Меньше памяти: 18 МБ против 825 МБ.
Почему хэш-таблицы всё равно выигрывают при точном поиске:
Один промах кэша: хэширование напрямую в бакет.
Отсутствует следование по указателям: одна операция поиска и всё.
Когда стоит использовать префиксные деревья
После всего этого вы можете задаться вопросом: «А стоит ли вообще когда-нибудь использовать префиксное дерево?».
Да, но только тогда, когда вам нужны префиксные операции, которые не могут обеспечить хэш-таблицы.
1. Автозавершение
Наш инструмент автозавершения должен был находить все команды, начинающиеся с «git co». Хэш-таблица не может сделать этого эффективно — придётся сканировать все 50 тысяч элементов.
При использовании ART мы выполняем обход до префикса «git co», а затем составляем список всех дочерних элементов. Это выполняется за O(k + m), где k — длина префикса, а m — количество совпадений.
В конечном итоге мы решили использовать для автозавершения ART, несмотря на замедление по сравнению с хэш-таблицами в два раза, ведь нам нужно было сопоставление префиксов.
2. Таблицы IP-маршрутизации
IP-маршрутизаторам требуется нахождение наибольшего префикса. Найдём самый длинный совпадающий маршрут для IP-адреса 192.168.1.100:
192.168.0.0/16 → Шлюз A.
192.168.1.0/24 → Шлюз B (соответствие длиннее, используем его).
Префиксные деревья идеально для этого подходят. Каждый бит IP-адреса — это ветвь дерева.
3. Системы проверки правописания
Для нахождения слов в пределах редакционного расстояния 1-2 от неправильно написанного слова требуется изучение схожих префиксов. Префиксные деревья обеспечивают эффективность выполнения этой задачи.
4. Когда НЕ использовать префиксные деревья
Не следует использовать префиксные деревья:
Для поиска только точных совпадений: используйте хэш-таблицу (в 2 раза быстрее, в 10 раз меньше памяти).
Малые датасеты (< 1000 элементов): оверхед хэш-таблиц ничтожен.
Случайные строки: если нет общих префиксов, префиксные деревья тратят память впустую.
Пример из реального мира: базисные деревья ядра Linux
Ядро Linux использует базисные деревья для:
Кэша страниц: отображения смещений файлов на страницы памяти.
IDR (распределителя ID): распределяет уникальные ID.
XArray: обобщённого индексированного хранилища.
Вот узел базисного дерева ядра (из lib/radix-tree.c):
struct radix_tree_node { unsigned char shift; // Высота в дереве unsigned char offset; // Смещение слота в родительском узле unsigned int count; // Количество дочерних узлов struct radix_tree_node *parent; void *slots[RADIX_TREE_MAP_SIZE]; // 64 слота };
В ядре используется фиксированный показатель ветвления 64 (6 бит на уровень). Для 32-битного индекса:
Высота: 32 ÷ 6 ≈ 6 уровней.
Промахи кэша: ~6 на поиск.
Это гораздо лучше, чем 32 уровня двоичного дерева.
Почему в ядре применяются базисные деревья:
Разреженные массивы: смещения файлов разреженные (кэшируется не каждая страница).
Операции с диапазонами: итерации со страницами в диапазоне файлов.
Предсказуемая производительность: O(log₆₄ n) в наихудшем случае.
Подведём итог
Проблема с автозавершением была устранена. Заменив стандартное префиксное дерево на адаптивное базисное дерево (ART ), мы снизили объём используемой памяти с 825 МБ до 18 МБ и ускорили поиск в 4 раза. ART обеспечило нужное нам сопоставление префиксов, однако в случае точного поиска хэш-таблицы всё равно остаются в 2 раза быстрее.
Ключевые выводы:
Стандартные префиксные деревья съедают кучу памяти. Из-за массивов с 256 указателями на узел они занимают в 50-100 раз больше памяти, чем хэш-таблицы.
Базисные деревья сжимают цепочки. Объединяя узлы с одним дочерним элементом, можно снизить занимаемую память на 60-70%.
Критически важны адаптивные типы узлов. У большинства узлов мало дочерних элементов. Использование Node4/Node16 вместо массивов из 256 указателей снижает занимаемую память ещё в 10 раз.
Префиксные деревья предназначены для операций с префиксами. Если вам нужны только точные совпадения, то используйте хэш-таблицу. Достоинства префиксных деревьев проявляются, когда нужно автозавершение, сопоставление с самым длинным префиксом или запросы на расстояниях редактирования.
Промахи кэша преобладают. Даже в случае ART мы проходим k уровней в случае строки длины k. Каждый уровень — это потенциальный промах кэша. Хэш-таблицы побеждают, обеспечивая всего 1-2 промаха кэша.
Показатели нашего инструмента автозавершения:
Стандартное префиксное дерево: 4 800 тактов на поиск, 825 МБ памяти.
Адаптивное базисное дерево (ART): 1 200 тактов на поиск, 18 МБ памяти.
Хэш-таблица: 600 тактов на поиск, 1,2 МБ памяти.
Мы выбрали ART, потому что нам нужно сопоставление префиксов, но если бы нам нужны были только точные совпадения, то абсолютным победителем стали бы хэш-таблицы.
В следующей главе: кучи и очереди с приоритетом — как поддерживать отсортированный порядок при помощи O(log n) операций.
