Pull to refresh

Comments 10

первая часть, которая до C++ кода, перекликается с ещё одним хорошим докладом: Никита Коваль – На пути к быстрой многопоточной хеш-таблице. Там ребята тоже пришли к варианту с открытой адресацией. Разница в том, что доклад Никиты про реализацию на Джаве.

— Вы продаете хэш-таблицы?
— Нет, только показываем
— Кросивое...


Спасибо большое за текстовый вариант статьи!
Хотел бы спросить, Вы как-нибудь пользуетесь тем фактом, что у Вас нет удалений из хэш-таблицы, и если да, влияет ли это как-то на производительность, и есть ли такие оптимизации у Гугловых опенсорс библиотек?

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

Спасибо за ответ!

Я имел в виду, пользуетесь ли вы где-то фактом того, что вам не нужны удаления во многих случаях, и дает ли это какой-то измеримый выигрыш по сравнению с другими реализациями?

Нет. В целом наша реализация конкретно на нашем сценарии агрегации работает лучше чем хеш-таблицы от гугла 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 работала бы немного эффективнее если бы не требовалось реализовывать удаление, за счет того что можно было бы использовать лишний бит в метаданных (например для хранения еще одного бита хеша).

Хорошая статья. Если говорить про абстракции в С++ и хеш-таблицы, то необходимо написать почему собственно std::unordered_map такая медленная, и не использует описанные оптимизации.

А все потому что, хотя С++ стандарт и не требует конкретной имплементации, он гарантирует следующее про абстракцию std::unordered_map:

References to elements in the unordered_map container remain valid in all cases, even after a rehash.

То есть адреса размещенных в таблице элементов не должны меняться. Это фактически требует метод цепочек или аналогичного. Дальше все еще можно оптимизировать, у Гугла в Abseil есть node_hash_map с такими же гарантиями, но производительность flat_hash_map уже не получишь.

И конечно надо предупреждать об этом читателей, а то вдохновившиеся могут броситься заменять в существующем коде стандартные контейнеры на flat_hash_map. Многим конечно повезет, если адрес не сохраняют, и flat_hash_map подходят. У кого-то упадут тесты и найдут проблему. А у кого-то будет отлично работать в тестах, в них rehash может и не произойдет, а потом бамс и сюрприз в продакшине.

Тут еще необходимо учесть, что реализация на нодах позволяет делать некоторые другие вещи, например, std::unordered_map::extract (с последующим insert) позволит достать элемент из таблицы, поменять ключ и вернуть элемент обратно в таблицу, никуда не двигая/копируя сам элемент. Поэтому для некоторых случаев std::unordered_map вполне может быть шустрее аналогов.

UFO just landed and posted this here

Например мы храним большие объекты например 56 байт и ключ будет 8 байт. В сумме кэш-линия 64 байта.

У нас на поиске значения к ключу произошло 4 коллизии в итоге это 4 фетча из памяти, в случае хранения указателей это фетч 1 кэш-линии (так как ключ 8 байт и значение указатель тоже 8 байт) и 1 фетч уже значения из например какой нибудь арены.

UFO just landed and posted this here
Sign up to leave a comment.