Хабрахабр

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


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

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

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

Здесь и далее диаграммы кликабельны

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

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

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

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

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

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

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

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

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

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

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

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть