Technik zur automatisierten Suche nach Integer-Hash-Funktionen

 (github.com/skeeto)
3 Punkte von GN⁺ 2024-05-06 | 1 Kommentare | Auf WhatsApp teilen
  • Hash Function Prospector ist ein Tool, das Integer-Hash-Funktionen in großer Zahl zufällig erzeugt, JIT-kompiliert, ihr Avalanche-Verhalten bewertet und anschließend die derzeit beste Funktion in C-Syntax ausgibt.
  • Für die Bewertung wird der Avalanche-Score verwendet, also die durchschnittliche Zahl der Ausgabebits, die beim Kippen eines einzelnen Eingabebits unverändert bleiben; je niedriger, desto besser, und der ideale Wert ist 0.
  • Ziel der Suche sind 32-Bit- und 64-Bit-Integer-Hash-Funktionen; wegen des JIT-Compilers läuft das Tool selbst nur auf x86-64, die gefundenen Funktionen können aber auch in anderen Umgebungen verwendet werden.
  • Die wichtigsten gefundenen Funktionen verwenden eine xorshift-multiply-xorshift-Struktur; das 2-Runden-lowbias32 zeigt mit kleinem Abstand geringere Bias als der 32-Bit-Finalizer von MurmurHash3, und das 3-Runden-triple32 liegt nahe an der theoretischen Bias-Grenze.
  • Eine exakte Bias-Messung kann für 32-Bit-Funktionen mit -E und -e durchgeführt werden; für 16-Bit-Hashes ist das separate Tool hp16 zuständig, wobei die Regeln zur Integer-Promotion in C beachtet werden müssen.

Die Rolle von Hash Function Prospector

  • Hash Function Prospector ist ein Tool zur automatisierten Entdeckung von Integer-Hash-Funktionen.
  • Es erzeugt zufällig Milliarden von Integer-Hash-Funktionen, JIT-kompiliert sie und bewertet dann ihr Avalanche-Verhalten.
  • Unter den erzeugten Funktionen wird die aktuell beste Funktion in C-Syntax ausgegeben.
  • Verlinkt ist außerdem der zugehörige Artikel Prospecting for Hash Functions.

Bewertungskriterien und unterstützter Umfang

  • Der Avalanche-Score ist die durchschnittliche Zahl der Ausgabebits, die beim Kippen eines einzelnen Eingabebits unverändert bleiben.
    • Je niedriger der Wert, desto besser.
    • Idealerweise kippt jedes Ausgabebit mit einer Wahrscheinlichkeit von 50 %, sodass der Score 0 beträgt.
  • Prospector kann 32-Bit- und 64-Bit-Integer-Hash-Funktionen erzeugen.
  • Alle Optionen sind in der Hilfe über -h zu finden.
  • Wegen des JIT-Compilers wird das Tool selbst nur auf x86-64 unterstützt.
    • Die gefundenen Hash-Funktionen können jedoch überall verwendet werden.

Reversible Operationen für die Suche

  • Der Generator setzt Funktionen zufällig aus 9 ausgewählten reversiblen Operationen zusammen.
  • Die Liste der Operationen lautet wie folgt:
    • x = ~x
    • x ^= constant
    • x *= constant | 1
    • x += constant
    • x ^= x >> constant
    • x ^= x << constant
    • x += x << constant
    • x -= x << constant
    • x <<<= constant
    • x = bswap(x)
  • Technisch gesehen lässt sich x = ~x auch als x ^= constant ausdrücken, aber die Wahrscheinlichkeit, dass der Generator diese XOR-Konstante zufällig auswählt, ist gering, daher wird es als eigene Operation behandelt.

Entdeckte 32-Bit-Hash-Funktionen

  • 2-Runden-Funktionen

    • Eine der nützlichen gefundenen Funktionsfamilien ist die 2-Runden-xorshift-multiply-xorshift-Struktur.
    • TheIronBorn fand mithilfe kombinatorischer Optimierung die bekannten optimalen Parameter für diese Struktur; das Ergebnis ist [16 21f0aaad 15 d35a2d97 15] = 0.10760229515479501.
    • lowbias32 ist eine 32-Bit-2-Runden-Permutation mit niedriger Bias und zeigt mit sehr kleinem Abstand eine geringere Bias als der 32-Bit-Finalizer von MurmurHash3.
    • Die exakte Bias von lowbias32 beträgt 0.17353355999581582.
    • Die Struktur wurde von Prospector gefunden, die Parameter wurden mit Hill Climbing und genetischen Algorithmen abgestimmt.
    • Die Umkehrfunktion lowbias32_r wird ebenfalls bereitgestellt.
    • prospector32 ist eine Funktion, die ausschließlich mit Prospector gefunden wurde.
    • Die exakte Bias beträgt 0.34968228323361017.
    • Sie hat eine höhere Bias als das zuvor genannte lowbias32.
    • Um alternative Multiplikationskonstanten per Zufallssuche zu finden, wird das Muster wie folgt angegeben:
    • ./prospector -p xorr:15,mul,xorr:12,mul,xorr:15

  • 3-Runden-Funktionen

    • Fügt man derselben Struktur eine weitere multiply-xorshift-Runde hinzu, kann man mit sorgfältig gewählten Parametern die theoretische Bias-Grenze erreichen.
    • triple32 hat eine exakte Bias von 0.020888578919738908.
    • Laut README ist es nicht von einer perfekten PRF zu unterscheiden, also einer zufälligen Permutation über alle 32-Bit-Integer.
    • Die Umkehrfunktion triple32_r wird ebenfalls bereitgestellt.
    • Die Liste der 3-Runden-Konstanten enthält Ergebnisse mit niedriger Bias von 0.020888578919738908 bis etwa 0.022984943828687553.
    • triple32inc, bei dem vor triple32 eine Inkrement-Operation eingefügt wird, beseitigt das Problem hash(0) = 0 und senkt die Bias noch leicht weiter.
    • Die exakte Bias beträgt 0.020829410544597495.
    • Die Umkehrfunktion triple32inc_r führt am Ende x-- aus.

Exakte Bias-Messung

  • Im Modus -E wird die Bias einer gegebenen Hash-Funktion bewertet.
  • Standardmäßig verwendet Prospector für eine schnelle Bias-Bewertung einen Schätzwert.
    • Diese Schätzung ist nicht deterministisch und enthält viel Rauschen.
  • Um die exakte Bias per vollständiger Enumeration zu messen, wird die Option -e verwendet.
  • Die zu prüfende Funktion kann auf zwei Arten definiert werden:
    • mit -p und einem Muster
    • mit -l und einer Shared Library, die eine hash()-Funktion enthält
  • Mit der Shared-Library-Methode lassen sich auch Hash-Funktionen testen, die sich mit der eingeschränkten Funktionsdarstellung von Prospector nicht ausdrücken lassen.
  • Standardmäßig wird die Eingabe als 32-Bit-Hash-Funktion behandelt.
  • Der Schalter -8 testet 64-Bit-Funktionen mit der Schätzmethode.
    • Für 64-Bit-Hash-Funktionen gibt es keinen exakten erschöpfenden Test, weil dieser zu viel Zeit benötigen würde.

hp16 für 16-Bit-Hashes

  • Für 16-Bit-Hashes gelten andere Einschränkungen, daher gibt es das separate Tool hp16.
  • Im Gegensatz zu den 32-Bit-/64-Bit-Versionen von Prospector ist hp16 vollständig portabel und kann auf nahezu jedem System ausgeführt werden.
  • hp16 kann auch 128KiB s-boxes erzeugen und bewerten.
  • Da 16-Bit-Hashes auf Maschinen ohne schnelle Multiplikationsinstruktionen benötigt werden können, gibt es Optionen, bestimmte Operationen bei der Suche auszulassen.
    • -m
    • -r

16-Bit-Ergebnisse und Hinweise zur C-Implementierung

  • Beispiele für bisherige 16-Bit-Ergebnisse sind:
    • 2-Runden-xorshift-multiply hash16_xm2: Bias 0.0085905051336723701
    • 3-Runden-xorshift-multiply hash16_xm3: Bias 0.0045976709018820602
    • ohne Multiplikation hash16_s6: Bias 0.023840118344741465
  • Es wird darauf hingewiesen, dass hash16_s6 ohne Multiplikation einer bestimmten xorshift-multiply-Form entspricht.
  • Ein guter 3-Runden-xorshift-Hash, der kurz mit hp16 -Xn3 gesucht wurde, ist eine gute Näherung an eine gute s-box aus hp16 -S.
  • Beim Schreiben von 16-Bit-Operationen in C müssen die Regeln zur Integer-Promotion beachtet werden.
    • Zum Beispiel kann in einer 32-Bit-Implementierung ein vorzeichenloser 16-Bit-Operand zu einem vorzeichenbehafteten 32-Bit-Integer promotet werden.
    • In diesem Fall kann es unter bestimmten Umständen zu falschen Ergebnissen kommen.
    • Der von diesem Programm ausgegebene C-Code achtet darauf, 16-Bit-Operationen an den nötigen Stellen zu unsigned int zu promoten.

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-05-06
Hacker-News-Meinungen

  • Ich kenne ihn persönlich nicht, aber ich mag seinen Code.
    Besonders gefallen mir die JSON-Bibliothek https://github.com/skeeto/pdjson, die Bibliotheken fürs Optionen-Parsing https://github.com/skeeto/optparse und https://github.com/skeeto/getopt, der branchless UTF-8 decoder https://github.com/skeeto/branchless-utf8, der lockfreie Stack https://github.com/skeeto/lstack und die Trie-Bibliothek https://github.com/skeeto/trie.
    Mir gefällt auch seine Lizenzpräferenz, dass all diese Projekte unter The Unlicense veröffentlicht werden.

    • Skeeto ist legendär. Für mich spielt er in derselben Liga wie Fabrice Bellard.
      Ich folge ihm seit Jahren auf GitHub, und er veröffentlicht immer wieder kleine, skurrile Nischen-Tools. Branchless UTF-8 ist zum Beispiel bekannt.
    • Er ist auch der Autor von elfeed https://github.com/skeeto/elfeed, „An Emacs web feeds client“. Von dessen minimalistischer Implementierung habe ich viel Inspiration bekommen.

  • Hallo, ich bin derjenige, der MurmurHash erstellt hat. Das ist eine interessante Arbeit, und es ist spannend zu sehen, wie gut sich der Multiply-Shift-XOR-Ansatz so lange gehalten hat.

    • XOR-Shift gleicht zwei Schwächen der Multiplikation aus: Bei den hohen Bits gibt es keine Bits darüber, die Einfluss nehmen können, und bei den niedrigen Bits gibt es keine Bits darunter, von denen sie beeinflusst werden könnten.
    • Wie MurmurHash scheinen auch diese als nicht-kryptografische Hashes gedacht zu sein.
      Allerdings scheint bei der Avalanche- und Bias-Idee einiges zu fehlen. Die am Ende aufgeführte Funktion triple32 hat zum Beispiel einen exakten Bias von 0.020888578919738908; wenn FabriceNeyret2 sie in ShaderToy implementiert, entsteht dieses Bild: https://www.shadertoy.com/view/WttXWX oder https://i.imgur.com/qU2P5rx.png.
      Wenn man jedoch eine einfache Gradientenableitung einer Normal Map durchführt, sieht man ziemlich viele auffällige „Kristall“-Linien. Für solche Gratstrukturen gibt es vermutlich einen technischen Begriff: https://i.imgur.com/IHWT1GM.png
      Nebenbei: Ich vermute, diese ganze Idee ist schon etwa fünf Jahre alt: https://nullprogram.com/blog/2018/07/31/

  • Wegen meiner Erfahrung mit der Entwicklung guter Hash-Funktionen habe ich oft über die Idee einer automatischen Hash-Suche nachgedacht.
    Es ist schön, so eine Arbeit zu sehen. Es wäre gut, die Ausgabe automatisch zu bewerten, indem man sie mit SMHasher3 verbindet, einer deutlich verbesserten und schnelleren Variante der alten Hash-Test-Suite von Frank J. T. Wojcik. Für mehr Geschwindigkeit könnte man nur einen Teil der Tests nutzen und früh fehlschlagen.
    Eine Erweiterung auf 64-Bit- und 128-Bit-Hashes wäre ebenfalls gut, aber natürlich wird der Suchraum dann größer. In diesem Zusammenhang habe ich auch einmal NodeJS-Code geschrieben, der bei Multiplikationen mit 64-Bit-Primzahlen die Avalanche misst, um Werte für Rain auszuwählen.
    [Rain]: https://github.com/dosyago/rain
    [SMHasher3]: https://gitlab.com/fwojcik/smhasher3

  • Es wäre interessant, das auf Operationen zu verallgemeinern, die in der RISC-V-Bitmanipulation-Erweiterung verfügbar sind. Vielleicht findet man dadurch starke Funktionen, die später nutzbar sind, wenn diese Instruktionen weiter verbreitet sind.
    Carry-less Multiplication könnte die Menge der reversiblen Operationen ebenfalls erweitern und ist auf mancher vorhandener Hardware schnell. CRC ist in gewisser Weise ebenfalls verwandt, aber auf einer größeren Menge von Hardware verfügbar und sollte eine echte Teilmenge dessen sein, was CLMUL finden kann.
    Da bei vielen Anwendungen von Hashes nur die niederwertigsten oder höchstwertigen Bits des Hashwerts relevant sind, wäre es auch interessant, den Bias in den höchsten/niedrigsten Bitbereichen oder die Reste bei Division durch verschiedene Zahlen zu bewerten. Eine Funktion, die bezogen auf die gesamte Ausgabe unverzerrt wirkt, kann bei Metriken, die nicht die gesamte Ausgabe betrachten, oder bei nicht gleichverteilten Eingaben wie ASCII-Text besser oder schlechter abschneiden.

  • Kann jemand erklären, warum das cool ist und wofür man es verwendet?

    • Es scheint ein Tool zu sein, das Befehlssequenzen zum Erstellen von Hash-Funktionen erzeugt und bewertet, wie gut diese Hash-Funktion ist.
      Als Zielmetrik scheint zu gelten, ob sich möglichst viele Ausgabe-Bits möglichst zufällig ändern, wenn sich ein einzelnes Eingabe-Bit ändert. Es gibt den C-Code der besten erzeugten Hash-Funktion aus.
      Nützlich ist das also, wenn man eine Hash-Funktion braucht und meint, dass bestehende Funktionen nicht gut genug sind, oder wenn man Hash-Funktionen erforscht und neue Strukturideen benötigt. Schon die Codegenerierung an sich ist cool, und Zufall einzusetzen ist der erste Schritt hin zu noch cooleren genetischen Programmierung. Außerdem scheinen Menschen seit etwa 15 Jahren Freude daran zu haben, Computer CPU-Zyklen verbrennen zu lassen, um Hashes zu berechnen, die größtenteils nie genutzt werden.
    • Solche Funktionen sind für Hash-Tabellen unverzichtbar. Verwandte Bezeichnungen sind Hash-Map und Hash-Set.
      Hash-Tabellen sind eine hervorragende Datenstruktur, mit der sich viele Algorithmen einfach und effizient implementieren lassen. Diese Effizienz hängt davon ab, ob man aus Daten einen kleinen, zum Beispiel 32- oder 64-Bit großen, nahezu eindeutigen Hash erzeugen kann.
      Wenn man zum Beispiel Benutzernamen hasht und nur den ASCII-Code des ersten Buchstabens verwendet, werden viele Benutzernamen auf dieselbe Zahl abgebildet, was schlecht funktioniert. Das nennt man eine Kollision, und bei vielen Kollisionen wird eine Hash-Tabelle sehr ineffizient.
      Besser ist es, Bits aus dem gesamten Benutzernamen zu nehmen und sie irgendwie zu vermischen, sodass throwaway_1237 und throwaway_12373 unterschiedliche Zahlen ergeben. Die Hash-Funktion übernimmt dieses Mapping, und die Avalanche-Eigenschaft beschreibt, wie gut sie Kollisionen vermeidet.
      In der Praxis gibt es meist einen Kompromiss zwischen der Geschwindigkeit einer Hash-Funktion und ihrer Fähigkeit, Kollisionen zu vermeiden. Hash-Funktionen von Weltklasse sehen ziemlich seltsam aus: Multiplikationen mit merkwürdigen Konstanten, XORs, Shifts und dergleichen. Für Menschen ist es sehr schwer, bei solchen undurchsichtigen Funktionen die Performance abzuschätzen.
      Dieser Code probiert zufällig viele Hash-Funktionen aus und lässt sie gegeneinander antreten. Wenn das gelingt, kann er die reale Performance zentraler Datenstrukturen verbessern, die in vielen Sprachen und Bibliotheken verwendet werden – und das ist cool.
    • Da es sich um Hash-Funktionen für Integer handelt, kann man sie verwenden, wenn man in Sets oder Maps einen schnellen Integer-Hash braucht. Wenn die Funktionen ausreichend unterschiedlich auseinanderlaufen, liefern sie auch schnelle Hashes für Bloom-Filter.

  • Vor ein paar Wochen habe ich 1brc in Go implementiert: https://github.com/infogulch/1brc-go. Dieses Repository hat mich dazu inspiriert, eine maßgeschneiderte perfekte Hash-Funktion zu suchen, bei der jede Messstation ohne Kollision in ihrem eigenen Bucket landet.
    Dann habe ich die Regel gesehen, dass man die Hash-Funktion vor dem Programmstart nicht an die Daten anpassen darf, und die Idee verworfen.
    Ich habe eine Testvorrichtung gebaut, die beliebige Konstanten, Startwerte, Multiplikationskonstanten, Shift-/Rotationsbeträge usw. prüft und die bisher besten Konstanten nach Anzahl der Kollisions-Buckets und Kollisionen ausgibt. Bei einer Auslastung von etwa 40 % habe ich es, glaube ich, so weit reduziert, dass nur in einem einzigen Bucket zwei Werte kollidierten. Interessanterweise enthielten die leistungsstärksten Konstanten unabhängig von anderen Konstanten ähnliche Shift-Positionen, sodass ich diese Werte am Ende hart codiert habe.

  • Es wäre wirklich interessant, wenn man einen eigenen Eingabedaten-Generator einbauen könnte. In der Praxis hat man oft keine zufälligen Binärdaten, sondern auf irgendeine Weise strukturierte Daten, und genau diese Struktur könnte vielleicht sehr gute Hash-Funktionen ermöglichen.

  • Sich auf reversible Operationen zu beschränken hat mathematische Vorteile, schließt aber gleichzeitig vieles aus.
    Als ich etwas Ähnliches gemacht habe, dachte ich an perfektes Hashing, bei dem die Eingabemenge im Voraus bekannt ist. Der übliche Ansatz verwendet ein Array von Konstanten, aber ich wollte sehen, ob man das stärker komprimieren kann, besonders wenn die Eingaben ohnehin kleine Integer sind. Natürlich geht das mit etwas wie hash -= hash >> gap_index.
    Also habe ich wohl eine Liste von ungefähr 100 primitiven Operationen ausprobiert. Manche davon überschneiden sich, waren aber als getrennte Konzepte nützlich. Dann wurde mir langweilig, und ich habe aus dem Projekt nichts gemacht.

    • Was genau sind die „mathematischen Vorteile, wenn man sich auf reversible Operationen beschränkt“, und warum sind reversible Operationen in diesem Kontext wünschenswert?

  • Ich bin mir nicht sicher, was genau das macht. Sucht es nach dem Allzeit-Bestwert? Falls nicht, frage ich mich, warum sich der Bestwert bei jedem Lauf ändert.
    Außerdem frage ich mich, ob jemand einen Mechanismus kennt, um eine gute Hash-Funktion zu finden, wenn man weiß, dass nur Integerwerte in einem bestimmten Bereich vorkommen, zum Beispiel zwischen 10.000 und 200.000, und man diese Werte auf eine optimale Anzahl von Hash-Buckets verteilen möchte.

    • Es probiert Werte zufällig aus, um unter den in diesem Lauf getesteten Werten den besten zu finden.
      Es ist praktisch unmöglich, in einem einzigen Lauf den gesamten Suchraum zu durchlaufen und das absolute Optimum zu finden, und weil auch die Reihenfolge der Versuche zufällig ist, können die Werte von Lauf zu Lauf variieren.
      Wenn man einfach einen „guten“ Hash braucht, ist es fast immer am besten, eine allgemeine Hash-Funktion zu verwenden. Wenn die Zahlen extrem groß sind und der Bereich sehr klein ist, kann man einen Offset anwenden, sodass der Minimalwert wieder bei 0 liegt, und dann einen kleineren, schnelleren Hash verwenden. Wenn man die „perfekte Wahl“ für einen exakten Bereich finden will, kommt so ein zufälliger Ansatz dem wohl am nächsten; man müsste die Tests dann so ändern, dass sie auf diesem Intervall laufen.

  • Ich frage mich, ob die Verwendung derselben Konstante für zwei Multiplikationen die Codegröße reduziert und die Berechnung dadurch vielleicht auch etwas schneller macht.
    Ich habe auch die StackOverflow-Antwort aktualisiert: https://stackoverflow.com/questions/664014/what-integer-hash...