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

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

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

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

std::collections::HashMap Rust с siphash
std::collections::BTreeMap Rust
std.HashMap Zig с siphash
std.HashMap Zig с wyhash
Моё собственное bptree с различными опциями компилятора для разных экспериментов.

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

Давайте начнём с тупейшего бенчмарка — заполним таблицу равномерно распределёнными случайными 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:

log2(количество ключей)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
rust btree	46	26	19	54	78	94	106	133	152	166	193	215	236	262	290	316	367
rust hashmap siphash	102	67	49	40	37	34	33	32	32	32	32	33	33	34	37	43	51
zig b+tree	46	26	37	56	64	87	100	110	123	143	165	180	197	220	235	269	294
zig hashmap siphash	99	84	64	69	70	68	68	68	68	68	68	68	69	68	69	73	77
zig hashmap wyhash	80	35	29	35	34	35	34	33	34	32	33	31	31	32	32	33	34

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:

log2(количество ключей)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
rust btree	47	48	50	82	107	123	135	163	182	200	227	256	279	309	328	358	405
rust hashmap siphash	101	101	101	100	105	103	102	103	103	103	103	108	112	116	124	140	166
zig b+tree	45	45	59	72	85	107	126	135	148	170	188	203	223	246	264	292	319
zig hashmap siphash	106	108	116	117	120	121	123	124	124	124	123	124	127	130	132	137	147
zig hashmap wyhash	53	53	57	63	68	69	72	72	73	71	72	69	76	81	78	87	92

Отличие только в том, что мы брали среднее для одного поиска за раз, а не для множества, но каким-то образом это замедлило хэш-таблицы в 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:

log2(количество ключей)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
zig b+tree	6	9	31	47	60	82	102	112	126	147	174	186	204	230	245	276	299
zig hashmap siphash	52	53	61	68	71	72	75	76	76	75	75	76	78	80	81	88	95
zig hashmap wyhash	29	29	31	35	38	38	40	41	42	40	40	42	41	39	42	46	43

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

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:

log2(#keys)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
zig b+tree	7	25	37	48	59	82	105	115	126	148	172	186	198	219	240	273	300
zig hashmap siphash	77	79	88	88	90	91	93	94	94	93	95	99	102	103	106	115	130
zig hashmap wyhash	35	37	44	48	52	52	55	57	55	54	57	63	64	63	70	76	88

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

При 2¹⁶ ключей весь датасет занимает примерно 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

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

При 2¹⁶ ключей 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 / случайные строки:

log2(количество ключей)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
zig b+tree	101	124	144	160	184	219	255	279	310	366	427	470	512	577	700	826	965
zig hashmap siphash	145	147	154	159	162	163	165	167	168	173	181	186	196	211	247	287	312
zig hashmap wyhash	49	50	59	65	68	69	72	74	75	81	88	93	103	119	154	188	219

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

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

log2(количество ключей)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
zig b+tree	102	150	221	338	546	618	807	911	1077	1393	1507	1641	1812	2095	2628	2848	3302
zig hashmap siphash	145	147	153	159	162	163	165	167	168	174	182	187	197	210	245	282	313
zig hashmap wyhash	49	50	59	66	69	69	72	74	74	81	88	93	102	117	154	188	214

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

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

Хэши Wasm

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

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

log2(количество ключей)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
zig b+tree	5	14	19	22	27	38	45	49	53	59	70	75	80	87	98	111	120
zig hashmap siphash	33	34	37	38	40	40	41	42	41	41	42	43	44	45	46	52	58
zig hashmap wyhash	29	30	33	35	36	36	37	38	38	37	38	40	40	42	43	47	51

lookup_hit_chain / произвольные строки / wasm:

log2(количество ключей)	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
zig b+tree	64	77	88	97	117	141	154	167	192	216	269	287	294	308	369	436	500
zig hashmap siphash	65	64	68	70	73	71	72	73	73	75	78	81	84	88	102	118	135
zig hashmap whyhash	45	45	48	50	52	52	53	54	54	56	59	62	65	69	79	93	105

В целом соотношения остались практически такими же, хотя похоже, что 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 после него. В случае поиска среди 2¹⁶ ожидается, что 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, они приблизительно соответствуют показателям, которые я нашёл онлайн.

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

ссылка на оригинал статьи https://habr.com/ru/articles/849654/