Как стать автором
Обновить

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

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

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

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

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


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


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

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


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


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


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

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

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

Попросили сравнить скорость переносимых и 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 
НЛО прилетело и опубликовало эту надпись здесь
А вот Wang Yi сделал действительно самый быстрый (пока) переносимый хеш github.com/wangyi-fudan.

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

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

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