Effizienteste Unicode-Hash-Funktion für Delphi 2009

Question

Ich benötige die schnellste Hash-Funktion in Delphi 2009, die Hashwerte aus einer Unicode-Zeichenfolge erzeugt, die ziemlich zufällig in Buckets verteilt wird.

ich ursprünglich mit Gabr ‚s HashOf Funktion von GpStringHash gestartet:

function HashOf(const key: string): cardinal; 
asm 
    xor edx,edx  { result := 0 } 
    and eax,eax  { test if 0 } 
    jz @End   { skip if nil } 
    mov ecx,[eax-4] { ecx := string length } 
    jecxz @End  { skip if length = 0 } 
@loop:   { repeat } 
    rol edx,2  { edx := (edx shl 2) or (edx shr 30)... } 
    xor dl,[eax] { ... xor Ord(key[eax]) } 
    inc eax   { inc(eax) } 
    loop @loop  { until ecx = 0 } 
@End: 
    mov eax,edx  { result := eax } 
end; { HashOf } 

Aber ich fand, dass dies nicht gute Zahlen von Unicode-Strings erzeugte. Ich stellte fest, dass Gabr Routinen nicht zu Delphi aktualisiert 2009.

Dann entdeckte ich HashNameMBCS in SysUtils von Delphi 2009 und übersetzt es auf diese einfache Funktion (wobei „string“ ist ein Delphi 2009 Unicode-String):

function HashOf(const key: string): cardinal; 
var 
    I: integer; 
begin 
    Result := 0; 
    for I := 1 to length(key) do 
    begin 
    Result := (Result shl 5) or (Result shr 27); 
    Result := Result xor Cardinal(key[I]); 
    end; 
end; { HashOf } 

ich dachte, das war ziemlich gut, bis ich an der CPU-Fenster und sah den Code Assembler es erzeugt:

Process.pas.1649: Result := 0; 
0048DEA8 33DB    xor ebx,ebx 
Process.pas.1650: for I := 1 to length(key) do begin 
0048DEAA 8BC6    mov eax,esi 
0048DEAC E89734F7FF  call $00401348 
0048DEB1 85C0    test eax,eax 
0048DEB3 7E1C    jle $0048ded1 
0048DEB5 BA01000000  mov edx,$00000001 
Process.pas.1651: Result := (Result shl 5) or (Result shr 27); 
0048DEBA 8BCB    mov ecx,ebx 
0048DEBC C1E105   shl ecx,$05 
0048DEBF C1EB1B   shr ebx,$1b 
0048DEC2 0BCB    or ecx,ebx 
0048DEC4 8BD9    mov ebx,ecx 
Process.pas.1652: Result := Result xor Cardinal(key[I]); 
0048DEC6 0FB74C56FE  movzx ecx,[esi+edx*2-$02] 
0048DECB 33D9    xor ebx,ecx 
Process.pas.1653: end; 
0048DECD 42    inc edx 
Process.pas.1650: for I := 1 to length(key) do begin 
0048DECE 48    dec eax 
0048DECF 75E9    jnz $0048deba 
Process.pas.1654: end; { HashOf } 
0048DED1 8BC3    mov eax,ebx 

Dies scheint als Code des Gabr ziemlich viel mehr Assembler-Code zu enthalten.

Geschwindigkeit ist von entscheidender Bedeutung. Kann ich irgendetwas tun, um den von mir geschriebenen Pascal-Code oder den Assembler, den mein Code generiert hat, zu verbessern?

---

Follow-up.

Ich ging schließlich mit der HashOf-Funktion basierend auf SysUtils.HashNameMBCS. Es scheint eine gute Hashverteilung für Unicode-Strings zu geben und scheint ziemlich schnell zu sein.

Ja, es wird eine Menge Assembler-Code generiert, aber der Delphi-Code, der ihn erzeugt, ist so einfach und verwendet nur Bit-Shift-Operationen, daher ist es schwer zu glauben, dass es nicht schnell gehen würde.

Answer 1

Der ASM-Ausgang ist kein guter Indikator für die Geschwindigkeit des Algorithmus. Von dem, was ich sehen kann, machen die beiden Teile des Codes fast die gleiche Arbeit. Der größte Unterschied scheint die Speicherzugriffsstrategie zu sein, und die erste ist das Verwenden von Roll-Links anstelle der äquivalenten Menge von Anweisungen (shl | shr - die meisten höheren Programmiersprachen lassen die "Roll" -Operatoren weg). Letzteres kann besser pipettieren als das erste.

ASM-Optimierung ist schwarze Magie und manchmal mehr Anweisungen ausführen schneller als weniger.

Um sicher zu sein, Benchmark beide und wählen Sie den Gewinner. Wenn Sie die Ausgabe der Sekunde mögen, aber die erste ist schneller, verstopfen Sie die Werte der Sekunde in die erste.

rol edx,5 { edx := (edx shl 5) or (edx shr 27)... } 

Beachten Sie, dass verschiedene Maschinen wird der Code auf verschiedene Weise ausgeführt werden, so dass, wenn es wirklich auf Schnelligkeit des Wesens ist dann Benchmark es auf der Hardware, die Sie auf die endgültige Anwendung ausführen möchten. Ich bin bereit zu wetten, dass über Megabytes von Daten die Differenz eine Angelegenheit von Millisekunden sein wird - die weit weniger ist, als das Betriebssystem von Ihnen nimmt.

---

PS. Ich bin nicht davon überzeugt, dass dieser Algorithmus eine gleichmäßige Verteilung erzeugt, etwas, das Sie explizit aufgerufen haben (haben Sie die Histogramme ausgeführt?). Sie können die Übertragung von this hash function nach Delphi betrachten.Es ist vielleicht nicht so schnell wie der obige Algorithmus, aber es scheint ziemlich schnell zu sein und gibt auch eine gute Verteilung. Auch hier sprechen wir wahrscheinlich in der Größenordnung von Millisekunden Differenz über Megabytes an Daten.

Answer 2

Es gab ein paar Diskussionen im Delphi/BASM-Forum, die für Sie von Interesse sein könnten. Werfen Sie einen Blick auf die folgenden:

http://forums.embarcadero.com/thread.jspa?threadID=13902&tstart=0

Answer 3

Wir hielten vor einiger Zeit einen netten kleinen Wettbewerb, auf einer Hash-Verbesserung als „MurmurHash“; Wikipedia zitieren:

Es ist für seine außergewöhnlich schnell bemerkt, oft zwei- bis viermal schneller als vergleichbare Algorithmen wie FNV, Jenkins' lookup3 und SuperFastHash des Hsieh, mit ausgezeichneten Verteilung, Lawinenverhalten und Gesamtkollisionsfestigkeit.

Sie können die Einsendungen für diesen Wettbewerb herunterladen here.

Eine Sache, die wir gelernt haben, war, dass manchmal Optimierungen Ergebnisse auf jeder CPU nicht verbessern. Mein Beitrag wurde optimiert, um gut auf AMD zu laufen, hat aber bei Intel nicht so gut abgeschnitten. Umgekehrt ist es auch umgekehrt (Intel Optimierungen laufen bei AMD suboptimal).

Also, wie Talljoe sagte: Messen Sie Ihre Optimierungen, da sie für Ihre Leistung schädlich sein könnten!

Als Randbemerkung: Ich stimme Lee nicht zu; Delphi ist ein netter Compiler und alles, aber manchmal sehe ich, dass es Code erzeugt, der einfach nicht optimal ist (selbst wenn das Kompilieren mit allen Optimierungen aktiviert ist). Zum Beispiel sehe ich regelmäßig, dass es Register löscht, die zuvor nur zwei oder drei Anweisungen gelöscht hatten. Oder EAX wird in EBX gelegt, nur um es zu verschieben und wieder in EAX zu legen. Diese Art von Ding. Ich rate nur hier, aber Hand-Optimierung dieser Art von Code wird sicherlich in engen Orten helfen.

Vor allem aber; Analysieren Sie zunächst Ihren Engpass und prüfen Sie, ob ein besserer Algorithmus oder eine bessere Datenstruktur verwendet werden kann. Versuchen Sie dann, den Pascal-Code zu optimieren (z. B. Speicherzuweisungen verringern, Referenzzählung vermeiden, Finalisierung, Versuch/Schluss, Versuch/Ausnahme von Blöcken usw.). und dann, nur als letztes Mittel, den Assembler-Code zu optimieren.

Answer 4

Ich habe zwei Assembly "optimierte" Funktionen in Delphi geschrieben, oder mehr bekannte schnelle Hash-Algorithmen in fein abgestimmten Pascal und Borland Assembler implementiert. Die erste war eine Implementierung von SuperFastHash, und die zweite war eine MurmurHash2-Implementierung, ausgelöst durch eine Anfrage von Tommi Prami auf meinem Blog, meine C# -Version in eine Pascal-Implementierung zu übersetzen. Dies führte zu einer discussion continued on the Embarcadero Discussion BASM Forums, die am Ende zu etwa 20 Implementierungen führte (siehe latest benchmark suite), die letztendlich zeigten, dass es aufgrund der großen Unterschiede in den Zykluszeiten pro Befehl zwischen Intel und AMD schwierig sein würde, die beste Implementierung auszuwählen.

Also, versuchen Sie eine von denen, aber denken Sie daran, die schnellste Zeit jedes Mal zu bekommen würde wahrscheinlich bedeuten, den Algorithmus zu einem einfacheren zu ändern, der Ihrer Distribution schaden würde. Die Feinabstimmung einer Implementierung erfordert viel Zeit und eine bessere Validierungs- und Benchmarking-Suite, um die Implementierung zu überprüfen.