delphi - Delphi 2009 最高效的 Unicode 哈希函数

Question

我需要 Delphi 2009 中最快的哈希函数，该函数将从 Unicode 字符串创建哈希值，该值将相当随机地分布到存储桶中。

我最初是从 Gabr 开始的来自 GpStringHash 的 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

这似乎比 Gabr 的代码包含更多的汇编代码。

速度至关重要。我可以做些什么来改进我编写的 pascal 代码或我的代码生成的汇编程序吗？

<小时/>

后续。

我最终选择了基于SysUtils.HashNameMBCS的HashOf函数。它似乎为 Unicode 字符串提供了良好的哈希分布，并且速度似乎相当快。

是的，生成了很多汇编代码，但是生成它的 Delphi 代码非常简单，并且仅使用位移操作，因此很难相信它不会很快。

Answer 1

ASM 输出并不能很好地指示算法速度。另外，据我所知，这两段代码正在执行几乎相同的工作。最大的区别似乎是内存访问策略，第一个是使用左滚而不是等效的指令集(shl | shr - 大多数高级编程语言都省略了“滚动”运算符)。后者的管道可能比前者更好。

ASM 优化是黑魔法，有时更多的指令比更少的指令执行得更快。

当然，对两者进行基准测试并选出获胜者。如果您喜欢第二个的输出，但第一个更快，请将第二个的值插入第一个。

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

请注意，不同的机器将以不同的方式运行代码，因此如果速度确实至关重要，那么请在您计划运行最终应用程序的硬件上进行基准测试。我敢打赌，超过兆字节的数据，差异将是几毫秒——这远远小于操作系统从您那里夺走的时间。

<小时/>PS。我不相信这个算法会创建均匀分布，这是您明确指出的(您运行过直方图吗？)。您可以查看移植 this hash function到德尔福。它可能不如上面的算法那么快，但它看起来相当快并且也提供了良好的分布。同样，我们讨论的可能是兆字节数据的毫秒级差异。