在Delphi 2009中,我需要最快的哈希函数,它将从Unicode字符串中创建散列值,该字符串将相当随机地分配到存储桶中.
我最初从GpStringHash开始使用Gabr的HashOf功能:
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 }
但是我发现这没有从Unicode字符串产生好的数字.我注意到Gabr的例程没有更新到Delphi 2009.
然后,我在Delphi 2009的SysUtils中发现了HashNameMBCS,并将其转换为这个简单的函数(“string”是Delphi 2009 Unicode字符串):
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 }
我认为这是非常好的,直到我看着cpu窗口,并看到它生成的汇编代码:
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
速度是至关重要的.有没有什么可以做的,以改善我写的pascal代码或我的代码生成的汇编程序?
跟进.
我终于用了基于SysUtils.HashNameMBCS的HashOf函数.似乎为Unicode字符串提供了一个很好的散列分布,似乎相当快.
是的,有很多汇编代码生成,但是生成它的Delphi代码是如此简单,只使用位移操作,所以很难相信它不会很快.
@H_403_26@解决方法
ASM输出不是算法速度的良好指示.另外,从我可以看到,这两个代码正在做几乎相同的工作.最大的区别似乎是存储器访问策略,第一个是使用左转而不是等效的指令集(shl | shr – 大多数更高级的编程语言忽略“滚动”操作符).后者可能比前者更好.
ASM优化是黑魔法,有时更多的指令执行速度要比较少.
可以肯定的是,两者都是基准的,并且选择赢家.如果您喜欢第二个输出,但第一个更快,请将第二个值插入第一个.
rol edx,5 { edx := (edx shl 5) or (edx shr 27)... }
请注意,不同的机器将以不同的方式运行代码,所以如果速度是真正的本质,那么在您计划运行最终应用程序的硬件上进行基准测试.我愿意打赌超过兆字节的数据,差异将是毫秒数 – 这远远小于操作系统从你身上带走.
PS.我不相信这个算法创建均匀的分布,你明确地调用了(你运行直方图吗?).你可以看看将this hash function移植到Delphi.它可能不如上面的算法那么快,但是看起来相当快,也给出了很好的分布.再次,我们可能会说的是毫秒数毫秒的差异超过兆字节的数据.
@H_403_26@ @H_403_26@