[Перевод] Насколько быстры B-деревья по сравнению с хэш-таблицами?22.10.2024 10:31

wrirpr8rrokxkxcbhwf1u0hodfw.jpeg


Во многих «скриптовых» языках для стандартных ассоциативных структур данных используется хэш-таблица (hashmap) (объекты Javascript, словари Python и так далее). Хэш-таблицы обладают множеством раздражающих свойств:

  • Уязвимость к hash flooding.
  • В случае защиты от hash flooding случайными seed порядок итераций становится недетерминированным, что мешает при тестировании снэпшотов, создании воспроизводимых сборок и так далее.
  • При вставке может требоваться рехэширование, что в наихудших случаях создаёт для больших хэш-таблиц ужасные задержки.
  • Многократное увеличение больших распределений памяти без фрагментации сложно реализовать в целевых платформах wasm, потому что трюки с виртуальной памятью недоступны, а для страниц невозможно выполнить unmapping.
  • Векторные команды в wasm ограничены, а команды AES отсутствуют. Это делает многие хэш-функции ещё более медленными.


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

Микробенчмарки — это сложно


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

const before = rdtscp();
for (keys) |key| {
    const value_found = map.get(key);
    if (value_found == null) {
        panic("Value not found", .{});
    }
}
const after = rdtscp();
record("lookup_hit_all", map.count(), @divTrunc(after - before, map.count()));


lookup_hit_all / равномерно распределённые u64:
B-деревья выглядят довольно ужасно. На самом деле, намного хуже, чем в другом бенчмарке, ссылку на который мне скинуло множество людей; там при схожих размерах данных поиск B-дерева занимает всего примерно в два раза больше времени, чем у хэш-таблиц. Но не беспокойтесь, мы можем воспроизвести и его: 

for (keys) |key| {
    const before = rdtscp();
    const value_found = map.get(key);
    const after = rdtscp();
    record("lookup_hit_one", map.count(), after - before);
    if (value_found == null) {
        panic("Value not found", .{});
    }
}


lookup_hit_one / равномерно распределённые u64:
Отличие только в том, что мы брали среднее для одного поиска за раз, а не для множества, но каким-то образом это замедлило хэш-таблицы в 2–3 раза!

Оба этих бенчмарка плохи, поэтому давайте создадим их улучшенные версии, прежде чем объяснять разницу. Я сделал это только для структур данных Zig, потому что лентяй.

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

const keys_hitting = try map.allocator.alloc(Key, @max(batch_size, count));
var permutation = XorShift64{};
for (keys_hitting) |*key| {
    const i = permutation.next() % count;
    key.* = keys[i];
}


Во-вторых, вместо того, чтобы измерять по одной операции поиска за раз, мы будем замерять пакеты по 256 операций поиска, чтобы амортизировать лишние траты на команду rdtscp и избавиться от panic в измерениях: 

for (0..@divTrunc(keys_hitting.len, batch_size)) |batch| {
    const keys_batch = keys_hitting[batch * batch_size ..][0..batch_size];
    var values_found: [batch_size]?Key = undefined;

    const before = rdtscp();
    var key: Key = keys_batch[0];
    for (&values_found, 0..) |*value, i| {
        value.* = map.get(key);
        key = keys_batch[(i + 1) % keys_batch.len];
    }
    const after = rdtscp();
    report("lookup_hit_batch", map.count(), @divTrunc(after - before, batch_size));

    for (values_found) |value_found| {
        if (value_found == null) {
            panic("Value not found", .{});
        }
    }
}


Результаты выглядят похожими на результаты lookup_hit_all:

lookup_hit_batch / равномерно распределённые u64:


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

for (0..@divTrunc(keys_hitting.len, batch_size)) |batch| {
    const keys_batch = keys_hitting[batch * batch_size ..][0..batch_size];
    var values_found: [batch_size]?Key = undefined;

    const before = rdtscp();
    var key: Key = keys_batch[0];
    for (&values_found, 0..) |*value, i| {
        value.* = map.get(key);
        key = keys_batch[(i + value.*.?) % keys_batch.len]; // <-- мы изменили эту строку
    }
    const after = rdtscp();
    report("lookup_hit_chain", map.count(), @divTrunc(after - before, batch_size));

    for (values_found) |value_found| {
        if (value_found == null) {
            panic("Value not found", .{});
        }
    }
}


Теперь у нас есть два бенчмарка с одинаковым размером пакетов и абсолютно одинаковыми командами. Единственное отличие заключается в том, что в lookup_hit_chain мы добавили зависимость данных между каждой итерацией цикла — чтобы знать, что искать дальше, нам нужно знать value. Это предотвращает успешное спекулятивное исполнение следующей итерации цикла.

lookup_hit_chain / равномерно распределённые u64:


Хэш-таблица wyhash уменьшает своё время поиска в lookup_hit_batch по сравнению с lookup_hit_chain, но B-дерево от этого никак не выигрывает; однако давайте сделаем относительно обоснованные предположения.

При 216 ключей весь датасет занимает примерно 1 МБ, что вполне умещается в L2, но гораздо больше, чем L1. Каждая операция поиска в хэш-таблице стоит 1 или, возможно, 2 операции поиска в кэше L2; задержка каждой из таких операций составляет примерно 20 тактов. Быстрый путь исполнения wyhash для u64 — это очень малое количество команд совершенно без ветвления: 

bench[0x1014710] <+0>:  rorxq  $0x20, %rdi, %rdx
bench[0x1014716] <+6>:  movabsq $-0x18fc812e5f4bd725, %rax ; imm = 0xE7037ED1A0B428DB
bench[0x1014720] <+16>: xorq   %rax, %rdx
bench[0x1014723] <+19>: movabsq $0x1ff5c2923a788d2c, %rcx ; imm = 0x1FF5C2923A788D2C
bench[0x101472d] <+29>: xorq   %rdi, %rcx
bench[0x1014730] <+32>: mulxq  %rcx, %rcx, %rdx
bench[0x1014735] <+37>: movabsq $-0x5f89e29b87429bd9, %rsi ; imm = 0xA0761D6478BD6427
bench[0x101473f] <+47>: xorq   %rcx, %rsi
bench[0x1014742] <+50>: xorq   %rax, %rdx
bench[0x1014745] <+53>: mulxq  %rsi, %rcx, %rax
bench[0x101474a] <+58>: xorq   %rcx, %rax
bench[0x101474d] <+61>: retq


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

При 216 ключей B-дерево имеет четыре уровня. При вставке случайных ключей на узел обычно приходится 15–16 ключей, поэтому перед нахождением ключа мы в среднем будем выполнять примерно 32 сравнения. Тело этого цикла поиска выглядит так: 

bench[0x10121b0] <+16>: cmpq   %rdx, (%rdi,%rax,8)
bench[0x10121b4] <+20>: jae    0x10121c2                 ; <+34> at bptree.zig
bench[0x10121b6] <+22>: addq   $0x1, %rax
bench[0x10121ba] <+26>: cmpq   %rax, %rsi
bench[0x10121bd] <+29>: jne    0x10121b0                 ; <+16> [inlined] bench.less_than_u64 + 9 at bench.zig:159:5


То есть 5 команд на сравнение, включая два ветвления. Не менее 160 команд и 64 ветвлений на весь поиск.

16 ключей занимают 2 линии кэша, поэтому в среднем получается 1,5 операций поиска в кэше на каждый линейный поиск ключа плюс 1 операция поиска в кэше для попадания в массив дочерних элементов/значений. Суммарно 10 операций поиска в кэше на поиск по всему B-дереву. Каждая из этих операций поиска в кэше зависит от предыдущей операции поиска, так что будет сложно предполагать корректно, но нам может помочь предварительная выборка в одном узле. Если каждая операция поиска в кэше приводит к попаданию в L2 в строгих последовательностях, то следует ожидать примерно 200 тактов, но, вероятно, часть более ранних узлов находится в L1.

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

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

Ключи-строки


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

lookup_hit_chain / случайные строки:


Совершенно случайные строки в реальности крайне маловероятны и дают несправедливые преимущества B-дереву, которому обычно для определения неравенства строк нужно сравнить только их первые символы. Однако в реальных датасетах (например, в URL из логов) ключи часто имеют большие одинаковые префиксы. Мы можем увидеть разницу, если сделаем первые 16 символов постоянными:

lookup_hit_chain / относительно случайные строки:


На хэш-таблицы это никак не влияет, но сильно вредит B-деревьям.

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

Хэши Wasm


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

lookup_hit_chain / равномерно распределённые u64 / wasm:


lookup_hit_chain / произвольные строки / wasm:
В целом соотношения остались практически такими же, хотя похоже, что wyhash немного пострадал по сравнению с siphash.

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

Настройка B-дерева


Я реализовал и B-деревья, и B+деревья. В случае вставок/поиска я не увидел особой разницы между ними, поэтому предпочёл B+дерево за более простую/быструю реализацию сканирования и запросов диапазонов.

btreemap языка Rust ограничивает максимальное количество ключей на узел значением 11. Для всех проверенных мной рабочих нагрузок идеальным параметром, похоже, оказывается ограничение размера узла 512 байтами, то есть 31 ключами для u64 и 20 ключами для строк.

Если позволить листьям и ветвям иметь разные размеры, то ничего не изменится.

Я добился небольшого ускорения, вручную задав структуру узла вида key_count, keys, values/children. Zig по умолчанию предпочитает помещать key_count в конец struct, чтобы избежать паддинга, но мы всегда читаем key_count первым, так что удобно иметь несколько ключей в одной линии кэша. Впрочем, поддержка этой оптимизации на разных архитектурах была утомительной, поэтому я откатился назад и не отразил её в представленных выше тестах.

btreemap языка Rust включает упорядочивание. Я получил небольшой рост скорости, использовав вместо него less_than во время поиска и вызывая equal после него. В случае поиска среди 216 ожидается, что less_than будет вызвано 32 раз, а equal — один раз, так что стоит потратиться на дополнительный вызов equal в обмен на более короткий внутренний цикл поиска.

Я попробовал различные виды двоичного поиска. Лучшим оказался вариант «без ветвления»: 

fn searchBinary(keys: []Key, search_key: Key) usize {
    if (keys.len == 0) return 0;
    var offset: usize = 0;
    var length: usize = keys.len;
    while (length > 1) {
        const half = length / 2;
        const mid = offset + half;
        if (less_than(keys[mid], search_key)) {
            @branchHint(.unpredictable);
            offset = mid;
        }
        length -= half;
    }
    offset += @intFromBool(less_than(keys[offset], search_key));
    return offset;
}


while (length > 1) требует ветвления, но оно легко предсказуемо. branchHint(.unpredictable) заставляет llvm сгенерировать условный переход при offset = mid.

bench[0x101f5e0] <+0>:  movq   %rsi, %rax
bench[0x101f5e3] <+3>:  testq  %rsi, %rsi
bench[0x101f5e6] <+6>:  je     0x101f616                 ; <+54> at bptree.zig
bench[0x101f5e8] <+8>:  xorl   %ecx, %ecx
bench[0x101f5ea] <+10>: cmpq   $0x1, %rax
bench[0x101f5ee] <+14>: je     0x101f60b                 ; <+43> [inlined] bench.less_than_u64 at bench.zig:185:5
bench[0x101f5f0] <+16>: movq   %rax, %rsi
bench[0x101f5f3] <+19>: shrq   %rsi
bench[0x101f5f6] <+22>: leaq   (%rcx,%rsi), %r8
bench[0x101f5fa] <+26>: cmpq   %rdx, (%rdi,%r8,8)
bench[0x101f5fe] <+30>: cmovbq %r8, %rcx
bench[0x101f602] <+34>: subq   %rsi, %rax
bench[0x101f605] <+37>: cmpq   $0x1, %rax
bench[0x101f609] <+41>: ja     0x101f5f0                 ; <+16> at bptree.zig:334:37
bench[0x101f60b] <+43>: cmpq   %rdx, (%rdi,%rcx,8)
bench[0x101f60f] <+47>: adcq   $0x0, %rcx
bench[0x101f613] <+51>: movq   %rcx, %rax
bench[0x101f616] <+54>: retq


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

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

Результат


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

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

Я пока не измерял использование пространства, но можно ожидать, что для B-деревьев ситуация будет хуже. Для случайных ключей типичная доля заполненности узла составляет 50% минус затраты на каждый узел наподобие key_count, а хэш-таблицы на Zig у меня были заняты на 80%. Поэтому мы с большой долей уверенности можем предположить, что B-деревья задействуют на 60 с лишним процентов больше памяти. ИСПРАВЛЕНИЕ: хэш-таблицы имеют низкую заполненность при дублировании, так что их средняя заполненность ближе к 57%. B-дерево же со стабильным перемешиванием приблизится к 67%.

Кроме того, маленькие таблицы очень неоптимально используют пространство. Мне нужно добавить дополнительные настройки, чтобы позволить корневому узлу B-дерева изначально иметь малый размер и постепенно расти вместо того, чтобы тратить полные 512 байтов на таблицу всего с одним ключом.

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

  • Рассмотрите часть с хэш-функцией Stable API для компилятора. Используйте хэш-таблицу с открытой адресацией, сохраняющую порядок хэшей. Устраните проблему hash flooding без создания seed хэшей, например, при помощи дерева.
  • Hash-array mapped tries имеет схожее с B-деревом поведение O (log (n)) с линиями кэша. Но если использовать в листьях хэш-таблицы с открытой адресацией, то глубина вложенности будет относительно низкой.
  • LSM в памяти с инкрементальным слиянием достаточно хорошо работают с дифференциальным потоком данных, но всё равно имеют это поведение O (log (n)) с линиями кэша. Но, возможно, с хэш-таблицами для вторичного поиска индексов это может быть приемлемым решением; кроме того, мы можем считать медленные вставки ценой, которую платим за отсутствие необходимости рехэширования.


Разное


Во всех экспериментах я использовал:

  • Rustc 1.77.2
  • Zig 0.14.0-dev. 1694+3b465ebec
  • wasmtime-cli 20.0.2


Вся работа выполнялась на Intel i7–1260P:

  • с отключенными efficiency core
  • для scaling governer был выбран параметр performance
  • turbo mode отключен
  • ASLR отключен


Обычно я использую cset, чтобы привязать эксперименты к shielded core, но похоже, что последние версии systemd поломали это решение, а замену я пока не придумал.

Остальную часть системы для бенчмарков можно найти в jamii/maps. Я замерял не только операции поиска, но B-деревья имеют сравнимую производительность для каждой операции из-за необходимости сначала находить ключ.

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

Благодарю Дэна Луу за помощь в анализе поведения кэша.

© Habrahabr.ru