Im Programm SMHasher erstellte Benchmarks für Core 2 Duo 3.0 GHzAuf Habré wurde wiederholt über
nicht-kryptografische Hash-Funktionen gesprochen , die eine Größenordnung schneller sind als kryptografische. Sie werden dort eingesetzt, wo Geschwindigkeit wichtig ist und es keinen Sinn macht, langsames MD5 oder SHA1 zu verwenden. Zum Beispiel, um Hash-Tabellen mit Speicherung von Schlüssel-Wert-Paaren zu erstellen oder um die Prüfsumme beim Übertragen großer Dateien schnell zu überprüfen.
Eine der beliebtesten ist die
xxHash- Familie von Hash-Funktionen, die vor etwa fünf Jahren erschien. Obwohl diese Hashes ursprünglich zur Überprüfung der Prüfsumme während der LZ4-Komprimierung konzipiert wurden, wurden sie für eine Vielzahl von Aufgaben verwendet. Es ist verständlich: Schauen Sie sich einfach die Tabelle oben an, um die Leistung von xxHash und einigen anderen Hash-Funktionen zu vergleichen. In diesem Test übertrifft xxHash seinen Leistungskonkurrenten um die Hälfte. Die neue Version von
XXH3 legt die Messlatte noch höher.
Im Folgenden können Diagramme angeklickt werdenDer Programmautor Yann Collet
schreibt, dass die Idee zur Verbesserung des Algorithmus während der Implementierung des Bloom-Filters entstand, die die schnelle Erzeugung von 64 Pseudozufallsbits basierend auf kleinen Eingabedaten variabler Länge erforderte. Im Prinzip könnte der Standard XXH64 damit umgehen, aber die Verarbeitung kleiner Eingabedaten hatte bei seiner Entwicklung nie Priorität. Mit anderen Worten ist eine Optimierung möglich. Als Ergebnis dieser Optimierung erschien eine neue Hash-Funktion XXH3, in der Ideen aus einigen anderen Hash-Algorithmen implementiert sind. Interessanterweise ist XXH3 erheblich schneller als alle vorhandenen xxHash-Varianten, nicht nur bei kleinen Eingabedaten, sondern in fast allen Anwendungsfällen.
XXH3 beseitigt den Hauptnachteil von XXH64 - Hash-Begrenzung von 64 Bit. Der Autor sagt, dass er aus diesem Grund oft gebeten wurde, mindestens eine 128-Bit-Version zu veröffentlichen. Die XXH3-Hash-Funktion kann also theoretisch Hashes mit bis zu 256 Bit erzeugen.
In XXH3 eine innere Schleife, die durch Vektorisierung optimal behandelt wird. Aus diesem Grund verwendet die Funktion Hardware-Unterstützung für die Befehlssätze SSE2, AVX2 und NEON. Die Leistung hängt vom Compiler ab. Unerwarteterweise ist die von clang kompilierte Version den anderen weit überlegen. Ian Colle dachte sogar, dass die Leistung der Hash-Funktion hier die Speicherbandbreite überschreiten würde. Diese Version in der Grafik entspricht einer gestrichelten Linie.
Als Ergebnis stellte sich heraus, dass die Hash-Funktion mit Unterstützung für AVX2 einen viel höheren Durchsatz als RAM hat, sodass die Cache-Größe zu einem wichtigen Faktor wird. Bei vielen Aufgaben ist es jedoch erforderlich, Daten zu verarbeiten, die sich bereits im Cache befinden. Daher ist es absolut sinnvoll, mit einer Geschwindigkeit zu arbeiten, die schneller als der Speicher ist.
Durch die Unterstützung von SSE2-Anweisungen kann die neue Hash-Funktion XXH32 in 32-Bit-Anwendungen, die in der realen Welt immer noch üblich sind (z. B. WASM-Bytecode), erheblich umgehen.
Bei kleinen Eingabedaten (20 bis 30 Byte) ist die XXH3-Hash-Funktion nicht viel, aber immer noch besser als Googles
CityHash sowie FarmHash, das früher eindeutig führend war.
Die folgende Grafik zeigt die Ergebnisse des realistischsten Tests mit Eingabedaten variabler Länge (Zufallsvariable von 1 bis N).
Ein weiterer Test berücksichtigt die
Verzögerung : Hier beginnt das Hashing mit einem Signal. Die Idee ist, eine reale Arbeitslast zu simulieren, bei der die Hash-Funktion nicht kontinuierlich funktioniert, sondern zu einem bestimmten Zeitpunkt in anderen Prozessen aufgerufen wird.
Der Autor schreibt, dass dieser Test mit einer Multiplikation von 64 × 64 => 128 Bit die
mumv2- Algorithmen von Vladimir Makarov und
t1ha2 von Leo
Yuryev bevorzugt.
Schließlich ist hier das letzte und wichtigste Diagramm, das die Hash-Rate für die Eingabedaten variabler Länge unter Berücksichtigung der Verzögerung zeigt. Es spiegelt die tatsächliche Verwendung der Hash-Funktion beispielsweise in Datenbanken wider.
XXH3 wurde als Teil des
xxHash v0.7.0-Pakets veröffentlicht . Es hat die Markierung "experimentell" und zum Entsperren müssen Sie das Makro
XXH_STATIC_LINKING_ONLY . Der Autor erklärt, dass die Hash-Funktion bisher nur für kurzlebige Testdaten verwendet werden kann, nicht jedoch für die eigentliche Speicherung von Hashes. Entsprechend den Ergebnissen des Versuchszeitraums und der Sammlung von Benutzerkritiken erhält die XXH3-Funktion in der nächsten Version von xxHash einen stabilen Status.
