Benchmarks réalisés dans le programme SMHasher sur Core 2 Duo 3.0 GHzOn Habré a parlé à plusieurs reprises de
fonctions de hachage non cryptographiques , qui sont un ordre de grandeur plus rapides que celles cryptographiques. Ils sont utilisés là où la vitesse est importante et cela n'a aucun sens d'utiliser des MD5 ou SHA1 lents. Par exemple, pour créer des tables de hachage avec stockage de paires clé-valeur ou pour vérifier rapidement la somme de contrôle lors du transfert de fichiers volumineux.
L'une des plus populaires est la famille de fonctions de hachage
xxHash , apparue il y a environ cinq ans. Bien qu'au départ, ces hachages aient été conçus pour vérifier la somme de contrôle pendant la compression LZ4, ils ont commencé à être utilisés sur une variété de tâches. C'est compréhensible: regardez simplement le tableau ci-dessus avec une comparaison des performances de xxHash et d'autres fonctions de hachage. Dans ce test, xxHash surpasse de moitié son concurrent le plus proche en termes de performances. La nouvelle version de
XXH3 place la barre encore plus haut.
Ci-après, les graphiques sont cliquablesL'auteur du programme, Yann Collet,
écrit que l'idée d'améliorer l'algorithme est née lors de la mise en œuvre du filtre Bloom, qui a nécessité la génération rapide de 64 bits pseudo-aléatoires basés sur de petites données d'entrée de longueur variable. En principe, le standard XXH64 pouvait gérer cela, mais le traitement de petites données d'entrée n'a jamais été une priorité dans son développement. En d'autres termes, l'optimisation est possible. À la suite de cette optimisation, une nouvelle fonction de hachage XXH3 est apparue, dans laquelle les idées de certains autres algorithmes de hachage sont implémentées. Plus intéressant encore, XXH3 est nettement plus rapide que toutes les variantes xxHash existantes, non seulement sur les petites données d'entrée, mais dans presque tous les cas d'utilisation.
XXH3 élimine le principal inconvénient de XXH64 - limitation du hachage de 64 bits. L'auteur dit que pour cette raison, on lui a souvent demandé de publier au moins une version 128 bits. Ainsi, la fonction de hachage XXH3 est théoriquement capable de générer des hachages jusqu'à 256 bits.
Dans XXH3, une boucle interne gérée de manière optimale par vectorisation. Pour cette raison, la fonction utilise le support matériel sur les jeux d'instructions SSE2, AVX2 et NEON. Les performances dépendent du compilateur. De façon inattendue, la version compilée par clang est de loin supérieure aux autres. Ian Colle pensait même que les performances de la fonction de hachage dépasseraient ici la bande passante mémoire. Cette version sur le graphique correspond à une ligne en pointillés.
En conséquence, il s'est avéré que la fonction de hachage avec prise en charge d'AVX2 a un débit beaucoup plus élevé que la RAM, de sorte que la taille du cache devient un facteur important. Cependant, dans de nombreuses tâches, il est nécessaire de traiter des données qui sont déjà dans le cache, donc travailler à une vitesse plus rapide que la mémoire est parfaitement logique.
La prise en charge des instructions SSE2 permet à la nouvelle fonction de hachage de contourner de manière significative XXH32 sur les applications 32 bits qui sont encore courantes dans le monde réel (par exemple, le bytecode WASM).
Sur les petites données d'entrée (20-30 octets), la fonction de hachage XXH3 n'est pas beaucoup, mais reste supérieure à
CityHash de Google, ainsi qu'à FarmHash, qui était auparavant un leader clair.
Le graphique suivant montre les résultats du test le plus réaliste avec des données d'entrée de longueur variable (variable aléatoire de 1 à N).
Un autre test prend en compte le
retard : ici le hachage commence sur un signal. L'idée est de simuler une charge de travail réelle, où la fonction de hachage ne fonctionne pas en continu, mais est appelée dans d'autres processus à un certain moment.
L'auteur écrit que ce test avec une multiplication de 64 × 64 => 128 bits préfère les algorithmes
mumv2 de Vladimir Makarov et
t1ha2 de Leo Yuryev.
Enfin, voici le graphique final et le plus important qui montre le taux de hachage sur les données d'entrée de longueur variable, en tenant compte du retard. Il reflète l'utilisation réelle de la fonction de hachage, par exemple, dans les bases de données.
XXH3 a été publié dans le cadre du
package xxHash v0.7.0 . Il a la marque «expérimental», et pour le déverrouiller, vous devez utiliser la macro
XXH_STATIC_LINKING_ONLY . L'auteur explique que la fonction de hachage jusqu'à présent ne peut être utilisée que pour tester des données éphémères, mais pas pour le stockage réel des hachages. Selon les résultats de la période expérimentale et la collecte des avis des utilisateurs, la fonction XXH3 recevra un statut stable dans la prochaine version de xxHash.
