C++：在范围内获取整数的最快方法

Question

C++：在范围内获取整数的最快方法

6

我需要为大约N=1亿个键生成哈希键。从我的研究来看，Murmur3（MurmurHash3_x86_32，请参见murmur3 hash）似乎是最快的哈希函数，具有最佳的延迟和足够小的碰撞率。我面临的问题是该函数将密钥返回为void *。更具体地说，模板如下： void MurmurHash3_x86_32 (const void *key, int len, uint32_t seed, void *out); 由于我的哈希表大小将小于它可以生成的最大哈希值，因此我需要将其放入表范围[0，N-1]内。最简单的解决方案似乎是使用%运算符。但是，由于已知它是一个慢速运算符，我想知道是否有更快的方法来解决这个问题。

我找到了一条有趣的建议，来自于StackOverflow，与C/C++中使用模（%）运算符有关。它建议使用“2的幂次方，以下代码可以实现（假设使用二进制补码表示）”：

return i & (n-1);

我的问题是，在新的CPU上，由于多路高速缓存，当大小接近2^n时，性能有时会下降（或者说大部分情况下都会下降），这个我记得。这个链接提供了一个关于插入的说明Big Memory, Part 3.5: Google sparsehash!。

目前，murmur3的优势似乎被硬件相关问题和已知的%运算符的低效率所抵消。由于性能是一个约束条件，即使不是MurmurHash3_x86_32，我也要求满足我的需求的低延迟和更快的解决方案。

- Quiescent

不要因为它速度慢就避免使用“%”运算符，如果你试图将一个128位的数字放入任意大小的空间中，那么你很难做得更好。另外，你能否给出一个关于2^n性能退化的更好的例子？ - Guvante

你实际上检查（分析）过“%”的成本与murmur3哈希的成本相比是否很高吗？ - Mark B

我认为你误解了“大内存，第3.5部分”中的性能下降。这是由于表的对数增长造成的。如果你预先分配整个表，就不会出现这种情况。 - Daniel

请参阅http://igoro.com/archive/gallery-of-processor-cache-effects/comment-page-2/，了解与缓存相关的观察细节。我没有进行基准测试，将%的性能视为已知。 - Quiescent

与计算一次哈希值进行操作的成本相比，一个“%”操作的性能微不足道。 - John Bollinger

同意，这听起来更像是内存分配问题，而不是逻辑运算符的价格。 - Jens Munk

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John Bollinger · Accepted Answer

我面临的问题是函数返回键作为void *。

事实并非如此。它不返回任何内容（void）。哈希结果通过您指定的缓冲区（指针）记录在最后一个参数中。对于MurmurHash3_x86_32()，最好将其指向uint32_t的指针。

因为我的哈希表大小比它可以生成的最大哈希值要小，所以我需要将它放入表范围[0,N-1]。最简单的解决方案似乎是使用%运算符。但正如人们所知道的那样，它是一种缓慢的运算符，我想知道是否有更快的方法来解决这个问题。

%不仅是最简单的解决方案，也是最常见的解决方案。 "慢"是相对的- %比+慢，但比调用MurmurHash3_x86_32()快得多。

我发现一个有趣的建议[...]建议[使用2的幂表大小，并通过&操作符计算模数]

请注意，与SO答案中的断言相反，实际上这与二进制补码表示没有任何依赖关系。

我对此的问题是，在新CPU上，由于多路缓存线，性能有时（或大多数情况下？）会在大小为2^n周围降低，如果我记得正确，(这个链接提供了关于插入Big Memory, Part 3.5: Google sparsehash!的说明)。

您所链接的报告中描述的性能下降归因于重新哈希，这似乎是非常合理的。这与你所问的操作无关。可以想象，缓存（不）关联可能会影响大型哈希表的性能，但通常不会比使用大型哈希表产生更大的影响。使用哈希表固有的内存访问模式自然会产生较差的缓存局部性。那几乎是重点。

目前，Murmur3的优势似乎已被硬件相关问题和已知的%运算符的低效问题所抵消。由于性能是一种限制条件，即使它不是MurmurHash3_x86_32，我也要求满足我的需求的低延迟和更快速的解决方案。

你对此过于深思熟虑了。使用大型哈希表只是为了获得有效的CPU缓存而付出的代价。它与哈希函数没有关联（只要哈希函数工作良好）。单个算术操作的成本，无论是%还是&，与计算哈希操作的成本相比几乎不会引起注意，因此选择哪种方式并不重要。如果您想为该操作获得微小的优势，则使用2的幂次方大小的表和&运算符。另一方面，这会放弃您费尽心思计算的一些哈希位。相反，考虑选择一个质数哈希表大小和%运算符--然后所有哈希位都将有助于桶选择，这可能提高您的分布效果。