Benchmarks realizados en el programa SMHasher en Core 2 Duo 3.0 GHzEn Habré habló repetidamente sobre
funciones hash no criptográficas , que son un orden de magnitud más rápido que las criptográficas. Se usan donde la velocidad es importante y no tiene sentido usar MD5 o SHA1 lento. Por ejemplo, para construir tablas hash con almacenamiento de pares clave-valor o para verificar rápidamente la suma de verificación al transferir archivos grandes.
Una de las más populares es la familia de funciones hash
xxHash , que apareció hace unos cinco años. Aunque inicialmente estos hashes fueron concebidos para verificar la suma de verificación durante la compresión LZ4, comenzaron a usarse en una variedad de tareas. Es comprensible: solo mire la tabla de arriba con una comparación del rendimiento de xxHash y algunas otras funciones hash. En esta prueba, xxHash supera a su competidor más cercano en rendimiento a la mitad. La nueva versión de
XXH3 eleva aún más el listón.
En lo sucesivo, se puede hacer clic en los gráficosLa autora del programa Yann Collet
escribe que la idea de mejorar el algoritmo surgió durante la implementación del filtro Bloom, que requería la generación rápida de 64 bits pseudoaleatorios basados en pequeños datos de entrada de longitud variable. En principio, el estándar XXH64 podría manejar esto, pero el procesamiento de datos de entrada pequeños nunca fue una prioridad en su desarrollo. En otras palabras, la optimización es posible. Como resultado de esta optimización, apareció una nueva función hash XXH3, en la que se implementan ideas de algunos otros algoritmos hash. Lo más interesante es que XXH3 es significativamente más rápido que todas las variantes existentes de xxHash, no solo en datos de entrada pequeños, sino en casi todos los casos de uso.
XXH3 elimina el inconveniente principal de XXH64: limitación de hash de 64 bits. El autor dice que por esta razón a menudo se le pidió que lanzara al menos una versión de 128 bits. Entonces, la función hash XXH3 es teóricamente capaz de generar hashes de hasta 256 bits.
En XXH3, un bucle interno que se maneja de manera óptima mediante vectorización. Debido a esto, la función utiliza soporte de hardware en los conjuntos de instrucciones SSE2, AVX2 y NEON. El rendimiento depende del compilador. Inesperadamente, la versión compilada por clang es muy superior al resto. Ian Colle incluso pensó que el rendimiento de la función hash aquí excedería el ancho de banda de la memoria. Esta versión en el gráfico corresponde a una línea discontinua.
Como resultado, resultó que la función hash con soporte para AVX2 tiene un rendimiento mucho mayor que la RAM, por lo que el tamaño de la caché se convierte en un factor importante. Sin embargo, en muchas tareas es necesario procesar los datos que ya están en la memoria caché, por lo que trabajar a una velocidad más rápida que la memoria tiene mucho sentido.
La compatibilidad con las instrucciones SSE2 permite que la nueva función hash evite significativamente XXH32 en aplicaciones de 32 bits que aún son comunes en el mundo real (por ejemplo, el código de bytes WASM).
En datos de entrada pequeños (20-30 bytes), la función de hash XXH3 no es mucho, pero sigue siendo superior a
CityHash de Google, así como a FarmHash, que solían ser líderes claros.
El siguiente gráfico muestra los resultados de la prueba más realista con datos de entrada de longitud variable (variable aleatoria de 1 a N).
Otra prueba tiene en cuenta el
retraso : aquí el hash comienza con una señal. La idea es simular una carga de trabajo real, donde la función hash no funciona continuamente, sino que se llama en otros procesos en un momento determinado.
El autor escribe que esta prueba con una multiplicación de 64 × 64 => 128 bits prefiere los algoritmos
mumv2 de Vladimir Makarov y
t1ha2 de Leo Yuryev.
Finalmente, aquí está el gráfico final y más importante que muestra la tasa de hash en los datos de entrada de longitud variable, teniendo en cuenta el retraso. Refleja el uso real de la función hash, por ejemplo, en bases de datos.
XXH3 se lanzó como parte del
paquete xxHash v0.7.0 . Tiene la marca "experimental", y para desbloquear necesita usar la macro
XXH_STATIC_LINKING_ONLY . El autor explica que la función hash hasta ahora solo se puede usar en datos efímeros de prueba, pero no para el almacenamiento real de hash. Según los resultados del período experimental y la recopilación de revisiones de usuarios, la función XXH3 recibirá un estado estable en la próxima versión de xxHash.
