Most Efficient Unicode Hash Function for Delphi 2009
assembly, delphi, delphi-2009, hash, unicode
Solution
ASM output is not a good indication of algorithm speed. Also, from what I can see, the two pieces of code are doing almost the identical work. The biggest difference seem to be the memory access strategy and the first is using roll-left instead of the equivalent set of instructions (shl | shr -- most higher-level programming languages leave out the "roll" operators). The latter may pipeline better than the former.
ASM optimization is black magic and sometimes more instructions execute faster than fewer.
To be sure, benchmark both and pick the winner. If you like the output of the second but the first is faster, plug the second's values into the first.
rol edx,5 { edx := (edx shl 5) or (edx shr 27)... }
Note that different machines will run the code in different ways, so if speed is REALLY of the essence then benchmark it on the hardware that you plan to run the final application on. I'm willing to bet that over megabytes of data the difference will be a matter of milliseconds -- which is far less than the operating system is taking away from you.
PS. I'm not convinced this algorithm creates even distribution, something you explicitly called out (have you run the histograms?). You may look at porting this hash function to Delphi. It may not be as fast as the above algorithm but it appears to be quite fast and also gives good distribution. Again, we're probably talking on the order of milliseconds of difference over megabytes of data.
Problem
I am in need of the fastest hash function possible in Delphi 2009 that will create hashed values from a Unicode string that will distribute fairly randomly into buckets. I originally started with Gabr's HashOf function from 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 } ``` But I found that this did not produce good numbers from Unicode strings. I noted that Gabr's routines have not been updated to Delphi 2009. Then I discovered HashNameMBCS in SysUtils of Delphi 2009 and translated it to this simple function (where "string" is a 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 } ``` I thought this was pretty good until I looked at the CPU window and saw the assembler code it generated: ``` 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 ``` This seems to contain quite a bit more assembler code than Gabr's code. Speed is of the essence. Is there anything I can do to improve either the pascal code I wrote or the assembler that my code generated? Followup. I finally went with the HashOf function based on SysUtils.HashNameMBCS. It seems to give a good hash distribution for Unicode strings, and appears to be quite fast. Yes, there is a lot of assembler code generated, but the Delphi code that generates it is so simple and uses only bit-shift operations, so it's hard to believe it wouldn't be fast.