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


    Бенчмарки сделаны в программе 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 представляет широкие возможности по внедрению доверенной цифровой подписи. От настольных, серверных до облачных вариантов реализации. Подробнее
    • +44
    • 11,4k
    • 9
    GlobalSign
    168,00
    Компания
    Поделиться публикацией

    Комментарии 9

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

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

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

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


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


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

          +9

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


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


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


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

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

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

              +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 
            +1
            Про t1ha2 слышал, xxh64(xxhash64) — юзал. А про это чудо слышу впервые, но автор вроде тот же, что и у xxh64, что внушает доверие. Это он оптимизировал дальше xxhash, вдохновляясь в том числе достижением бывшего рекордсмена — t1ha2? Или мы имеем дело просто с эволюцией семейства xxhash? Результаты бенчей выглядят хорошо, нужно будет посмотреть как в реальном применении он выглядит.
              0
              А вот Wang Yi сделал действительно самый быстрый (пока) переносимый хеш github.com/wangyi-fudan.

              Теперь точно придется постараться c t1ha3 )
                0
                Почти переносимый )
                __uint128_t это не стандартный тип — он даже в C/C++ не во всех компиляторах поддерживается (попробуйте clang, например), не говоря о других языках, таких как java, go…
                И далеко не во всех процессорах есть инструкции широкого умножения (из двух слов в одно двойное слово), а ведь переносимый хеш должен быстро работать и на таких процессорах, иначе какой же он 'dream fast'
                  0
                  Умножение 64x64 => 128 используется в массе хешей, включая MUM, t1ha и xxh3.
                  Реализовать такое умножение можно через переносимые операции с uint64_t.

                  Но конечно это будет немного медленнее, чем использование соответствующих intrinsic-ков или __uint128_t от нормального компилятора. Кстати, 128-битные целые поддерживаются clang-ом (и всеми приличными компиляторами) для 64-битных платформ.

                  А вот у java тут действительно болит, точнее со всеми языками на основе java-VM. Ибо от «большого ума» убрали uint64_t, оставив только int64_t. Поэтому умножение 64x64=>128 или 128-битные умножения стоят еще дороже, ибо дополнительно приходиться проверять и переворачивать знаки. Тем не менее для java-кофеварок это приемлемо.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое