Например мы храним большие объекты например 56 байт и ключ будет 8 байт. В сумме кэш-линия 64 байта.
У нас на поиске значения к ключу произошло 4 коллизии в итоге это 4 фетча из памяти, в случае хранения указателей это фетч 1 кэш-линии (так как ключ 8 байт и значение указатель тоже 8 байт) и 1 фетч уже значения из например какой нибудь арены.
Бенчмарки на реальных данных для всех возможных сценариев сделать или найти довольно сложно.
Возможно abseil hash table работала бы немного эффективнее если бы не требовалось реализовывать удаление, за счет того что можно было бы использовать лишний бит в метаданных (например для хранения еще одного бита хеша).
В целом для нашего сценария агрегации удаление не приоритет.
В google::dense_hash_map удаление реализовано через tombstone, клиенту необходимо выбрать ключ который никогда не встретится в хэш таблице и удаленные элементы будут помечаться этим ключом.
В abseil фреймворке признак удален ключ или нет хранится в метаданных.
Спасибо.
Ссылка на доклад https://www.youtube.com/watch?v=hFuTo76tizU.
Ссылка на презентацию https://maksimkita.com/presentations/highload_spb_2022/clickhouse_performance_optimization_practices/index.html.
Например мы храним большие объекты например 56 байт и ключ будет 8 байт. В сумме кэш-линия 64 байта.
У нас на поиске значения к ключу произошло 4 коллизии в итоге это 4 фетча из памяти, в случае хранения указателей это фетч 1 кэш-линии (так как ключ 8 байт и значение указатель тоже 8 байт) и 1 фетч уже значения из например какой нибудь арены.
Нет. В целом наша реализация конкретно на нашем сценарии агрегации работает лучше чем хеш-таблицы от гугла https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/examples/integer_hash_tables_benchmark.cpp#L77. В бенчмарках можно посмотреть на цифры abseil hash table для ARM из-за того что там нету SIMD инструкций она работает медленнее чем google::dense_hash_map.
Бенчмарки на реальных данных для всех возможных сценариев сделать или найти довольно сложно.
Возможно abseil hash table работала бы немного эффективнее если бы не требовалось реализовывать удаление, за счет того что можно было бы использовать лишний бит в метаданных (например для хранения еще одного бита хеша).
У нас реализовано удаление из хэш-таблицы правда только для случая линейных проб с шагом 1. Сам алгоритм https://en.wikipedia.org/wiki/Linear_probing#Deletion. Реализация у нас в коде с комментариям альтернативных вариантов https://github.com/ClickHouse/ClickHouse/blob/master/src/Common/HashTable/HashTable.h#L1046.
В целом для нашего сценария агрегации удаление не приоритет.
В google::dense_hash_map удаление реализовано через tombstone, клиенту необходимо выбрать ключ который никогда не встретится в хэш таблице и удаленные элементы будут помечаться этим ключом.
В abseil фреймворке признак удален ключ или нет хранится в метаданных.
Еще хороший доклад от Алексея про хэш-таблицы в целом https://www.youtube.com/watch?v=EoX82TEz2sQ.