xxHash
v0.8.2
XXHASH est un algorithme de hachage extrêmement rapide, traitement aux limites de vitesse RAM. Le code est hautement portable et produit des hachages identiques sur toutes les plateformes (Little / Big Endian). La bibliothèque comprend les algorithmes suivants:
v0.8.0 ): génère des hachages 64 ou 128 bits, en utilisant l'arithmétique vectorisée. La variante 128 bits est appelée xxh128.Toutes les variantes complètent avec succès la suite de tests Smhasher qui évalue la qualité des fonctions de hachage (collision, dispersion et aléatoire). Des tests supplémentaires, qui évaluent les propriétés de vitesse et de collision plus approfondies de hachages 64 bits, sont également fournies.
| Bifurquer | Statut |
|---|---|
| libérer |  |
| dev |  |
Le système de référence de référence utilise un processeur Intel I7-9700K et exécute Ubuntu x64 20.04. Le programme de référence open source est compilé avec clang V10.0 en utilisant le drapeau -O3 .
| Nom de hachage | Largeur | Bande passante (GB / s) | Petite vitesse de données | Qualité | Commentaire |
|---|---|---|---|---|---|
| Xxh3 (SSE2) | 64 | 31,5 Go / s | 133.1 | 10 | |
| Xxh128 (SSE2) | 128 | 29,6 Go / s | 118.1 | 10 | |
| Lecture séquentielle de RAM | N / A | 28,0 Go / s | N / A | N / A | pour référence |
| Ville64 | 64 | 22,0 Go / s | 76.6 | 10 | |
| T1ha2 | 64 | 22,0 Go / s | 99.0 | 9 | Collisions légèrement pires |
| Ville128 | 128 | 21,7 Go / s | 57.7 | 10 | |
| Xxh64 | 64 | 19,4 Go / s | 71.0 | 10 | |
| Gré | 64 | 19,3 Go / s | 53.2 | 10 | |
| Maman | 64 | 18,0 Go / s | 67.0 | 9 | Collisions légèrement pires |
| Xxh32 | 32 | 9,7 Go / s | 71.9 | 10 | |
| Ville32 | 32 | 9.1 Go / s | 66.0 | 10 | |
| Murmur3 | 32 | 3,9 Go / s | 56.1 | 10 | |
| Siphasse | 64 | 3,0 Go / s | 43.2 | 10 | |
| FNV64 | 64 | 1,2 Go / s | 62.7 | 5 | Pauvres propriétés d'avalanche |
| Blake2 | 256 | 1,1 Go / s | 5.1 | 10 | Cryptographique |
| Sha1 | 160 | 0,8 Go / s | 5.6 | 10 | Cryptographique mais cassée |
| Md5 | 128 | 0,6 Go / s | 7.8 | 10 | Cryptographique mais cassée |
Remarque 1: La vitesse des petites données est une évaluation approximative de l'efficacité de l'algorithme sur les petites données. Pour une analyse plus détaillée, veuillez vous référer au paragraphe suivant.
Remarque 2: Certains algorithmes se présentent plus rapidement que la vitesse RAM . Dans ce cas, ils ne peuvent atteindre leur potentiel à pleine vitesse que lorsque la saisie est déjà dans le cache CPU (L3 ou mieux). Sinon, ils ont maximisé la limite de vitesse RAM.
Les performances sur les grandes données ne sont qu'une partie de l'image. Le hachage est également très utile dans les constructions comme les tables de hachage et les filtres de floraison. Dans ces cas d'utilisation, il est fréquent de hacher beaucoup de petites données (à partir de quelques octets). Les performances de l'algorithme peuvent être très différentes pour de tels scénarios, car certaines parties de l'algorithme, telles que l'initialisation ou la finalisation, deviennent un coût fixe. L'impact de la mauvaise prédiction des branches devient également beaucoup plus présente.
XXH3 a été conçu pour d'excellentes performances sur les entrées longues et petites, qui peuvent être observées dans le graphique suivant:
Pour une analyse plus détaillée, veuillez visiter le wiki: https://github.com/cyan4973/xxhash/wiki/Performance-Comparison#benchmarks-Cencentrating-on-Small-Data-
La vitesse n'est pas la seule propriété qui compte. Les valeurs de hachage produites doivent respecter d'excellentes propriétés de dispersion et de hasard, de sorte que toute sous-section de celle-ci peut être utilisée pour étaler au maximum un tableau ou un indice, ainsi que de réduire la quantité de collisions au niveau théorique minimal, après le paradoxe d'anniversaire.
xxHash a été testé avec l'excellente suite de tests Smhasher d'Austin Appleby et passe tous les tests, garantissant des niveaux de qualité raisonnables. Il passe également des tests prolongés à partir de nouvelles fourches de Smhasher, avec des scénarios et conditions supplémentaires.
Enfin, XXHASH fournit son propre testeur de collision massif, capable de générer et de comparer des milliards de hachages pour tester les limites des algorithmes de hachage 64 bits. Sur ce front aussi, XXHASH propose de bons résultats, conformément au paradoxe d'anniversaire. Une analyse plus détaillée est documentée dans le wiki.
Les macros suivantes peuvent être définies au temps de compilation pour modifier le comportement de libxxhash . Ils sont généralement désactivés par défaut.
XXH_INLINE_ALL : faire toutes les fonctions inline , l'implémentation est directement incluse dans xxhash.h . Les fonctions d'inclinaison sont bénéfiques pour la vitesse, notamment pour les petites clés. Il est extrêmement efficace lorsque la longueur de Key est exprimée comme une constante de temps de compilation , avec des améliorations de performances observées dans la plage de + 200%. Voir cet article pour plus de détails.XXH_PRIVATE_API : même résultat que XXH_INLINE_ALL . Toujours disponible pour le support hérité. Le nom souligne que les noms de symboles XXH_* ne seront pas exportés.XXH_STATIC_LINKING_ONLY : donne accès à la déclaration d'état interne, requise pour l'allocation statique. Incompatible avec la liaison dynamique, en raison des risques de changements ABI.XXH_NAMESPACE : préfixe tous les symboles avec la valeur de XXH_NAMESPACE . Cette macro ne peut utiliser que le jeu de caractères compilable. Utile pour échapper aux collisions de dénomination des symboles, en cas d'inclusions multiples du code source de XXHASH. Les applications client utilisent toujours les noms de fonction réguliers, car les symboles sont automatiquement traduits via xxhash.h .XXH_FORCE_ALIGN_CHECK : utilisez un chemin de lecture direct plus rapide lorsque l'entrée est alignée. Cette option peut entraîner une amélioration spectaculaire des performances des architectures incapables de charger la mémoire à partir d'adresses non alignées lorsque la saisie dans le hachage se trouve être alignée sur les limites 32 ou 64 bits. Il est (légèrement) préjudiciable sur la plate-forme avec de bonnes performances d'accès à la mémoire non alignées (même instruction pour les accès alignés et non alignés). Cette option est automatiquement désactivée sur x86 , x64 et aarch64 et activée sur toutes les autres plates-formes.XXH_FORCE_MEMORY_ACCESS : La méthode par défaut 0 utilise une notation memcpy() portable. La méthode 1 utilise un attribut packed spécifique au GCC, qui peut fournir de meilleures performances à certaines cibles. La méthode 2 force les lectures non alignées, ce qui n'est pas conforme standard, mais pourrait parfois être le seul moyen d'extraire des performances de meilleure lecture. La méthode 3 utilise une opération de bytehift, ce qui est le meilleur pour les anciens compilateurs qui n'en ont pas en ligne memcpy() ou les systèmes Big-Endian sans instruction byteswap.XXH_CPU_LITTLE_ENDIAN : Par défaut, Endianness est déterminé par un test d'exécution résolu au moment de la compilation. Si, pour une raison quelconque, le compilateur ne peut pas simplifier le test d'exécution, il peut coûter des performances. Il est possible de sauter la détection automatique et de simplement indiquer que l'architecture est peu endeur en définissant cette macro sur 1. Le définissant sur 0 états Big-endian.XXH_ENABLE_AUTOVECTORIZE : l'auto-vectorisation peut être déclenchée pour xxh32 et xxh64, selon les capacités vectorielles du processeur et la version du compilateur. Remarque: l'auto-vectorisation a tendance à être déclenchée plus facilement avec les versions récentes de clang . Pour XXH32, SSE4.1 ou équivalent (néon) est suffisant, tandis que XXH64 nécessite AVX512. Malheureusement, l'auto-vectorisation est généralement préjudiciable aux performances XXH. Pour cette raison, le code source XXHASH essaie d'éviter l'auto-vectorisation par défaut. Cela étant dit, les systèmes évoluent, et cette conclusion n'est pas à venir. Par exemple, il a été rapporté que les récents processeurs ZEN4 sont plus susceptibles d'améliorer les performances avec la vectorisation. Par conséquent, si vous préférez ou souhaitez tester du code vectorisé, vous pouvez activer ce drapeau: il supprimera le code de protection sans vectorisation, ce qui le rend plus probable pour que XXH32 et XXH64 soient automatiquement vectorisés.XXH32_ENDJMP : STOWAGE MULTIFICATION MULTI-BRANCH DE XXH32 par un seul saut. Ceci est généralement indésirable pour les performances, en particulier lorsque les entrées de hachage de tailles aléatoires. Mais selon l'architecture exacte et le compilateur, un saut pourrait fournir des performances légèrement meilleures sur les petites entrées. Désactivé par défaut.XXH_IMPORT : MSVC Spécifique: ne doit être défini que pour la liaison dynamique, car il empêche les erreurs de liaison.XXH_NO_STDLIB : Désactiver l'invocation des fonctions <stdlib.h> , notamment malloc() et free() . Le XXH*_createState() NULL libxxhash Mais le hachage à un coup (comme XXH32() ) ou le streaming à l'aide d'états alloués statiquement fonctionne toujours comme prévu. Ce drapeau de construction est utile pour les environnements intégrés sans allocation dynamique.XXH_DEBUGLEVEL : Lorsqu'il est défini sur n'importe quelle valeur> = 1, active les instructions assert() . Cela ralentit (légèrement) l'exécution, mais peut aider à trouver des bugs pendant les séances de débogage. XXH_NO_XXH3 : supprime les symboles liés à XXH3 (64 et 128 bits) de binaire généré. XXH3 est de loin le plus grand contributeur à la taille libxxhash , il est donc utile de réduire la taille binaire des applications qui n'utilisent pas XXH3 .XXH_NO_LONG_LONG : supprime la compilation d'algorithmes reposant sur des types long long 64 bits qui incluent XXH3 et XXH64 . Seul XXH32 sera compilé. Utile pour les cibles (architectures et compilateurs) sans support 64 bits.XXH_NO_STREAM : désactive l'API de streaming, limitant la bibliothèque aux variantes de tir unique.XXH_NO_INLINE_HINTS : Par défaut, xxhash utilise __attribute__((always_inline)) et __forceinline pour améliorer les performances au prix de la taille du code. La définition de cette macro à 1 marquera toutes les fonctions internes comme static , permettant au compilateur de décider ou non d'une fonction. Ceci est très utile lors de l'optimisation de la plus petite taille binaire, et est automatiquement défini lors de la compilation avec -O0 , -Os , -Oz ou -fno-inline sur GCC et Clang. Cela pourrait également augmenter les performances en fonction du compilateur et de l'architecture.XXH_SIZE_OPT : 0 : par défaut, optimiser pour la vitesse 1 : par défaut pour -Os et -Oz : désactive certains hacks de vitesse pour l'optimisation de la taille 2 : rend le code aussi petit que possible, les performances peuvent pleurer XXH_VECTOR : sélectionnez manuellement un jeu d'instructions vectoriel (par défaut: sélectionné automatique au moment de la compilation). Les ensembles d'instructions disponibles sont XXH_SCALAR , XXH_SSE2 , XXH_AVX2 , XXH_AVX512 , XXH_NEON et XXH_VSX . Le compilateur peut nécessiter des drapeaux supplémentaires pour garantir une prise en charge appropriée (par exemple, gcc sur x86_64 nécessite -mavx2 pour AVX2 , ou -mavx512f pour AVX512 ).XXH_PREFETCH_DIST : Sélectionnez Distance de préfecciation. Pour une adaptation à proximité à des plates-formes matérielles spécifiques. Xxh3 uniquement.XXH_NO_PREFETCH : Désactiver la préfecture. Certaines plates-formes ou situations peuvent mieux fonctionner sans pré-lutte. Xxh3 uniquement. Lors de la compilation de l'interface de ligne de commande xxhsum à l'aide make , les variables d'environnement suivantes peuvent également être définies:
DISPATCH=1 : Utilisez xxh_x86dispatch.c , pour sélectionner automatiquement entre scalar , sse2 , avx2 ou avx512 Ensemble d'instructions au moment de l'exécution , selon l'hôte local. Cette option n'est valable que pour les systèmes x86 / x64 .XXH_1ST_SPEED_TARGET : sélectionnez une cible de vitesse initiale, exprimée en MB / s, pour le premier test de vitesse en mode de référence. Benchmark ajustera la cible aux itérations ultérieures, mais le premier test est fait "aveuglément" en ciblant cette vitesse. Actuellement réglé de manière conservatrice à 10 Mo / s, pour prendre en charge les plates-formes très lentes (imitées).NODE_JS=1 : Lors de la compilation xxhsum pour node.js avec Emscripten, cela relie la bibliothèque NODERAWFS pour l'accès et les correctifs sans restriction et les correctifs isatty pour que l'utilitaire de ligne de commande détecte correctement le terminal. Cela rend le binaire spécifique à Node.js.Vous pouvez télécharger et installer XXHASH à l'aide du gestionnaire de dépendance VCPKG:
git clone https://github.com/Microsoft/vcpkg.git
cd vcpkg
./bootstrap-vcpkg.sh
./vcpkg integrate install
./vcpkg install xxhash
Le port XXHASH de VCPKG est tenu à jour par les membres de l'équipe Microsoft et les contributeurs communautaires. Si la version est obsolète, veuillez créer une demande de problème ou d'extraction sur le référentiel VCPKG.
L'exemple le plus simple appelle la variante XXHASH 64 bits en tant que fonction à un coup générant une valeur de hachage à partir d'un seul tampon, et invoquée à partir d'un programme C / C ++:
#include "xxhash.h"
(...)
XXH64_hash_t hash = XXH64 ( buffer , size , seed );
}La variante de streaming est plus impliquée, mais permet de fournir des données progressivement:
#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 ;
} Les fichiers de la bibliothèque xxhash.c et xxhash.h sont sous licence BSD. L'utilitaire xxhsum est sous licence GPL.
Au-delà de la version de référence C, XXHASH est également disponible à partir de nombreux langages de programmation différents, grâce à de grands contributeurs. Ils sont répertoriés ici.
De nombreuses distributions regroupent un gestionnaire de packages qui permet une installation XXHASH facile en tant que bibliothèque libxxhash et interface de ligne de commande xxhsum .
xxhsum -c et un excellent soutien au début des versions xxhXXH64XXH3 et XXH128
