Бенчмарки сделаны в программе SMHasher на Core 2 Duo 3,0 ГГц
На Хабре неоднократно рассказывали про некриптографические хеш-функции, которые на порядок быстрее криптографических. Они применяются там, где важна скорость и нет смысла применять медленные MD5 или SHA1. Например, для построения хеш-таблиц с хранением пар ключ-значение или для быстрой проверки контрольной суммы при передаче больших файлов.
Одно из самых популярных — семейство хеш-функций xxHash, которое появилось около пяти лет назад. Хотя изначально эти хеши задумывались для проверки контрольной суммы при сжатии LZ4, но их стали применять на самых разных задачах. Оно и понятно: достаточно посмотреть на таблицу вверху со сравнением производительности xxHash и некоторых других хеш-функций. В этом тесте xxHash обходит ближайшего конкурента по производительности в два раза. Новая версия XXH3 поднимает планку ещё выше.
Здесь и далее диаграммы кликабельны
Автор программы Ян Колле (Yann Collet) пишет, что идея усовершенствовать алгоритм появилась в процессе реализации фильтра Блума, который требовал быстрой генерации 64 псевдослучайных бит на основе небольших входных данных переменной длины. В принципе, с этим могла бы справиться стандартная XXH64, но обработка малых входных данных никогда не являлась приоритетом при её разработке. Другими словами, возможна оптимизация. В результате этой оптимизации и появилась новая хэш-функция XXH3, в которой реализованы идеи из некоторых других хэш-алгоритмов. Что самое интересное, XXH3 значительно быстрее всех существующих вариантов xxHash не только на малых входных данных, но практически по всем вариантам использования.
XXH3 устраняет главный недостаток XXH64 — ограничение хеша длиной в 64 бита. Автор говорит, что по этой причине его часто просили выпустить хотя бы 128-битную версию. Так вот, хеш-функция XXH3 теоретически способна генерировать хеши до 256 бит.
В XXH3 внутренний цикл, который оптимально обрабатывается векторизацией. Благодаря этому функция использует аппаратную поддержку на наборах инструкций SSE2, AVX2 и NEON. Производительность зависит от комилятора. Неожиданно оказалось, что версия, скомпилированная clang, намного превосходит остальные. Ян Колле даже подумал, что производительность хеш-функции здесь превысит пропускную способность памяти. Этой версии на графике соответствует пунктирная линия.
В итоге оказалось, что у хеш-функции с поддержкой AVX2 пропускная способность гораздо выше, чем у оперативной памяти, так что важным фактором становится объём кэша. Впрочем, во многих задачах приходится обрабатывать данные, которые уже находятся в кэше, так что работа со скоростью быстрее памяти вполне имеет смысл.
Поддержка инструкций SSE2 позволяет новой хеш-функции значительно обойти XXH32 на 32-битных приложениях, которые по-прежнему часто встречаются в реальном мире (например, байткод WASM).
На маленьких входных данных (20-30 байт) хеш-функция XXH3 ненамного, но всё-таки превосходит CityHash от Google, а также FarmHash, которые раньше были явными лидерами.
На следующем графике приведены результаты самого реалистичного теста с входными данными переменной длины (случайная величина от 1 до N).
В ещё одном тесте учитывается задержка: здесь хеширование начинается по сигналу. Идея в том, чтобы симулировать реальную рабочую нагрузку, где хеш-функция не работает непрерывно, а вызывается в другими процессами в определённый момент.
Автор пишет, что данный тест с умножением 64×64=>128 бит отдаёт предпочтение алгоритмам mumv2 от Владимира Макарова и t1ha2 от Лео Юрьева.
Наконец, вот итоговый и самый важный график, который показывает скорость хеширования на входных данных переменной длины с учётом задержки. Он отражает реальное применение хеш-функции, например, в базах данных.
XXH3 вышла в составе пакета xxHash v0.7.0. У неё стоит пометка «экспериментальная», а для разлочки нужно применить макрос
XXH_STATIC_LINKING_ONLY. Автор поясняет, что хеш-функцию пока можно использовать только на тестовых эфемерных данных, но не для реального сохранения хешей. По итогам экспериментального периода и сбора отзывов пользователей функция XXH3 получит стабильный статус в следующей версии xxHash.
