xxHash
v0.8.2
XXHASH - это чрезвычайно быстрый алгоритм хэш -алгоритма, обработка с ограничениями скорости оперативной памяти. Код очень портативный и производит идентичные хеши на всех платформах (Little / Big Endian). Библиотека включает в себя следующие алгоритмы:
v0.8.0 ): генерирует 64 или 128-битные хэши, используя векторизованную арифметику. 128-битный вариант называется XXH128.Все варианты успешно завершают тестовый набор Smhasher, который оценивает качество функций хэш (столкновение, дисперсия и случайность). Также предоставляются дополнительные тесты, которые оценивают более тщательные свойства скорости и столкновения 64-битных хэшей.
| Ветвь | Статус |
|---|---|
| выпускать |  |
| девчонка |  |
Справочная система с контролем использует процессор Intel I7-9700K и запускает Ubuntu X64 20.04. Программа с открытым исходным кодом составлена с clang V10.0 с использованием флага -O3 .
| Хеш -название | Ширина | Пропускная способность (ГБ/с) | Небольшая скорость данных | Качество | Комментарий |
|---|---|---|---|---|---|
| XXH3 (SSE2) | 64 | 31,5 ГБ/с | 133.1 | 10 | |
| XXH128 (SSE2) | 128 | 29,6 ГБ/с | 118.1 | 10 | |
| RAM Sequential Read | N/a | 28,0 ГБ/с | N/a | N/a | для справки |
| Город64 | 64 | 22,0 ГБ/с | 76.6 | 10 | |
| T1HA2 | 64 | 22,0 ГБ/с | 99,0 | 9 | Немного худшие столкновения |
| Город128 | 128 | 21,7 ГБ/с | 57.7 | 10 | |
| XXH64 | 64 | 19,4 ГБ/с | 71.0 | 10 | |
| Spookyhash | 64 | 19,3 ГБ/с | 53,2 | 10 | |
| Мама | 64 | 18,0 ГБ/с | 67.0 | 9 | Немного худшие столкновения |
| XXH32 | 32 | 9,7 ГБ/с | 71.9 | 10 | |
| Город32 | 32 | 9,1 ГБ/с | 66.0 | 10 | |
| Мурот3 | 32 | 3,9 ГБ/с | 56.1 | 10 | |
| Сифаш | 64 | 3,0 ГБ/с | 43.2 | 10 | |
| FNV64 | 64 | 1,2 ГБ/с | 62,7 | 5 | Плохое лавиновое свойства |
| Blake2 | 256 | 1,1 ГБ/с | 5.1 | 10 | Криптографический |
| SHA1 | 160 | 0,8 ГБ/с | 5.6 | 10 | Криптографический, но сломанный |
| MD5 | 128 | 0,6 ГБ/с | 7,8 | 10 | Криптографический, но сломанный |
ПРИМЕЧАНИЕ 1: Небольшая скорость данных является грубой оценкой эффективности алгоритма на небольших данных. Для получения более подробного анализа, пожалуйста, обратитесь к следующему абзацу.
Примечание 2: Некоторые алгоритмы имеют быстрее, чем скорость оперативной памяти . В этом случае они могут достичь своего полного потенциала скорости только тогда, когда ввод уже в кеше ЦП (L3 или лучше). В противном случае они максимально подходят на ограничение скорости оперативной памяти.
Производительность на больших данных - это только одна часть изображения. Хэширование также очень полезно в таких конструкциях, как хэш -таблицы и фильтры цветов. В этих вариантах использования часто бывает много небольших данных (начиная с нескольких байтов). Производительность алгоритма может быть очень отличной для таких сценариев, поскольку части алгоритма, такие как инициализация или завершение, становятся фиксированными затратами. Влияние неправильного предсказуния филиала также становится гораздо более присутствующим.
XXH3 был разработан для превосходной производительности как на длинных, так и на небольших входах, которые можно наблюдать на следующем графике:
Для более подробного анализа, пожалуйста, посетите Wiki: https://github.com/cyan4973/xxhash/wiki/performance-comparison#benchmarks-concentration-on-small-data-
Скорость - не единственное свойство, которое имеет значение. Производимые значения хеш должны соблюдать превосходные свойства дисперсии и случайности, чтобы любой подраздел из них может быть использован для максимального распределения таблицы или индекса, а также для снижения количества столкновений до минимального теоретического уровня после парадокса по случаю дня рождения.
xxHash был протестирован с превосходным Smhasher Test Suite Остина Эпплби и проходит все тесты, обеспечивая разумные уровни качества. Он также проходит расширенные тесты от новых вилок Smhasher, включающих дополнительные сценарии и условия.
Наконец, XXHASH предоставляет свой собственный массивный тестер столкновения, способный генерировать и сравнить миллиарды хэшей, чтобы проверить пределы 64-битных алгоритмов хеш-алгоритмов. На этом фронте XXHASH имеет хорошие результаты, в соответствии с парадоксом дня рождения. Более подробный анализ задокументирован в вики.
Следующие макросы могут быть установлены во время компиляции для изменения поведения libxxhash . Они обычно отключены по умолчанию.
XXH_INLINE_ALL : сделать все функции inline , реализация напрямую включена в xxhash.h . Внутренние функции полезны для скорости, особенно для небольших клавиш. Это чрезвычайно эффективно, когда длина ключа выражается как постоянная времени компиляции , при этом улучшение производительности наблюдается в диапазоне +200%. Смотрите эту статью для деталей.XXH_PRIVATE_API : тот же результат, что и XXH_INLINE_ALL . Все еще доступен для устаревшей поддержки. Имя подчеркивает, что имена символов XXH_* не будут экспортированы.XXH_STATIC_LINKING_ONLY : дает доступ к объявлению внутреннего состояния, необходимого для статического распределения. Несовместимо с динамическим связыванием из -за риска изменений ABI.XXH_NAMESPACE : префиксы все символы со значением XXH_NAMESPACE . Этот макрос может использовать только компилируемый набор символов. Полезно, чтобы уклониться от столкновений с именования символов, в случае множества включений исходного кода Xxhash. Клиентские приложения по -прежнему используют обычные имена функций, поскольку символы автоматически переводятся через xxhash.h .XXH_FORCE_ALIGN_CHECK : используйте более быстрый путь прямого чтения, когда ввод выровнен. Этот вариант может привести к значительному улучшению производительности в архитектурах, которые не могут загрузить память с невыносимых адресов, когда вход в HASH выровняется на 32 или 64-разрядных границах. Он (немного) наносит ущерб платформе с хорошей невыполненной производительности доступа к памяти (та же инструкция как для выравниваемых, так и для невыполненных доступа). Эта опция автоматически отключена на x86 , x64 и aarch64 и включена на все другие платформы.XXH_FORCE_MEMORY_ACCESS : метод по умолчанию 0 использует нотацию memcpy() . Метод 1 использует packed атрибут, специфичный для GCC, который может обеспечить лучшую производительность для некоторых целей. Метод 2 Силы не выровненные чтения, которые не являются стандартными, но иногда могут быть единственным способом извлечения лучшего чтения производительности. Метод 3 использует операцию по байтэффифлязу, которая лучше всего подходит для старых компиляторов, которые не входят в линию memcpy() или биг-эндианские системы без инструкции Byteswap.XXH_CPU_LITTLE_ENDIAN : По умолчанию Endianness определяется тестированием времени выполнения, разрешаемой во время компиляции. Если по какой -то причине компилятор не может упростить тест во время выполнения, это может стоить производительность. Можно пропустить автоматическое обнаружение и просто указать, что архитектура является маленькой эндэдийской, установив этот макрос на 1. Установка его до 0 государств Big-Endian.XXH_ENABLE_AUTOVECTORIZE : Авторекторизация может быть инициирована для XXH32 и XXH64, в зависимости от возможностей вектора ЦП и версии компилятора. Примечание. Авторекторизация, как правило, проще запускается с недавними версиями clang . Для XXH32, SSE4.1 или эквивалент (NEON) достаточно, в то время как XXH64 требует AVX512. К сожалению, авторекторизация, как правило, наносит ущерб XXH. По этой причине исходный код XXHASH пытается по умолчанию предотвратить автоматическую векторизацию. При этом системы развиваются, и этот вывод не является. Например, сообщалось, что недавние процессоры Zen4 с большей вероятностью улучшат производительность с векторизацией. Следовательно, если вы предпочитаете или хотите протестировать векторизованный код, вы можете включить этот флаг: он удалит код защиты без векторизации, что повышает вероятность автоматической проверки XXH32 и XXH64.XXH32_ENDJMP : переключить стадию завершения многопользования XXH32 одним прыжком. Как правило, это нежелательно для производительности, особенно при хранении входных данных о случайных размерах. Но в зависимости от точной архитектуры и компилятора, прыжок может обеспечить немного лучшую производительность на небольших входах. Отключено по умолчанию.XXH_IMPORT : MSVC Speciaty: следует определить только для динамического связывания, поскольку это предотвращает ошибки сцепления.XXH_NO_STDLIB : отключить вызов функций <stdlib.h> , в частности malloc() и free() . libxxhash 's s XXH*_createState() всегда будет терпеть неудачу и вернуть NULL . Но одноразовый хэшинг (например, XXH32() ) или потоковая передача с использованием статически выделенных состояний все еще работает, как и ожидалось. Этот флаг сборки полезен для встроенных сред без динамического распределения.XXH_DEBUGLEVEL : когда установлено на любое значение> = 1, включает операторы assert() . Это (немного) замедляет выполнение, но может помочь найти ошибки во время сессий отладки. XXH_NO_XXH3 : удаляет символы, связанные с XXH3 (оба 64 и 128 бит) из генерируемого двоичного файла. XXH3 , безусловно, является наибольшим участником размера libxxhash , поэтому полезно уменьшить бинарный размер для приложений, которые не используют XXH3 .XXH_NO_LONG_LONG : удаляет компиляцию алгоритмов, основанных на 64-битных long long типах, которые включают XXH3 и XXH64 . Только XXH32 будет составлен. Полезно для целей (архитектуры и компиляторы) без 64-разрядной поддержки.XXH_NO_STREAM : отключает потоковой API, ограничивая библиотеку только для одного выстрела.XXH_NO_INLINE_HINTS : По умолчанию, XXHASH использует __attribute__((always_inline)) и __forceinline для повышения производительности за счет размера кода. Определение этого макроса до 1 будет отмечать все внутренние функции как static , что позволит компилятору решать, внедрить ли функцию или нет. Это очень полезно при оптимизации для наименьшего двоичного размера и автоматически определяется при компиляции с -O0 , -Os , -Oz или -fno-inline на GCC и Clang. Это также может повысить производительность в зависимости от компилятора и архитектуры.XXH_SIZE_OPT : 0 : по умолчанию, оптимизируйте для скорости 1 : по умолчанию для -Os и -Oz : отключает некоторые скоростные взломы для оптимизации размера 2 : делает код максимально небольшим, производительность может плакать XXH_VECTOR : вручную выберите набор векторных инструкций (по умолчанию: автоматически выбранный во время компиляции). Доступными наборами инструкций являются XXH_SCALAR , XXH_SSE2 , XXH_AVX2 , XXH_AVX512 , XXH_NEON и XXH_VSX . Компилятор может потребовать дополнительных флагов для обеспечения правильной поддержки (например, gcc на x86_64 требует -mavx2 для AVX2 или -mavx512f для AVX512 ).XXH_PREFETCH_DIST : выберите расстояние предварительного получения. Для адаптации близко к металлу к конкретным аппаратным платформам. Только XXH3.XXH_NO_PREFETCH : отключить предварительную салон. Некоторые платформы или ситуации могут работать лучше без предварительной выборки. Только XXH3. При составлении интерфейса командной строки xxhsum с использованием make , также можно установить следующие переменные среды:
DISPATCH=1 : используйте xxh_x86dispatch.c , чтобы автоматически выбирать между scalar , sse2 , avx2 или avx512 набор инструкций во время выполнения , в зависимости от локального хоста. Эта опция действительна только для систем x86 / x64 .XXH_1ST_SPEED_TARGET : выберите начальную цель скорости, выраженную в MB/S, для первого теста скорости в эталонном режиме. Benchmark будет регулировать цель при последующих итерациях, но первый тест сделан «слепо», нацеливаясь на эту скорость. В настоящее время консервативно устанавливается до 10 МБ/с, для поддержки очень медленных (эмулированных) платформ.NODE_JS=1 : при составлении xxhsum для node.js с emscripten это связывает библиотеку NODERAWFS для неограниченного доступа к файловой системе и исправляет isatty , чтобы сделать утилиту командного строки правильно обнаружить клемму. Это делает бинарную специфику для node.js.Вы можете скачать и установить XXHASH, используя VCPKG Degy Deving Manager:
git clone https://github.com/Microsoft/vcpkg.git
cd vcpkg
./bootstrap-vcpkg.sh
./vcpkg integrate install
./vcpkg install xxhash
Порт XXHASH в VCPKG обновляется членами команды Microsoft и участниками сообщества. Если версия установлена на устаре, пожалуйста, создайте проблему или запрос на вытягивание в репозитории VCPKG.
Самый простой пример вызывает XXHASH 64-битный вариант в качестве функции с одним выстрелом, генерирующей хеш-значение из одного буфера, и вызванная из программы C/C ++:
#include "xxhash.h"
(...)
XXH64_hash_t hash = XXH64 ( buffer , size , seed );
}Потоковой вариант более вовлечен, но позволяет постепенно предоставлять данные:
#include "stdlib.h" /* abort() */
#include "xxhash.h"
XXH64_hash_t calcul_hash_streaming ( FileHandler fh )
{
/* create a hash state */
XXH64_state_t * const state = XXH64_createState ();
if ( state == NULL ) abort ();
size_t const bufferSize = SOME_SIZE ;
void * const buffer = malloc ( bufferSize );
if ( buffer == NULL ) abort ();
/* Initialize state with selected seed */
XXH64_hash_t const seed = 0 ; /* or any other value */
if ( XXH64_reset ( state , seed ) == XXH_ERROR ) abort ();
/* Feed the state with input data, any size, any number of times */
(...)
while ( /* some data left */ ) {
size_t const length = get_more_data ( buffer , bufferSize , fh );
if ( XXH64_update ( state , buffer , length ) == XXH_ERROR ) abort ();
(...)
}
(...)
/* Produce the final hash value */
XXH64_hash_t const hash = XXH64_digest ( state );
/* State could be re-used; but in this example, it is simply freed */
free ( buffer );
XXH64_freeState ( state );
return hash ;
} Файлы библиотеки xxhash.c и xxhash.h лицензированы BSD. Утилита xxhsum имеет лицензию GPL.
Помимо справочной версии C, XXHASH также доступен на многих различных языках программирования, благодаря отличным участникам. Они перечислены здесь.
Многие распределения связывают диспетчер пакетов, который позволяет простой установке XXHASH в качестве интерфейса командной строки libxxhash и интерфейса командной строки xxhsum .
xxhsum -c и отличной поддержки во время ранних выпусков XXHXXH64XXH3 и XXH128
