22.10.2024 07:17
PatientZero 2 8300 Источник

Во многих «скриптовых» языках для стандартных ассоциативных структур данных используется хэш-таблица (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:

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-дерево от этого никак не выигрывает; однако давайте сделаем относительно обоснованные предположения.

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

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

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

Комментарии (2)


  1. nin-jin
    22.10.2024 07:57
    #27447480

    Почему бы не использовать разбитый на чанки хеш от кортежа ключей в качестве пути В-TRIE дерева? Если взять 8 байт хеш и бить его по 4 байта, то получаем минимальную глубину - 2 букета.


  1. ptr128
    22.10.2024 07:57
    #27460694

    Btree и hash решают несколько разные задачи. Для поиска только по равенству, само собой, hash эффективней. Но, для примера, в PostgreSQL hash индексы применяются не часто. По той простой причине, что на практике в выборках нужны сравнения не только по равенству, но и > или <. И тут hash не поможет, в отличии от Btree. Так что, если упорядоченность не нужна - применяем hash. Но если нужна - Btree.