più efficiente Funzione Unicode hash per Delphi 2009

Question

ho bisogno della funzione di hash più veloce possibile in Delphi 2009 che creerà valori hash da una stringa Unicode che distribuirà abbastanza casualmente in secchi.

Originariamente ho iniziato con la funzione HashOf Gabr s' dal GpStringHash:

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 } 

ma ho scoperto che questo non ha prodotto buoni numeri da stringhe Unicode. Ho notato che le routine di Gabr non sono stati aggiornati a Delphi 2009.

Poi ho scoperto HashNameMBCS in SysUtils di Delphi 2009 e tradotto a questa semplice funzione (dove "stringa" è un Unicode stringa di Delphi 2009):

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 } 

ho pensato che questo era abbastanza buono fino a quando ho guardato la finestra di CPU e ho visto il codice assembler ha generato:

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 

questo sembra contenere un bel più codice assembler po 'di codice di Gabr.

La velocità è l'essenza. C'è qualcosa che posso fare per migliorare il codice Pascal che ho scritto o l'assemblatore che il mio codice ha generato?

---

follow-up.

ho finalmente andato con la funzione HashOf sulla base di SysUtils.HashNameMBCS. Sembra dare una buona distribuzione hash per le stringhe Unicode, e sembra essere abbastanza veloce.

Sì, c'è un sacco di codice assembler generato, ma il codice Delphi che genera è così semplice e utilizza solo le operazioni di bit turni, quindi è difficile credere che non sarebbe stato veloce.

Answer 1

uscita ASM non è una buona indicazione della velocità algoritmo. Inoltre, da quello che posso vedere, i due pezzi di codice stanno facendo quasi il lavoro identico. La differenza più grande sembra essere la strategia di accesso alla memoria e il primo sta usando roll-sinistra invece del set equivalente di istruzioni (SHL | SHR - la maggior parte dei linguaggi di programmazione di alto livello lasciare fuori gli operatori "Roll"). Quest'ultimo può pipeline meglio del primo.

ottimizzazione ASM è la magia nera e talvolta più istruzioni vengono eseguite più velocemente di meno.

A dire il vero, punto di riferimento sia e scegliere il vincitore. Se ti piace l'output del secondo ma il primo è più veloce, inserisci i valori del secondo nel primo.

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

Si noti che diverse macchine verrà eseguito il codice in modo diverso, quindi se la velocità è davvero essenziale, allora punto di riferimento è l'hardware che si prevede di eseguire l'applicazione finale su. Sono disposto a scommettere che oltre megabyte di dati la differenza sarà una questione di millisecondi - che è molto meno di quanto il sistema operativo stia portando via da te.

---

PS. Non sono convinto che questo algoritmo crei una distribuzione uniforme, qualcosa che hai esplicitamente chiamato (hai eseguito gli istogrammi?). Si può guardare il porting this hash function a Delphi.Potrebbe non essere veloce come l'algoritmo di cui sopra, ma sembra essere abbastanza veloce e dà anche una buona distribuzione. Di nuovo, probabilmente stiamo parlando dell'ordine di millisecondi di differenza su megabyte di dati.

Answer 2

C'è stato un po 'di discussione nel forum Delphi/BASM che potrebbe interessarti. Date un'occhiata al seguente:

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

Answer 3

abbiamo tenuto un bel piccolo concorso un po 'indietro, migliorando su un hash chiamato "MurmurHash"; Comportante Wikipedia:

È noto per essere eccezionalmente veloce, spesso due a quattro volte più veloce di algoritmi comparabili come FNV, lookup3 Jenkins' e Hsieh SuperFastHash, con eccellente distribuzione, comportamento valanghe e resistenza complessiva alle collisioni.

È possibile scaricare gli invii per tale concorso here.

Una cosa che abbiamo imparato è che a volte le ottimizzazioni non migliorano i risultati su ogni CPU. Il mio contributo è stato ottimizzato per funzionare bene su AMD, ma non è andato bene per Intel. È accaduto anche il contrario (ottimizzazioni Intel in esecuzione non ottimale su AMD).

Quindi, come disse Talljoe: misura le tue ottimizzazioni, in quanto potrebbero essere dannose per la tua performance!

Come nota a margine: non sono d'accordo con Lee; Delphi è un bel compilatore e tutto, ma a volte vedo che genera codice che non è ottimale (anche quando si compila con tutte le ottimizzazioni attivate). Ad esempio, vedo regolarmente i registri di cancellazione che erano già stati cancellati solo due o tre dichiarazioni precedenti. O EAX è messo in EBX, solo per averlo spostato e rimesso in EAX. Questo genere di cose. Sto solo indovinando qui, ma l'ottimizzazione manuale di quel tipo di codice ti aiuterà sicuramente in punti ristretti.

Soprattutto; Analizza innanzitutto il collo di bottiglia, quindi verifica se è possibile utilizzare un algoritmo o una struttura dati migliore, quindi cerca di ottimizzare il codice pascal (ad esempio: riduci le allocazioni di memoria, evita il conteggio dei riferimenti, la finalizzazione, try/finally, try/except blocks, ecc), e quindi, solo come ultima risorsa, ottimizza il codice assembly.

Answer 4

Ho scritto due funzioni "ottimizzate" di assemblaggio in Delphi, o più algoritmi di hash veloci implementati noti sia in Pascal sia in Borland Assembler. Il primo era un'implementazione di SuperFastHash e la seconda era un'implementazione MurmurHash2 attivata da una richiesta di Tommi Prami sul mio blog per tradurre la mia versione C# in un'implementazione pascal. Questo ha generato uno discussion continued on the Embarcadero Discussion BASM Forums, che alla fine ha portato a circa 20 implementazioni (controllare lo latest benchmark suite) che alla fine ha mostrato che sarebbe stato difficile selezionare l'implementazione migliore a causa delle grandi differenze nei tempi di ciclo per istruzione tra Intel e AMD.

Quindi, prova uno di questi, ma ricorda che ottenere il più veloce ogni volta probabilmente significherebbe cambiare l'algoritmo in uno più semplice che danneggerebbe la tua distribuzione. La messa a punto di un'implementazione richiede molto tempo e consente di creare una buona suite di validazione e benchmarking per verificare le implementazioni.