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




Бенчмарки сделаны в программе 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.

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

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (6):

  1. zuborg
    /#19902600

    И ни строчки про то, как конкретно, собственно, эта функция устроена (

    А вообще скорость хеширования определяется двумя параметрами — скоростью потоковой обработки и задержкой на одну транзакцию (что эквивалентно максимальному кол-ву хешей в секунду). Первая решает при обработки больших кусков данных (контрольные суммы, системы дедупликации...), но при обработке целых чисел фиксированного размера скорость определяется вторым параметром. Скажем, в математическом алгоритме, где используется map[uint32]uint32, лучше использовать тот же mmh3_x64

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

  2. yleo
    /#19902844 / +1

    Не-переносимые реализации (SSE, AVX, AVX2) не совсем корректно сравнивать с переносимыми — получается волшебно большая разница. Соответственно, логично бы добавить в графики результаты t1ha0_aes.


    Тем не менее, приятно видеть что t1ha2 уверенно идет на втором месте (за вычетом имеющих проблемы FNV и функций без seed).


    В целом здорово что Yann Collet продолжил соревнование, так что постараюсь не отставать с t1ha3 :)

    • yleo
      /#19903146

      На всякий, у xxHash есть некоторые проблемы, причем у всех версий.


      Чтобы устранить подобные недостатки (в том числе, еще пример) следует использовать Merkle–Damgard хотя-бы в варианте "fast wide pipe". С точки зрения практической реализации это означает удвоение ширины внутреннего состояния c перекрестным "опылением" его половин на каждом цикле. Также желательно обеспечивать две точки инъекции данных, чтобы не терять энтропию.


      Внутри t1ha именно так и сделано (wide pipe с перекрестным перемешиванием и двумя точками инъекции). Тем не менее, свойства t1ha2 не идеальны, так как операции перемешивания сильно упрощены ради скорости. Можно сказать, что именно эти упрощения не позволяют конкурировать с SipHash.


      Поэтому, в t1ha3 основное изменением будет именно в этом месте. Кроме этого, будут заменены внутренности t1ha0 (это позволяет задекларированный контракт интерфейса), в том числе вариантов с AES-NI.

    • firedragon
      /#19904804

      Как то один парень из топов сказал. Чуваки вы используете материализованные последовательности и юникс, так какого черта вы требуете что бы ваш DBL был переносим на MS SQL?

      Если встает вопрос оптимизации, то уже четко понятно что будет использоваться что то XEON Gold| Platinum или CUDA.

      • yleo
        /#19905172 / +2

        Попросили сравнить скорость переносимых и SIMD-версий (ну и самому было интересно).


        С использованием всех возможностей i7-6700K (GCC 7.3.0 с опцией -march=native) в перерасчете тактов в GiB/s для частоты процессора 3 ГГц.
        На всякий случай поясню — из t1ha-семейства тут только t1ha0(), так именно она изменяет переносимости ради скорости.


        Bench for huge keys (262144 bytes):
        xxHash3                 :  26951.000 cycle/hash, 29.180 GiB/s @3.0GHz 
        t1ha0                   :  19340.000 cycle/hash, 40.663 GiB/s @3.0GHz 

        Теперь переносимые реализации хеш-функций, последние три строки — это 32-битные хеши для сопоставления.
        На всякий случай поясню — здесь вместо t1ha0() результаты t1ha2_atonce(), так она переносима (и будет вызвана изнутри t1ha0 на CPU без AVX и т.п.):


        Bench for huge keys (262144 bytes):
        xxHash3                 : 131694.000 cycle/hash,  5.972 GiB/s @3.0GHz 
        t1ha2_atonce            :  55506.000 cycle/hash, 14.168 GiB/s @3.0GHz 
        StadtX                  :  58764.000 cycle/hash, 13.383 GiB/s @3.0GHz 
        xxhash64                :  65642.208 cycle/hash, 11.981 GiB/s @3.0GHz 
        --
        t1ha0_32le              : 117699.000 cycle/hash,  6.682 GiB/s @3.0GHz 
        t1ha0_32be              : 121929.000 cycle/hash,  6.450 GiB/s @3.0GHz 
        xxhash32                : 131099.000 cycle/hash,  5.999 GiB/s @3.0GHz 

  3. glowingsword
    /#19905482 / +1

    Про t1ha2 слышал, xxh64(xxhash64) — юзал. А про это чудо слышу впервые, но автор вроде тот же, что и у xxh64, что внушает доверие. Это он оптимизировал дальше xxhash, вдохновляясь в том числе достижением бывшего рекордсмена — t1ha2? Или мы имеем дело просто с эволюцией семейства xxhash? Результаты бенчей выглядят хорошо, нужно будет посмотреть как в реальном применении он выглядит.