Хэширование
xkcd.com
Магический приём, который пронизывает
всё software engineering & computer science.
Используется повсеместно.
Алгоритмы поиска, машинное обучение,
распределённые системы, сжатие данных,
sketching структуры данных...
Алексей, разработчик ClickHouse.
С 2008 занимался движком обработки данных в Яндекс.Метрике.
Пишу на C++.
GROUP BY
SELECT DISTINCT
IN, JOIN
А также:
— uniqExact, uniq;
— arrayEnumerateUniq;
— LIMIT BY.
1. Хэширование.
2. Разрешение коллизий.
3. Ресайзы.
Все пункты не являются обязательными.
Пример: direct mapped cache.
Магический приём, который пронизывает
всё software engineering & computer science.
Используется повсеместно.
Алгоритмы поиска, машинное обучение,
распределённые системы, сжатие данных,
sketching структуры данных...
1. Использование тривиальной хэш-функции
hash(x) = x
Так сделано в реализации стандартной библиотеки (std::hash)
в libstdc++ и в libc++ для int-ов.
Пример: посчитаем, сколько раз каждый пользователь был в интернете.
На входе — массив yandexuid.
yandexuid — UInt64
for (const auto & key : data)
++map[key];
Всего 100 000 000 посещений, в них 17 630 976 разных yandexuid.
value_type — 16 байт, оперативки примерно 260 MB
— не помещается в LL кэш.
Что такое yandexuid: concat(rand, timestamp).
Младшие биты — unix timestamp с точностью до секунд.
SELECT toHour(EventTime) * 60 + toMinute(EventTime) AS k,
count() AS c FROM hits_all
WHERE EventDate >= today() - 365 GROUP BY k ORDER BY k
INTO OUTFILE 'minutes.tsv' FORMAT TabSeparated
Elapsed: 800.580 sec. Processed 4.33 trillion rows
std::unordered_map
— разницы в производительности нет (10.319 vs 10.279 сек)
google::dense_hash_map
— разница в производительности: 3.156 vs 81.86 сек — в 26 раз
ClickHouse HashMap
— разница в производительности: 2.527 vs 10.264 сек — в 4 раза
hash(x, y) = hash(x) ^ hash(y) — ужасно, так делать нельзя
hash(x, y) = hash(hash(x) ^ y) — можно так, но зачастую можно лучше
Пример:
hash(int x) = CityHash64(reinterpret_cast<const char *>(&x), sizeof(x))
— очень плохо.
— хэш-функции для строк как правило не инлайнятся; — они содержат много бранчей — представляют собой вариации на тему duff device для fast path цикла и обработки хвостиков, всё это не нужно, если хэшируем типы фиксированной длины.
HashMap в ClickHouse:
| — хорошая хэш-функция: | 2.439 сек. |
| — ошибочно используем CityHash64 для UInt64: | 3.347 сек. |
| — используем murmur finalizer: | 2.722 сек. |
| — тривиальная хэш-функция: | 9.721 сек. |
std::unordered_map:
| — хорошая хэш-функция: | 10.097 сек. |
| — ошибочно используем CityHash64 для UInt64: | 11.040 сек. |
(производительность скрадывается зависимыми кэш-промахами)
Для прямо или косвенно связанных друг с другом структур данных используйте разные хэш-функции.
Пример: для шардирования данных и для хэш-таблиц при обработке этих данных.
☠ Приводит к замедлению в разы или к полному залипанию!
Иногда выбор нескольких хэш-функций из одного семейства — недостаточно хорошее решение.
Пример: hash(x, seed) = hash(x ^ seed)— зачастую недостаточно хорошо,
если часть операций hash коммутирует с xor.
Пример: в libstdc++ из gcc 7 используется FNV1a для строк. Эта хэш-функция содержит цикл по байтам, может работать не медленно только для коротких строк, но для коротких строк слишком низкое качество.
Пример: Делаем 5 млн. вставок. PageCharset — короткие повторяющиеся строки (windows-1251, utf-8)
| — FNV1a: | 76 409 407 inserts/sec. |
| — CityHash64: | 94 725 900 inserts/sec. |
| — хэш-функция из ClickHouse: | 112 791 109 inserts/sec. |
| — FNV1a: | 10 108 171 inserts/sec. |
| — CityHash64: | 11 337 682 inserts/sec. |
| — хэш-функция из ClickHouse: | 13 637 320 inserts/sec. |
Иногда не ошибка, если надо избежать algorithmic complexity attack.
В этом случае используйте SipHash. Не используйте MD5, SHA1,2,3 для хэш-таблиц.
Но добиться этого иногда можно и другими способами (выбор случайной хэш-функции из семейства)
* правда это обычно не помогает.
Пример: URL:
| CityHash64: | 3755.84 MB/sec. |
| SipHash: | 1237.51 MB/sec. |
| MD5: | 361.86 MB/sec. |
| CityHash64: | 822.56 MB/sec. |
| SipHash: | 183.35 MB/sec. |
| MD5: | 30.87 MB/sec. |
Пример: SMHasher. https://github.com/aappleby/smhasher
Avalanche, Bit Independence
http://ticki.github.io/blog/designing-a-good-non-cryptographic-hash-function/Для разных алгоритмов имеют смысл разные критерии качества хэш-функций.
Хэш-функция может быть качественной для linear probing open addressing hash table, но не качественной для HyperLogLog.
inline UInt64 intHash64(UInt64 x)
{
x ^= x >> 33;
x *= 0xff51afd7ed558ccdULL;
x ^= x >> 33;
x *= 0xc4ceb9fe1a85ec53ULL;
x ^= x >> 33;
return x;
}
2.5 "раунда", состоящих из xor-shift и умножения. (city, farm, metro hash используют примерно то же самое)
latency умножения — 3 такта, xor и shift — 1 такт, в одной хэш-функции нет instruction level parallelism, поэтому всего latency примерно 12 тактов.
Достоинства: — хорошее качество; — независимое вычисление нескольких хэшей векторизуется (gcc, clang даже сами это делают); — instruction-parallel независимое вычисление нескольких хэшей; — понятный смысл.
Недостатки: — когда хэш-таблица помещается в L1..L2 кэш, оверхед всё-таки большой. (можно уменьшить до 1..1.5 раунда, если качество устраивает)
#if __SSE4_2__
#include <nmmintrin.h>
inline UInt64 intHashCRC32(UInt64 x)
{
return _mm_crc32_u64(-1ULL, x);
}
#endif
одна инструкция (на самом деле две) latency 3 такта instruction level parallelism — 3 операции одновременно throughput до 1 такта на операцию https://software.intel.com/sites/landingpage/IntrinsicsGuide/
Недостатки: — всего лишь 32 бита — нулевое качество по Avalanche и Bit Independence Criteria потому что crc коммутирует с xor:
crc(x ^ y) = crc(x) ^ crc(y)
значит при изменении n-го бита x, m-й бит crc(x) меняется или не меняется в зависимости от n, но независимо от x. каждый бит crc — это xor некоторых бит x.
Достоинства: — хорошо работает на практике в хэш-таблицах
Кстати, обе функции обратимы.
Но это никого не волнует.
Throughput, Latency, Avalanche хэш-функций для int-ов: https://github.com/ClickHouse/ClickHouse/blob/master/dbms/src/Common/tests/int_hashes_perf.cpp
./int_hashes_perf 1000000000
(цепочечные; с внешними явными списками разрешения коллизий)
Примеры: std::unordered_map, boost::intrusive::hash_table.
Достоинства: — подходит для толстых объектов; — подходит для неперемещаемых объектов; — подходит для intrusive контейнеров; — node-based container, не инвалидируются указатели на ноды (внимание, итераторы инвалидируются); — нет взаимного влияния цепочек разрешения коллизий — положительной обратной связи на разрастание цепочек; — более терпимо к плохой хэш-функции и к большому load factor.
Недостатки: — низкая кэш-локальность; — нагрузка на аллокатор; — большой оверхед по памяти для маленьких значений;
(closed hashing; с внутренними цепочками разрешения коллизий) Примеры: ClickHouse HashMap, sparse_hash_map, dense_hash_map, HashMap в Rust.
Недостатки: — очень чувствительны к выбору хэш-функции; — например, абсолютно плохо работают с тривиальной хэш-функцией; — многообразие вариантов memory layout и collision resolution, нужно выбирать под конкретную задачу; — сильная деградация производительности, если хранить inplace крупные объекты;
Достоинства: — при правильном использовании работают быстро :)
Не обязательно списки.
Другие внешние явные структуры данных для разрешения коллизий: — непрерывные массивы; — сбалансированные деревья (пример: HashMap в Java).
Chaining с первой ячейкой inplace; — сочетают в себе недостатки chaining и open-addressing; — можно использовать комбинированный вариант для multiset/multimap.
Как обозначить, что ячейка занята? 1. Явно — бит занятости в каждой ячейке. 2. Неявно — отсутствие значение обозначено нулевым ключом, а элемент с нулевым ключом хранится отдельно.
— простой массив ячеек; — необычный массив ячеек — sparse array (пример: sparse_hash_map); — двухуровневый массив; — массив с address translation (косвенной адресацией); — два массива ячеек — один для key, другой для mapped; — два и больше массива ячеек для cuckoo hash table; — массив ячеек + битовые маски;
— значение хэша — для shortcut сравнения тяжёлых ключей; для отсутствия повторных вычислений при ресайзах; — номер версии для мгновенной очистки хэш-таблицы; — информация, как далеко находится элемент с соответствующим значением остатка от деления хэша; — указатели, формирующие цепочку разрешения коллизий как в chaining hash table; — атомики и даже мъютексы для блокировок.
1. В случае, когда всё влезает в L1..L2 кэш (иногда L3 кэш): — вычисление хэш-функции; — обход цепочек разрешения коллизий (бранчи, арифметика, иногда просто много инструкций); — сравнение элементов на равенство. 2. В случае, когда всё не помещается в LL кэш (иногда только в L3 кэш): — случайные чтения из памяти.
Достоинства: — отличная кэш-локальность; — очень простой; — самый быстрый при условии одинаковых длин цепочек; Недостатки: — максимально капризный метод; — не терпит большой fill factor. Средняя сложность lookup-а в хэш-таблице: O(n^2), где n — средняя длина цепочки разрешения коллизий.
Достоинства: — неплохая кэш-локальность; — только чуть-чуть сложнее linear probing; — слегка менее капризный;
Пример: используется в dense_hash_map.
Недостатки: — плохая кэш-локальность; — более сложный в реализации и использовании; — менее эффективный при условии одинаковых длин цепочек; Достоинства: — не капризный. Бонус: — полезен не только для хэш-таблиц Например, для Bloom Filter достаточно двух хэш-функций для генерации семейства хэш-функций: hash(x, k) = hash1(x) + k * hash2(x)
Недостатки: — чуть-чуть медленнее linear probing при условии одинаковых длин цепочек; — нужно больше вычислять или хранить значение хэш-функции для ячеек; Достоинства: — такая же кэш-локальность, как у linear probing; — средние длины цепочек существенно меньше linear probing; — хэш-таблица получается почти полностью упорядоченной по остатку от деления хэш-функции, что можно использовать в других алгоритмах. Пример: HashMap в Rust.
Достоинства: — O(1) lookup Недостатки: — два (в среднем полтора) случайных доступа к памяти вместо одного — сложные insert-ы
Достоинства: — O(1) lookup Недостатки: — сложные insert-ы Я вчера взял первую попавшуюся реализацию из интернета, скопировал в проект, и она тормозит. https://github.com/Tessil/hopscotch-map/ http://codecapsule.com/2013/08/11/hopscotch-hashing/
Недостатки: — вообще непонятно зачем.
— какой max fill использовать; — во сколько раз ресайзить; — какой размер хэш-таблицы брать; — как выделять и инициализировать память; — как перемещать элементы;
0.5 — прекрасно подходит для самых капризных вариантов, — если оверхед по памяти слабо волнует; — при max fill = 0.5 и ресайзе в два раза, максимальный оверхед — 4 раза. Больше — неприемлимо для linear probing. Только для Robin Hood (не всегда) и double hashing.
В два раза (или близко). — это почти единственный вариант, если размер-степень двух; Пока хэш-таблица маленькая, можно и в 4 раза. — так как не имеет значения оверхед по памяти; — но польза от этого маленькая; Другие варианты: В 1.5 раза; в golden ratio раз? — сложно, бессмысленно, дорого. Использовать массивы из чанков с косвенной адресацией и добавлять чанки. — сложно, дорого.
2n — дешёвая арифметика — возможно чудовищное замедление при вставке элементов из одной хэш-таблицы в меньшую, если max_fill > 0.5: https://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion
Простое число, близкое к 2n Недостатки: — деление с остатком — очень медленно — если константа compile time, то компилятор заменяет на умножения и сдвиги — чтобы было compile time, приходится использовать switch/case со всеми вариантами — хотя бранч хорошо предсказуем, в итоге всё-равно медленно
Ложное достоинство: — скрадывает низкое качество хэш-функции; Почему ложное: Повышения качества распределения элементов аналогично выбору более качественной хэш-функции, но остаток от деления — слишком дорогой способ повышения качества. Разумно инкапсулировать качество распределения внутри хэш-функции. Возможно, использование простого числа для размера — нелепость. std::unordered_map использует именно эту нелепость.
Если пустая ячейка представлена нулевыми байтами, то можно использовать mmap, или calloc. При ресайзе, можно для inplace ресайза использовать mremap или realloc. Но: — mmap чудовищно медленный; — calloc почти во всех аллокаторах полностью бесполезен (работает через malloc, memset); — realloc почти во всех аллокаторах полностью бесполезен (работает через malloc, memcpy, free); — также заметим, что в std::allocator и вовсе нет интерфейса для realloc или calloc.
~ 2000 вызовов mmap, page fault, munmap в секунду, независимо от количества ядер. Почему mmap медленный: — системный вызов; — изменение структур данных в ядре; — сброс TLB кэша; — page fault.
Можно использовать mmap, munmap, mremap только для больших кусков памяти. 64 MiB (пусть мы умеем работать с памятью со скоростью 50 GB/sec; пусть мы хотим, чтобы оверхед на mmap составлял не больше половины; пусть mmap можно делать всего 1000 раз в секунду) Вообще-то все аллокаторы уже используют mmap, если кусок памяти большой, но: — страдают использованием mmap для недостаточно больших кусков памяти; — не используют mremap для realloc даже в этом случае; Поэтому использовать mmap вручную разумно.
1. Выделить новый массив, вставить туда все элементы. Достоинства: тривиально.
2. Расширить массив в два раза. Правая половина будет пустой. При условии, что размер массива всегда — степень двух, в среднем — чуть меньше половины элементов останутся на месте; — половина элементов переедет на новое место вправо; — некоторая часть элементов переедет немного влево за счёт того, что предыдущие в цепочке разрешения коллизий переедут в правую половину. Достоинства: — это реально эффективнее; — меньше выделяем временной памяти; — лучше кэш-локальность; Недостатки: — сложный алгоритм, легко ошибиться;
3. Амортизированный ресайз — делать ресайз постепенно, размазав сложность на время вставки новых элементов. Достоинства: — контроль над latency; Недостатки: — throughput будет хуже; — сложнее реализация; — надо до двух случайных доступов к памяти вместо одного.
Ресайзить, когда цепочка стала длинной — длина цепочки разрешения коллизий — распределение с тяжёлыми хвостами, и максимальная длина в случае linear probing слишком рано становится большой.
Избавиться от overlap — бессмысленно, так как в случае 2n размера хэш-таблицы, overlap — это bit and с маской, и это очень простая операция, которая никак не уменьшает throughput благодаря instruction level parallelism.
Вынести условие на ресайз за пределы цикла
/// Это цикл:
for (const auto & key : data)
++map[key]; /// А здесь может вызваться ресайз.
if (there is enough space)
for (batch of data)
insert into map without
possibility of resize;
— в данном случае хорошо предсказуемый бранч ничего не стоит
mmap, mremap для больших размеров
if (old_size < MMAP_THRESHOLD && new_size < MMAP_THRESHOLD
&& alignment <= MALLOC_MIN_ALIGNMENT)
{
...
}
else if (old_size >= MMAP_THRESHOLD && new_size >= MMAP_THRESHOLD)
{
...
buf = mremap(buf, old_size, new_size, MREMAP_MAYMOVE);
if (MAP_FAILED == buf)
DB::throwFromErrno("Allocator: Cannot mremap memory chunk...
/// No need for zero-fill, because mmap guarantees it.
}
else
{
...
}
Inplace ресайзы
/** Now some items may need to be moved to a new location.
* The element can stay in place, or move to a new location "on the right",
* or move to the left of the collision resolution chain, because
* the elements to the left of it have been moved to the new "right" location.
*/
size_t i = 0;
for (; i < old_size; ++i)
if (!buf[i].isZero(*this) && !buf[i].isDeleted())
reinsert(buf[i], buf[i].getHash(*this));
/** There is also a special case:
* if the element was to be at the end of the old buffer, [ x]
* but is at the beginning because of the collision resolution chain, [o x]
* then after resizing, it will first be out of place again, [ xo ]
* and in order to transfer it where necessary,
* after transferring all the elements from the old halves you need to [ o x ]
* process tail from the collision resolution chain immediately after it [ o x ]
*/
for (; !buf[i].isZero(*this) && !buf[i].isDeleted(); ++i)
reinsert(buf[i], buf[i].getHash(*this));
Shortcut для подряд идущих одинаковых значений ключа
typename Method::Key prev_key;
for (size_t i = 0; i < rows; ++i)
{
/// Get the key to insert into the hash table.
typename Method::Key key = state.getKey(...);
/// Optimization for consecutive identical keys.
if (!Method::no_consecutive_keys_optimization)
{
if (i != 0 && key == prev_key)
{
/// Add values to the aggregate functions.
continue;
}
else
prev_key = key;
}
method.data.emplace(key, it, inserted);
/// Add values to the aggregate functions.
}
Сохранение значения хэша для тяжёлых ключей
template <typename Key, typename TMapped, typename Hash, ...>
struct HashMapCellWithSavedHash
: public HashMapCell<Key, TMapped, Hash, TState>
{
using Base = HashMapCell<Key, TMapped, Hash, TState>;
size_t saved_hash;
using Base::Base;
bool keyEquals(const Key & key_) const
{ return this->value.first == key_; }
bool keyEquals(const Key & key_, size_t hash_) const
{ return saved_hash == hash_ && this->value.first == key_; }
void setHash(size_t hash_value) { saved_hash = hash_value; }
size_t getHash(const Hash & hash) const { return saved_hash; }
};
Мгновенно очищаемые хэш-таблицы
template <typename Key, typename BaseCell>
struct ClearableHashTableCell : public BaseCell
{
using State = ClearableHashSetState;
using value_type = typename BaseCell::value_type;
UInt32 version;
bool isZero(const State & state) const
{ return version != state.version; }
void setZero() { version = 0; }
static constexpr bool need_zero_value_storage = false;
ClearableHashTableCell() {}
ClearableHashTableCell(const Key & key_, const State & state)
: BaseCell(key_, state), version(state.version) {}
};
Prefetch
template <size_t N>
void ALWAYS_INLINE hasN(const Key * x, UInt8 * res) const
{
size_t hash_value[N];
size_t place[N];
for (size_t i = 0; i < N; ++i)
{
hash_value[i] = hash(x[i]);
place[i] = grower.place(hash_value[i]);
_mm_prefetch(&buf[place[i]], _MM_HINT_T0);
}
for (size_t i = 0; i < N; ++i)
res[i] = Cell::isZero(x[i], *this)
? this->hasZero()
: !buf[findCell(x[i], hash_value[i], place[i])]
.isZero(*this);
}
Пометка методов хэш-таблицы как ALWAYS_INLINE, а внешних методов, содержащих циклы работы с хэш-таблицей как NO_INLINE.
#define ALWAYS_INLINE __attribute__((__always_inline__))
#define NO_INLINE __attribute__((__noinline__))
Предсказание размера хэш-таблицы перед её созданием Хранение состояний агрегатных функций inplace в хэш-таблице, если они маленькие Хранение состояний агрегатных функций inplace в хэш-таблице, а если они большое, то разделение на два массива — отдельно ключи и значения Хранение коротких строковых ключей inplace в хэш-таблице с разделением на несколько хэш-таблиц по power-of-two size class-ам Unrolled speculative probing SIMD probing
Для строк: — складываем подряд строки в Arena, в хэш-таблице храним StringRef (std::string_view, std::pair<const char *, size_t>). Для кортежей: — если кортеж маленький, то укладываем его в 64 или 128 или 256 бит и используем это в качестве ключа; — если кортеж большой, то сериализуем его в Arena и работаем как со строковым ключом.