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

Question

我需要生成大约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].最简单的解决方案似乎是使用%运算符.但由于众所周知这是一个缓慢的操作员,我想知道是否有更快的方法来解决问题.

我发现一个有趣的建议是否有替代在C/C++中使用%(模数)？在StackOverflow本身.它暗示了"两个人的力量,以下作品(假设两个补语表示)":

return i & (n-1);

我的问题是,在较新的CPU上,它有时(或者大部分时间都是这样？),由于多路缓存线,性能会在大约2 ^ n,IIRC附近降低.(此链接提供有关插入大内存的说明,第3.5部分:Google sparsehash!).

目前,murmur3的优势似乎因硬件相关问题和%运营商的低效率而无效.由于性能是一个约束,我要求低延迟和更快的解决方案,即使它不是MurmurHash3_x86_32.

Answer 1

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

它不是。它不返回任何内容 ( void)。哈希结果记录在您通过最后一个参数指定的缓冲区（指向的指针）中。因为MurmurHash3_x86_32()，将其作为指向 a 的指针是最有意义的uint32_t。

由于我的哈希表大小小于它可以生成的最大哈希值，因此我需要将其放入表范围 [0, N-1] 中。最简单的解决方案似乎是使用 % 运算符。但由于众所周知它是一个缓慢的操作符，我想知道是否有更快的方法来解决这个问题。

这%不仅是最简单的解决方案，而且是最常用的解决方案。“慢”是相对的——%比调用 慢得多+，但比调用快得多MurmurHash3_x86_32()。

我发现的一个有趣的建议[...]建议[使用二次方表大小，并通过运算符计算模数&]

请注意，与 SO 答案中的断言相反，事实上这根本不依赖于二进制的补码表示。

我的问题是，在较新的 CPU 上，有时（或者大多数情况下？），由于多路缓存行，性能会在 2^n，IIRC 大小左右下降。（此链接提供了有关插入大内存的说明，第 3.5 部分：Google稀疏哈希！）。

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

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

这件事你想太多了。无法有效利用 CPU 缓存只是使用大型哈希表所付出的代价。它与哈希函数无关（只要哈希函数能够很好地完成其工作）。与计算操作 的哈希值的成本相比，单个算术运算的成本（无论是%或&）并不明显，因此您选择哪一个并不重要。如果您希望该操作有一点点优势，那么请使用二次幂大小的表和运算符。另一方面，这会丢弃一些您费尽心思计算的哈希位。考虑选择一个质数哈希表大小和运算符——然后所有哈希位都将有助于存储桶选择，这可能会提高您的分布。&%