c++ - 使用 CPU 缓存行击败二进制搜索

出于教育目的，我正在尝试使用 CPU 缓存行击败二进制搜索。

如果你取消注释#define EXIT_ONLY，搜索就像普通的二分搜索，除非元素很少，搜索变成线性搜索.

正如预期的那样，这比二进制搜索执行得更快。

但是我想改进 future ，所以如果您评论 #define EXIT_ONLY，那么将进行“小型”线性搜索，而不是仅访问“中间”元素。

理论上，线性搜索的值必须在 CPU 缓存行中，并且访问必须“免费”。

然而在实践中，这种搜索比普通的二进制搜索慢得多。

如果我将 CACHE_COUNT_2 硬编码为等于 1，则速度相当，但仍然较慢。

请注意，我从未尝试在 _linear() 中展开 for 循环。

执行速度较慢的原因是什么？

包含所有文件的 repo 协议(protocol)在这里:
https://github.com/nmmmnu/beating_binsearch

最佳答案

您的代码中存在一些问题。例如，此代码不考虑缓存行边界。

while (end - start > CACHE_COUNT_MIN){
//  uint64_t mid = start + ((end - start) /  2);
uint64_t mid = start + ((end - start) >> 1);

等...

char cmp = _linear(mid - CACHE_COUNT_2, mid + CACHE_COUNT_2, data, key, mid);

缓存行分配在以行大小为模的地址上。因此，要扫描整个缓存行，您需要屏蔽掉地址的相关位。即使它是缓存命中，您仍然会花费周期访问该行(在层次结构中越高，它越多)。

二分搜索已经是基于比较的搜索中缓存效率更高的算法之一，尽管因此通过缓存感知来改进它可能很困难。您在每次迭代中消除了一半的搜索空间，这已经避免了大多数缓存未命中，并且它是一个线性空间，并且您增加了每次搜索的局部性。预测甚至可以隐藏一些失误。

您可能想使用 perf对代码中的性能事件进行采样。此外，要了解有时如何使用缓存感知来优化算法，您可能还想看看一些现有的感知缓存，例如 hopscotch hashing。 .

关于c++ - 使用 CPU 缓存行击败二进制搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32328270/