XXH3: новый рекордсмен по скорости хеширования

Бенчмарки сделаны в программе SMHasher ^[1] на Core 2 Duo 3,0 ГГц

На Хабре неоднократно рассказывали про некриптографические хеш-функции ^[2], которые на порядок быстрее криптографических. Они применяются там, где важна скорость и нет смысла применять медленные MD5 или SHA1. Например, для построения хеш-таблиц с хранением пар ключ-значение или для быстрой проверки контрольной суммы при передаче больших файлов.

Одно из самых популярных — семейство хеш-функций xxHash ^[3], которое появилось около пяти лет назад. Хотя изначально эти хеши задумывались для проверки контрольной суммы при сжатии LZ4, но их стали применять на самых разных задачах. Оно и понятно: достаточно посмотреть на таблицу вверху со сравнением производительности xxHash и некоторых других хеш-функций. В этом тесте xxHash обходит ближайшего конкурента по производительности в два раза. Новая версия XXH3 ^[4] поднимает планку ещё выше.

^[5]
Здесь и далее диаграммы кликабельны

Автор программы Ян Колле (Yann Collet) пишет ^[6], что идея усовершенствовать алгоритм появилась в процессе реализации фильтра Блума, который требовал быстрой генерации 64 псевдослучайных бит на основе небольших входных данных переменной длины. В принципе, с этим могла бы справиться стандартная XXH64, но обработка малых входных данных никогда не являлась приоритетом при её разработке. Другими словами, возможна оптимизация. В результате этой оптимизации и появилась новая хэш-функция XXH3, в которой реализованы идеи из некоторых других хэш-алгоритмов. Что самое интересное, XXH3 значительно быстрее всех существующих вариантов xxHash не только на малых входных данных, но практически по всем вариантам использования.

XXH3 устраняет главный недостаток XXH64 — ограничение хеша длиной в 64 бита. Автор говорит, что по этой причине его часто просили выпустить хотя бы 128-битную версию. Так вот, хеш-функция XXH3 теоретически способна генерировать хеши до 256 бит.

В XXH3 внутренний цикл, который оптимально обрабатывается векторизацией. Благодаря этому функция использует аппаратную поддержку на наборах инструкций SSE2, AVX2 и NEON. Производительность зависит от комилятора. Неожиданно оказалось, что версия, скомпилированная clang, намного превосходит остальные. Ян Колле даже подумал, что производительность хеш-функции здесь превысит пропускную способность памяти. Этой версии на графике соответствует пунктирная линия.

^[7]

В итоге оказалось, что у хеш-функции с поддержкой AVX2 пропускная способность гораздо выше, чем у оперативной памяти, так что важным фактором становится объём кэша. Впрочем, во многих задачах приходится обрабатывать данные, которые уже находятся в кэше, так что работа со скоростью быстрее памяти вполне имеет смысл.

Поддержка инструкций SSE2 позволяет новой хеш-функции значительно обойти XXH32 на 32-битных приложениях, которые по-прежнему часто встречаются в реальном мире (например, байткод WASM).

^[8]

На маленьких входных данных (20-30 байт) хеш-функция XXH3 ненамного, но всё-таки превосходит CityHash ^[9] от Google, а также FarmHash, которые раньше были явными лидерами.

^[10]

На следующем графике приведены результаты самого реалистичного теста с входными данными переменной длины (случайная величина от 1 до N).

^[11]

В ещё одном тесте учитывается задержка: здесь хеширование начинается по сигналу. Идея в том, чтобы симулировать реальную рабочую нагрузку, где хеш-функция не работает непрерывно, а вызывается в другими процессами в определённый момент.

^[12]

Автор пишет, что данный тест с умножением 64×64=>128 бит отдаёт предпочтение алгоритмам mumv2 ^[13] от Владимира Макарова и t1ha2 ^[14] от Лео Юрьева.

^[15]

Наконец, вот итоговый и самый важный график, который показывает скорость хеширования на входных данных переменной длины с учётом задержки. Он отражает реальное применение хеш-функции, например, в базах данных.

^[16]

XXH3 вышла в составе пакета xxHash v0.7.0 ^[17]. У неё стоит пометка «экспериментальная», а для разлочки нужно применить макрос XXH_STATIC_LINKING_ONLY. Автор поясняет, что хеш-функцию пока можно использовать только на тестовых эфемерных данных, но не для реального сохранения хешей. По итогам экспериментального периода и сбора отзывов пользователей функция XXH3 получит стабильный статус в следующей версии xxHash.

Сертификаты подписи документов ^[18] Microsoft Office, Adobe PDF, LibreOffice и др.
GlobalSign представляет широкие возможности по внедрению доверенной цифровой подписи. От настольных, серверных до облачных вариантов реализации. Подробнее ^[18]

Автор: GlobalSign_admin

Источник ^[19]