Delphi 2009中最有效的Unicode哈希函数

Question

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

我最初是从加布尔的HashOf函数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 }

但我发现这并不能从Unicode字符串中产生很好的数字。我注意到Gabr的例程还没有更新到Delphi 2009。

然后，我在Delphi2009的HashNameMBCS中发现了它，并将它翻译成这个简单的函数(其中"string“是Delphi2009Unicode字符串)：

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代码或者我的代码生成的汇编程序吗？

后续行动。

最后，我使用了基于HashOf的SysUtils.HashNameMBCS函数。它似乎为Unicode字符串提供了一个很好的散列分布，并且看起来相当快。

是的，生成了很多汇编程序代码，但是生成它的Delphi代码非常简单，只使用位移位操作，所以很难相信它不会很快。

Answer 1

ASM输出不能很好地反映算法的速度。而且，据我所见，这两段代码所做的工作几乎是相同的。最大的区别似乎是内存访问策略，第一个是使用左滚指令而不是等效的指令集(shl \ shr -最高级的编程语言忽略了"roll“操作符)。后者的管道可能比前者更好。

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

可以肯定的是，两者都是基准，并选出赢家。如果您喜欢第二个的输出，但是第一个更快，请将第二个值插入第一个值。

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

请注意，不同的机器将以不同的方式运行代码，因此如果速度非常重要，那么在您计划运行最终应用程序的硬件上对其进行基准测试。我敢打赌，在兆字节的数据上，差别将是毫秒的问题--这比操作系统从你身上夺走的要少很多。

PS。我不相信这个算法会创建均匀的分布，这是您显式调用的内容(您运行了直方图吗？)您可以考虑将这个散列函数移植到Delphi。它可能不像上述算法那么快，但它看起来相当快，也给出了很好的分布。再说一遍，我们讨论的可能是毫秒与兆字节之间的差异。

Answer 2

一段时间前，我们举行了一次不错的小竞赛，改进了一个名为“MurmurHash”的散列，引用了维基百科的话：

它的速度非常快，通常比类似的算法(如FNV、Jenkins‘s lookup3和谢家华的SuperFastHash )快两到四倍，具有出色的分布、雪崩性能和整体抗碰撞性能。

你可以下载比赛的参赛作品这里。

我们学到的一件事是，有时优化并不能提高每个CPU的结果。我的贡献被调整为运行良好的AMD，但表现不太好的英特尔.反过来也发生了(英特尔优化运行次优在AMD上)。

因此，正如Talljoe所说:度量您的优化，因为它们实际上可能会损害您的性能！

顺便提一句:我不同意Lee的观点；Delphi是一个很好的编译器，但有时我看到它生成的代码不是最优的(即使在打开所有优化的情况下也是如此)。例如，我经常看到已经清除了两三条语句的寄存器。或者，EAX被放入EBX，但却被转移到EAX中。这类事。我只是在这里猜测，但是手工优化这类代码肯定会在一些困难的地方有所帮助。

不过，首先要分析瓶颈，然后看看是否可以使用更好的算法或数据结构，然后尝试优化pascal代码(例如:减少内存分配、避免引用计数、终结、尝试/最后、尝试/除块等)，然后，仅作为最后手段，优化组装代码。

Answer 3

我在Delphi中编写了两个程序集“优化”函数，或者在微调的Pascal和Borland汇编程序中实现了更多已知的快速哈希算法。第一个是SuperFastHash的实现，第二个是由Tommi在我的博客上请求将我的c#版本转换为Pascal实现而触发的一个MurmurHash2实现。这产生了一个继续讨论Embarcadero讨论会BASM论坛，最终导致了大约20个实现(检查最新基准套件)，这最终表明，由于英特尔和AMD之间每条指令的循环时间有很大的差异，很难选择最佳的实现。

所以，尝试其中之一，但是记住，每次获得最快的速度可能意味着将算法更改为一个更简单的算法，这会损害您的分发。微调实现需要花费大量的时间，并且更好地创建一个好的验证和基准测试套件来检查您的实现。