Структуры данных на практике. Глава 9: Двоичные деревья поиска / Habr

«Все знают, что отладка вдвое сложнее, чем написание программы. Но если вы будете писать её максимально умно, то как вообще собираетесь отлаживать?», — Брайан Керниган

Катастрофа с красно-чёрным деревом

Компилятор тратил 60% времени на поиск символов. Не на парсинг, не на генерацию кода, просто на поиск в таблице символов.

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

«У него O(log n); судя по учебникам, оно идеально подходит для этой цели», — сказал мой коллега.

Но профилировщик показывал иное:

$ perf stat -e cache-misses,instructions ./compiler test.c
  Performance counter stats:
    2,847,234 cache-misses
    8,500,000 instructions

2,8 миллиона промахов кэша на 8,5 миллиона команд? Получается один промах кэша на каждые три команды!

Я попробовал нечто безумное: заменил красно-чёрное дерево на отсортированный массив и двоичный поиск. Двоичный поиск тоже имеет O(log n), поэтому, теоретически, должен обладать той же скоростью.

Результат: компилятор стал в 3 раза быстрее.

Как два алгоритма O(log n) могут иметь столь разную производительность?

Расследование

Я прогнал обе реализации через perf, чтобы понять, что происходит:

# Версия с красно-чёрным деревом
$ perf stat -e cache-references,cache-misses,cycles ./compiler_rbtree test.c
  Performance counter stats:
    3,247,832  cache-references
    2,847,234  cache-misses  (87.7% miss rate)
   24,000,000  cycles

# Версия с отсортированным массивом
$ perf stat -e cache-references,cache-misses,cycles ./compiler_array test.c
  Performance counter stats:
    1,123,456  cache-references
      234,567  cache-misses  (20.9% miss rate)
    8,000,000  cycles

Вот и причина: 87,7% промахов кэша у красно-чёрного дерева и всего 20,9% у отсортированного массива.

В системе RISC-V каждый промах кэша стоит примерно 100 тактов. Красно-чёрное дерево основную часть своего времени тратило на ожидание памяти.

Что пишут в учебниках

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

Дерево двоичного поиска (Binary Search Tree, BST):

Вставка: O(log n).
Поиск: O(log n).
Удаление: O(log n).
Обход по порядку даёт отсортированный порядок.

Сбалансированные деревья (AVL, красно-чёрные) гарантируют высоту O(log n) даже при конфликтующих входных данных.

Учебники делают такой вывод: «Используйте сбалансированные BST для динамических датасетов с частыми вставками и операциями поиска».

Кажется, это идеально подходит для таблицы символов, правда?

Проверка реальностью

Но учебники не говорят нам, что деревья двоичного поиска — это настоящий кошмар следования по указателям.

Каждый обход дерева выполняет переход в произвольный адрес памяти. Каждый переход с большой долей вероятности окажется промахом кэша.

Почему деревья двоичного поиска медленные

Проблема заключается в схеме памяти.

Отсортированный массив: последовательная память

При распределении массива все его элементы находятся в памяти друг за другом:

Память: [10][20][30][40][50][60][70][80]
          ↑   ↑   ↑   ↑   ↑   ↑   ↑   ↑
       0x1000 ...последовательно, удобно для кэша...

При доступе к array[4] CPU получает 64-байтную линию кэша, включающую в себя array[4], array[5], array[6] и так далее. Если дальше выполняется доступ к array[5], то этот элемент уже находится в памяти.

Дерево двоичного поиска: разбросанная память

При вставке узлов в BST каждый узел распределяется malloc() отдельно. В результате они оказываются разбросаны по куче:

       40 (@ 0x5000)
      /  \
    20    60 (@ 0x2000, @ 0x8000)
   /  \   /  \
  10  30 50  70 (@ 0x1000, @ 0x3000, @ 0x6000, @ 0x9000)

Каждый узел находится в отдельном адресе памяти. При следовании по указателям выполняется переход к произвольному адресу.

Поведение кэша: конкретный пример

Давайте поищем значение 70 в обеих структурах.

Отсортированный массив (двоичный поиск):

Шаг 1: проверка среднего элемента [40] @ 0x1020
  → ПРОМАХ кэша (100 тактов)
  → CPU получает линию кэша, содержащую [30][40][50][60]

Шаг 2: проверка [60] @ 0x1030
  → ПОПАДАНИЕ в кэш (1 такт) — уже находится в линии кэша!

Шаг 3: проверка [70] @ 0x1038
  → ПОПАДАНИЕ в кэш (1 такт) — всё ещё в кэше

Всего: ~102 такта, 1 промах кэша

Дерево двоичного поиска:

Шаг 1: проверка корня [40] @ 0x5000
  → ПРОМАХ кэша (100 тактов)
  → Получение линии кэша по адресу 0x5000

Шаг 2: переход вправо, проверка [60] @ 0x8000
  → ПРОМАХ кэша (100 тактов) — другой адрес памяти!

Шаг 3: переход вправо, проверка [70] @ 0x9000
  → ПРОМАХ кэша (100 тактов) — ещё один адрес!

Всего: ~300 тактов, 3 промаха кэша

В обоих алгоритмах одинаковое количество сравнений (3), но из-за промахов кэша BST в 3 раза медленнее.

Именно поэтому таблица символов компилятора была такой медленной. Каждая операция поиска символа следовала по указателям в разбросанной памяти.

Бенчмарк

Покажу вам реальный код, который я тестировал. Вот простая реализация BST:

// Узел дерева двоичного поиска
typedef struct bst_node {
    int key;
    void *value;
    struct bst_node *left;
    struct bst_node *right;
} bst_node_t;

void* bst_search(bst_node_t *root, int key) {
    while (root) {
        if (key == root->key) return root->value;
        root = (key < root->key) ? root->left : root->right;
    }
    return NULL;
}

А вот версия с отсортированным массивом:

typedef struct {
    int key;
    void *value;
} array_entry_t;

void* array_search(array_entry_t *arr, int n, int key) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid].key == key) return arr[mid].value;
        if (key < arr[mid].key) right = mid - 1;
        else left = mid + 1;
    }
    return NULL;
}

Я выполнил 10000 случайных операций поиска по датасетам разных размеров:

Датасет: 1000 элементов
  BST:                      2400 тактов на операцию поиска
  Отсортированный массив:    800 тактов на операцию поиска
  Ускорение: 30×

Датасет: 10000 элементов
  BST:                     3200 тактов на операцию поиска
  Отсортированный массив:  1100 тактов на операцию поиска
  Ускорение: 2,9×

Промахи кэша (статистика perf):
  BST:                      8,5 промаха на операцию поиска
  Отсортированный массив:   2,1 промаха на операцию поиска

Отсортированный массив стабильно быстрее в 3 раза быстрее, хоть оба решения имеют O(log n).

Почему отсортированный массив побеждает:

Последовательная схема: при двоичном поиске доступ выполняется к элементам, которые с большой вероятностью находятся в одной линии кэша.
Многократное использование линий кэша: при каждом промахе кэша загружается 8 элементов (64-байтная линия кэша ÷ 8-байтный элемент).
Prefetcher помогает: аппаратный prefetcher может распознать шаговый паттерн и выполнять упреждающую выборку.

У BST нет ни одного этого преимущества. Каждое разыменование указателя оказывается лотереей.

Оверхед памяти

Узел BST (64-битная система):

struct bst_node {
    int key;           // 4 байта
    void *value;       // 8 байт
    struct bst_node *left;   // 8 байт
    struct bst_node *right;  // 8 байт
    // Заполнитель: 4 байта
};
// Всего: 32 байта на элемент

Элемент отсортированного массива:

struct array_entry {
    int key;     // 4 байта
    void *value; // 8 байт
    // Заполнитель: 4 байта (для выравнивания)
};
// Всего: 16 байт на элемент

Используемая память (1000 элементов):

BST: 32 КБ (32 байт × 1000)
Массив: 16 КБ (16 байт × 1000)

BST тратит в 2 раза больше памяти на указатели, что снижает скорость работы с кэшем.

Ну а как насчёт сбалансированных деревьев?

Вы можете подумать: «Да, если вставить отсортированные данные, то базовое BST может выродиться в связанный список. Но что насчёт сбалансированных деревьев, например, AVL или красно-чёрных деревьев? Они имеют гарантированную высоту O(log n)!»

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

Он был прав в том, что сбалансированные деревья решают проблему наихудшего случая. Если вставлять в базовое BST ключи в отсортированном порядке, то получится связанный список с высотой O(n). Сбалансированные деревья предотвращают это.

Но сбалансированные деревья не решают проблему кэша. Они всё равно выполняют следование по указателям в разбросанной памяти.

Красно-чёрные деревья

Красно-чёрное дерево в нашем компиляторе обеспечивало следующие инварианты:

Каждый узел или красный, или чёрный.
Корень чёрный.
Красные узлы имеют чёрные дочерние узлы.
Все пути от корня к листьям имеют одинаковое количество чёрных узлов.

Эти правила гарантируют, что высота дерева будет не больше 2×log₂(n).

Пи вставке или удалении дерево выполняет вращения для сохранения баланса:

Вращение вправо:
    y              x
   / \            / \
  x   C    →     A   y
 / \                / \
A   B              B   C

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

Проблема с кэшем сохраняется

Вот, какие показатели были у красно-чёрного дерева:

$ perf stat -e cache-misses,L1-dcache-load-misses ./compiler_rbtree test.c
  Performance counter stats:
    2,847,234 cache-misses
    2,654,123 L1-dcache-load-misses

Почти каждый обход дерева приводил к промаху кэша. Дерево сбалансировано, но оно всё равно медленное.

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

Так когда же использовать BST?

После замены красно-чёрного дерева сортированным массивом в нашем компиляторе мне задали вопрос: «Нужно ли вообще когда-нибудь использовать BST?»

Да. Но сценарии его применения более специфичны, чем рассказывается в учебниках.

1. Когда есть частые вставки и удаления

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

Но что, если вставки и удаления происходят постоянно?

В случае отсортированного массива:

Вставка: O(n) — необходимо сдвинуть все элементы вправо.
Удаление: O(n) — необходимо сдвинуть все элементы влево.

В случае BST:

Вставка: O(log n) — просто обновить несколько указателей.
Удаление: O(log n) — просто обновить несколько указателей.

Я протестировал это на 1000 произвольных операций вставки/удаления:

Отсортированный массив:   12000 тактов/операция (оверхед на сдвиг)
Красно-чёрное дерево:      3500 тактов/операция
Ускорение: 3,4× для BST

При большом количестве вставок/удалений BST побеждают, несмотря на промахи кэша.

2. Когда нам нужны запросы в диапазоне

У BST есть удобное свойство: при обходе по порядку посещение ключей происходит в отсортированном порядке.

void inorder(bst_node_t *node, void (*visit)(int key)) {
    if (!node) return;
    inorder(node->left, visit);
    visit(node->key);
    inorder(node->right, visit);
}

Благодаря этому становятся эффективными запросы в диапазоне. Если нам нужны «все ключи от 100 до 200», то можно пропускать целые поддеревья, находящиеся вне этого диапазона.

В случае отсортированного массива мы находим 100 при помощи двоичного поиска, а затем выполняем линейное сканирование до 200. Если диапазон большой, это происходит медленнее.

3. Когда датасет маленький

При маленьких датасетах (< 100 элементов) потери от промахов кэша менее серьёзны:

Размер датасета: 50 элементов
  BST:                    180 тактов на операцию поиска
  Отсортированный массив: 150 тактов на операцию поиска
  Разница: всего 20% (не 3×)

Если элементов всего 50, многие узлы BST умещаются в кэш. Проблема следования по указателям менее серьёзна.

В случае малых датасетов используйте то, что проще реализовать. Разница в производительности не так важна.

Оптимизации: BST с учётом кэша

Косвенное двоичное дерево (на основе массива)

Принцип: хранение дерева в массиве при помощи индексной арифметики (например, двоичной кучи).

Схема:

Индекс:  0   1   2   3   4   5   6
Массив: [40][20][60][10][30][50][70]

Структура дерева:
       40 (индекс 0)
      /  \
    20    60 (индекс 1, 2)
   /  \   /  \
  10  30 50  70 (индекс 3, 4, 5, 6)

Родительский элемент i: (i-1)/2
Левый дочерний элемент:  2*i + 1
Правый дочерний элемент: 2*i + 2

Преимущества:

Последовательная схема памяти.
Нет указателей (экономия 16 байт для каждого узла).
Удобство для кэша.

Недостатки:

Должно быть полным деревом (впустую тратит пространство, если не сбалансировано).
Вставка/удаление требует сдвига массива.

Когда использовать: для статических датасетов (сборка один раз, многократные запросы).

B-дерево

Более качественное решение: деревья с несколькими потомками (см. Главу 10)

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

Пример из реального мира: красно-чёрные деревья ядра Linux

После того, как я заменил в нашем компиляторе красно-чёрное дерево на отсортированный массив, один коллега спросил: «Но в ядре Linux повсеместно используются красно-чёрные деревья. Разработчики ошибаются?».

Нет, они используют подходящий для своего случая инструмент.

В ядре Linux красно-чёрные деревья применяются для:

Планировщика процессов: отслеживания запускаемых процессов.
Виртуальной памяти: управления областями памяти.
Таймеров: планирования будущих событий.

Всё это нагрузки с большим объёмом операций записи и частыми вставками и удалениями. Процессы постоянно создаются и уничтожаются. Области памяти распределяются и освобождаются. Таймеры добавляются и удаляются.

Вот, как выглядит узел красно-чёрного дерева ядра (фрагмент lib/rbtree.c):

struct rb_node {
    unsigned long  __rb_parent_color;  // Указатель на родителя + бит цвета
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

Обратите внимание на оптимизацию: указатель на родителя и бит цвета скомбинированы в одном поле. Так как указатели выровнены в 8 байтах, нижние 3 бита всегда равны нулю. Ядро использует один из этих битов для хранения цвета (красный/чёрный). Это экономит по 8 байт на узел.

Я выполнил бенчмаркинг нагрузки, напоминающей планировщик (10000 операций вставки/удаления/поиска):

Красно-чёрное дерево:      2,1 мкс
Отсортированный массив:    8,5 мкс (слишком медленно для планировщика)

При такой нагрузке красно-чёрное дерево в 4 раз быстрее, потому что преобладают вставки и удаления.

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

Подведём итог

Катастрофа с красно-чёрным деревом была устранена простым отсортированным массивом. Компилятор ускорился в 3 раза, а доля времени на поиск символов снизилась с 60% до 20%. Частота промахов кэша упала с 87,7% до 20,9%. Но это не значит, что использование BST всегда будет ошибкой — просто нужно понимать, что необходимо учитывать тип нагрузки.

Основные наблюдения:

Деревья двоичного поиска неудобны для кэша. Каждое разыменование указателя скорее всего будет приводить к промаху кэша. При нагрузках, где активно применяется поиск, отсортированные массивы часто в 3 раза быстрее, несмотря на то, что имеют такую же сложность O(log n).
Важно учитывать память. BST используют в 2 раза больше памяти, чем массивы (32 байта против 16 байт на элемент в 64-битных системах). Лишние указатели вредят и оптимальности использования кэша, и пропускной способности памяти.
BST побеждают в случае нагрузок с большим количеством операций записи. Если вы постоянно выполняете вставки и удаления, то BST в 3-4 раза быстрее, чем отсортированные массивы, потому что в них не нужно сдвигать элементы.
Сбалансированные деревья не решают проблемы с кэшем. Красно-чёрные деревья и АВЛ-деревья гарантируют высоту O(log n), но всё равно приводят к следованию по указателям по разбросанной памяти.
Правильность выбора определяется типом нагрузки. В таблице символов нашего компилятора преобладали операции чтения (поиска), поэтому победили отсортированные массивы. В планировщике Linux преобладают операции записи (постоянные вставки/удаления), поэтому победили красно-чёрные деревья.

Показатели из нашего компилятора:

Красно-чёрное дерево: 2400 тактов на операцию поиска, 87,7% промахов кэша.
Отсортированный массив: 800 тактов на операцию поиска, 20,9% промахов кэша.
Ускорение: 3×.

Показатели из нагрузки с преобладающими операциями записи:

Красно-чёрное дерево: 3500 тактов на операцию.
Отсортированный массив: 12000 тактов на операцию.
Ускорение: 3,4× в пользу BST.

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

Структуры данных на практике. Глава 9: Двоичные деревья поиска

Оглавление