xxHash
v0.8.2
XXHASH es un algoritmo de hash extremadamente rápido, procesando a límites de velocidad RAM. El código es altamente portátil y produce hashes idénticos en todas las plataformas (Little / Big Endian). La biblioteca incluye los siguientes algoritmos:
v0.8.0 ): genera hashes de 64 o 128 bits, utilizando aritmética vectorizada. La variante de 128 bits se llama XXH128.Todas las variantes completan con éxito la suite de prueba Smhasher que evalúa la calidad de las funciones hash (colisión, dispersión y aleatoriedad). También se proporcionan pruebas adicionales, que evalúan las propiedades de velocidad y colisión más a fondo de las hashes de 64 bits.
| Rama | Estado |
|---|---|
| liberar |  |
| enchufe |  |
El sistema de referencia de referencia utiliza una CPU Intel I7-9700K y ejecuta Ubuntu X64 20.04. El programa de referencia de código abierto se compila con clang V10.0 usando la bandera -O3 .
| Nombre de hash | Ancho | Ancho de banda (GB/S) | Pequeña velocidad de datos | Calidad | Comentario |
|---|---|---|---|---|---|
| XXH3 (SSE2) | 64 | 31.5 GB/s | 133.1 | 10 | |
| XXH128 (SSE2) | 128 | 29.6 GB/s | 118.1 | 10 | |
| Ram secuencial lectura | N / A | 28.0 GB/s | N / A | N / A | como referencia |
| Ciudad64 | 64 | 22.0 GB/s | 76.6 | 10 | |
| T1ha2 | 64 | 22.0 GB/s | 99.0 | 9 | Colisiones ligeramente peores |
| Ciudad128 | 128 | 21.7 GB/s | 57.7 | 10 | |
| Xxh64 | 64 | 19.4 GB/s | 71.0 | 10 | |
| Spookyhash | 64 | 19.3 GB/s | 53.2 | 10 | |
| Mamá | 64 | 18.0 GB/s | 67.0 | 9 | Colisiones ligeramente peores |
| XXH32 | 32 | 9.7 GB/s | 71.9 | 10 | |
| City32 | 32 | 9.1 GB/s | 66.0 | 10 | |
| Murmur3 | 32 | 3.9 GB/s | 56.1 | 10 | |
| Siphash | 64 | 3.0 GB/s | 43.2 | 10 | |
| FNV64 | 64 | 1.2 GB/s | 62.7 | 5 | Propiedades de Avalanche pobres |
| Blake2 | 256 | 1.1 GB/s | 5.1 | 10 | Criptográfico |
| SHA1 | 160 | 0.8 GB/s | 5.6 | 10 | Criptográfico pero roto |
| MD5 | 128 | 0.6 GB/s | 7.8 | 10 | Criptográfico pero roto |
Nota 1: La velocidad de los datos pequeños es una evaluación aproximada de la eficiencia del algoritmo en pequeños datos. Para un análisis más detallado, consulte el siguiente párrafo.
Nota 2: Algunos algoritmos cuentan más rápido que la velocidad de la RAM . En cuyo caso, solo pueden alcanzar su potencial de velocidad total cuando la entrada ya está en caché de CPU (L3 o mejor). De lo contrario, se maximizan en el límite de velocidad de RAM.
El rendimiento en grandes datos es solo una parte de la imagen. El hash también es muy útil en construcciones como tablas hash y filtros de floración. En estos casos de uso, es frecuente para hash muchos datos pequeños (comenzando en algunos bytes). El rendimiento del algoritmo puede ser muy diferente para tales escenarios, ya que partes del algoritmo, como la inicialización o la finalización, se vuelven fijos. El impacto de la predicción errónea de la rama también se vuelve mucho más presente.
XXH3 ha sido diseñado para un excelente rendimiento en entradas largas y pequeñas, que se pueden observar en el siguiente gráfico:
Para obtener un análisis más detallado, visite el wiki: https://github.com/cyan4973/xxhash/wiki/performance-comparison#benchmarks-concentrating-on-small-data-
La velocidad no es la única propiedad que importa. Los valores de hash producidos deben respetar excelentes propiedades de dispersión y aleatoriedad, de modo que cualquier subsección de la misma pueda usarse para extender al máximo una tabla o índice, así como reducir la cantidad de colisiones al nivel teórico mínimo, después de la paradoja del cumpleaños.
xxHash ha sido probado con la excelente suite de prueba SMHasher de Austin Appleby, y pasa todas las pruebas, asegurando niveles de calidad razonables. También pasa pruebas extendidas de nuevas horquillas de Smhasher, con escenarios y condiciones adicionales.
Finalmente, XXHash proporciona su propio probador de colisión masivo, capaz de generar y comparar miles de millones de hash para probar los límites de los algoritmos hash de 64 bits. En este frente también, Xxhash presenta buenos resultados, en línea con la paradoja de cumpleaños. Un análisis más detallado se documenta en el wiki.
Las siguientes macros se pueden establecer en el momento de la compilación para modificar el comportamiento de libxxhash . Generalmente están deshabilitados de forma predeterminada.
XXH_INLINE_ALL : hacer todas las funciones inline , la implementación se incluye directamente en xxhash.h . La incrustación de funciones es beneficiosa para la velocidad, especialmente para las claves pequeñas. Es extremadamente efectivo cuando la longitud de la clave se expresa como una constante de tiempo de compilación , con mejoras de rendimiento observadas en el rango de +200%. Vea este artículo para más detalles.XXH_PRIVATE_API : mismo resultado que XXH_INLINE_ALL . Todavía disponible para soporte heredado. El nombre subraya que los nombres de símbolos XXH_* no se exportarán.XXH_STATIC_LINKING_ONLY : da acceso a la declaración del estado interno, requerido para la asignación estática. Incompatible con la vinculación dinámica, debido a los riesgos de los cambios de ABI.XXH_NAMESPACE : prefijos todos los símbolos con el valor de XXH_NAMESPACE . Esta macro solo puede usar un conjunto de caracteres compilable. Útil para evadir las colisiones de nombres de símbolos, en el caso de múltiples inclusiones del código fuente de XXHASH. Las aplicaciones del cliente aún usan los nombres de funciones regulares, ya que los símbolos se traducen automáticamente a través de xxhash.h .XXH_FORCE_ALIGN_CHECK : use una ruta de lectura directa más rápida cuando la entrada esté alineada. Esta opción puede dar lugar a una mejora dramática del rendimiento en las arquitecturas que no pueden cargar la memoria de las direcciones no alineadas cuando la entrada al hash se alinea en los límites de 32 o 64 bits. Es (ligeramente) perjudicial en la plataforma con un buen rendimiento de acceso a la memoria no alineado (la misma instrucción para accesos alineados y no alineados). Esta opción se deshabilita automáticamente en x86 , x64 y aarch64 , y se habilita en todas las demás plataformas.XXH_FORCE_MEMORY_ACCESS : el método predeterminado 0 usa una notación portátil memcpy() . El método 1 utiliza un atributo packed específico de GCC, que puede proporcionar un mejor rendimiento para algunos objetivos. Método 2 Fuerzas no alineadas lecturas, que no cumplen con el estándar, pero a veces podría ser la única forma de extraer un mejor rendimiento de lectura. El método 3 utiliza una operación de desplazamiento de bytess, que es mejor para compiladores antiguos que no en línea memcpy() o sistemas de gama grande sin instrucciones de byteswap.XXH_CPU_LITTLE_ENDIAN : por defecto, la endianness se determina mediante una prueba de tiempo de ejecución resuelta en el momento de la compilación. Si, por alguna razón, el compilador no puede simplificar la prueba de tiempo de ejecución, puede costar el rendimiento. Es posible omitir la detección automática y simplemente afirmar que la arquitectura es poco endiana al establecer esta macro en 1. Establecerla en 0 estados grandes.XXH_ENABLE_AUTOVECTORIZE : la vectorización automática se puede activar para XXH32 y XXH64, dependiendo de las capacidades vectoriales de CPU y la versión del compilador. Nota: La autovectorización tiende a activarse más fácilmente con versiones recientes de clang . Para XXH32, SSE4.1 o equivalente (neón) es suficiente, mientras que XXH64 requiere AVX512. Desafortunadamente, la autovectorización es generalmente perjudicial para el rendimiento XXH. Por esta razón, el código fuente XXHASH intenta evitar la autovectorización de forma predeterminada. Dicho esto, los sistemas evolucionan, y esta conclusión no está llegando. Por ejemplo, se ha informado que las CPU Zen4 recientes tienen más probabilidades de mejorar el rendimiento con la vectorización. Por lo tanto, si prefiere o desea probar el código vectorizado, puede habilitar este indicador: eliminará el código de protección de no vectorización, por lo que es más probable que XXH32 y XXH64 se vectorice automáticamente.XXH32_ENDJMP : Etapa de finalización de múltiples ramos de cambio de XXH32 por un solo salto. Esto generalmente es indeseable para el rendimiento, especialmente cuando el hash de las entradas de tamaños aleatorios. Pero dependiendo de la arquitectura y el compilador exactos, un salto podría proporcionar un rendimiento ligeramente mejor en las entradas pequeñas. Deshabilitado por defecto.XXH_IMPORT : MSVC específico: solo debe definirse para la vinculación dinámica, ya que previene los errores de vinculación.XXH_NO_STDLIB : deshabilitar la invocación de las funciones <stdlib.h> , especialmente malloc() y free() . libxxhash 's XXH*_createState() siempre fallará y devolverá NULL . Pero el hashing único (como XXH32() ) o la transmisión que usa estados asignados estáticamente todavía funcionan como se esperaba. Este indicador de compilación es útil para entornos integrados sin asignación dinámica.XXH_DEBUGLEVEL : cuando se establece en cualquier valor> = 1, habilita las declaraciones assert() . Esto (ligeramente) ralentiza la ejecución, pero puede ayudar a encontrar errores durante las sesiones de depuración. XXH_NO_XXH3 : Elimina símbolos relacionados con XXH3 (tanto 64 y 128 bits) del binario generado. XXH3 es, con mucho, el mayor contribuyente al tamaño de libxxhash , por lo que es útil reducir el tamaño binario para aplicaciones que no emplean XXH3 .XXH_NO_LONG_LONG : Elimina la compilación de algoritmos que se basan en tipos long long 64 bits que incluyen XXH3 y XXH64 . Solo se compilará XXH32 . Útil para objetivos (arquitecturas y compiladores) sin soporte de 64 bits.XXH_NO_STREAM : deshabilita la API de transmisión, limitando la biblioteca a variantes de disparo único solamente.XXH_NO_INLINE_HINTS : de forma predeterminada, xxhash usa __attribute__((always_inline)) y __forceinline para mejorar el rendimiento a costa del tamaño del código. Definir esta macro a 1 marcará todas las funciones internas como static , lo que permitirá que el compilador decida si en línea en línea o no. Esto es muy útil cuando se optimiza para el tamaño binario más pequeño, y se define automáticamente al compilar con -O0 , -Os , -Oz o -fno-inline en GCC y Clang. Esto también podría aumentar el rendimiento según el compilador y la arquitectura.XXH_SIZE_OPT : 0 : predeterminado, optimizar para la velocidad 1 : predeterminado para -Os y -Oz : deshabilita algunos hacks de velocidad para la optimización de tamaño 2 : hace que el código sea lo más pequeño posible, el rendimiento puede llorar XXH_VECTOR : seleccione manualmente un conjunto de instrucciones vectoriales (predeterminado: seleccionado automáticamente en el tiempo de compilación). Los conjuntos de instrucciones disponibles son XXH_SCALAR , XXH_SSE2 , XXH_AVX2 , XXH_AVX512 , XXH_NEON y XXH_VSX . El compilador puede requerir banderas adicionales para garantizar un soporte adecuado (por ejemplo, gcc en x86_64 requiere -mavx2 para AVX2 o -mavx512f para AVX512 ).XXH_PREFETCH_DIST : seleccione la distancia de captación previa. Para adaptación cercana a metal a plataformas de hardware específicas. XXH3 solamente.XXH_NO_PREFETCH : deshabilitar previamente. Algunas plataformas o situaciones pueden funcionar mejor sin prestar previamente. XXH3 solamente. Al compilar la interfaz de línea de comando xxhsum usando make , las siguientes variables de entorno también se pueden establecer:
DISPATCH=1 : use xxh_x86dispatch.c , para seleccionar automáticamente entre instrucciones scalar , sse2 , avx2 o avx512 establecidas en tiempo de ejecución , dependiendo del host local. Esta opción solo es válida para los sistemas x86 / x64 .XXH_1ST_SPEED_TARGET : seleccione un objetivo de velocidad inicial, expresado en MB/S, para la primera prueba de velocidad en modo de referencia. Benchmark ajustará el objetivo en iteraciones posteriores, pero la primera prueba se realiza "ciegamente" al apuntar a esta velocidad. Actualmente, de conservación, establecido en 10 MB/s, para admitir plataformas muy lentas (emuladas).NODE_JS=1 : Al compilar xxhsum para node.js con emscripten, esto vincula la biblioteca NODERAWFS para el acceso del sistema de archivos sin restricciones y los parches isatty para que la utilidad de la línea de comandos detecte correctamente el terminal. Esto hace que el binario sea específico de Node.js.Puede descargar e instalar xxhash usando el Administrador de dependencias VCPKG:
git clone https://github.com/Microsoft/vcpkg.git
cd vcpkg
./bootstrap-vcpkg.sh
./vcpkg integrate install
./vcpkg install xxhash
El puerto XXHASH en VCPKG se mantiene actualizado por los miembros del equipo de Microsoft y los contribuyentes comunitarios. Si la versión está desactualizada, cree un problema o extraiga la solicitud en el repositorio de VCPKG.
El ejemplo más simple llama a la variante XXHash de 64 bits como una función de un solo disparo que genera un valor hash a partir de un solo búfer, e invocado desde un programa C/C ++:
#include "xxhash.h"
(...)
XXH64_hash_t hash = XXH64 ( buffer , size , seed );
}La variante de transmisión es más involucrada, pero permite proporcionar datos de forma incremental:
#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 ;
} Los archivos de la biblioteca xxhash.c y xxhash.h tienen licencia BSD. La utilidad xxhsum tiene licencia GPL.
Más allá de la versión de referencia C, XXHash también está disponible en muchos lenguajes de programación diferentes, gracias a los grandes contribuyentes. Se enumeran aquí.
Muchas distribuciones agrupan un administrador de paquetes que permite una instalación fácil de xxhash como una biblioteca libxxhash e interfaz de línea de comandos xxhsum .
xxhsum -c y un gran apoyo durante los primeros lanzamientos XXHXXH64XXH3 y XXH128
