关于无分支二分搜索

Question

我问了一个关于减少未命中预测的问题。

Jerry Coffin 给了我一个令人印象深刻的答案。

关于减少分支未命中预测

二分搜索是无分支的，但是当我在我的集​​合交集算法中使用它时，我发现它比原始二分搜索慢得多。什么原因？

更新：

我使用以下事件来测试 i7 处理器的分支未命中预测数：BR_MISS_PRED_RETIRED。我发现无分支版本比原始版本少了大约一半的分支缺失。

对于缓存未命中：我使用 LLC_MISSES 来测试最后一级缓存未命中的次数，也是一半。

但时间是原来的2.5倍左右。

Answer 1

条件移动（无分支）搜索的问题发生在数组很大并且内存访问时间相对于分支预测错误很大时。

条件移动搜索类似于：

int needle; // value we are searching for
int *base = ...; // base pointer
int n; // number of elements in the current region
while (n > 1) {
  int middle = n/2;
  base += (needle < *base[middle]) ? 0 : middle;
  n -= middle;
}

请注意，我们有条件地更新base而不使用分支（至少假设编译器不决定将三元运算符实现为分支）。问题是base每次迭代中的值都依赖于前一次迭代中的比较结果，因此一次访问一次内存，通过数据依赖进行序列化。

对于大型数组的搜索，这消除了内存级并行的可能性，并且您的搜索需要类似log2(N) * average_access_time. 基于分支的搜索没有这样的数据依赖：它在迭代之间只有一个推测的控制依赖：CPU 选择一个方向并跟随它。如果猜对了，您将同时加载当前迭代和下一次迭代的结果！它并没有就此结束：猜测还在继续，您可能同时有十几个货物在飞行。

当然，CPU 并不总是猜对的！在最坏的情况下，如果分支完全不可预测（您的数据和针值没有偏差），一半的时间都会出错。尽管如此，这意味着平均而言，0.5 + 0.25 + 0.125 + ... = ~1除了当前的访问权限之外，它还将在飞行中维持额外的访问权限。这不仅仅是理论上的：尝试对随机数据进行二分搜索，您可能会看到基于分支的搜索比无分支搜索的速度提高了 2 倍，这是由于并行性加倍。

对于许多数据集，分支方向并非完全随机，因此您可以看到超过 2 倍的加速，就像您的情况一样。

对于适合缓存的小型阵列，情况正好相反。无分支搜索仍然存在同样的“串行依赖”问题，但加载延迟很小：几个周期。另一方面，基于分支的搜索会遭受持续的错误预测，其成本约为 20 个周期，因此在这种情况下，无分支搜索通常会更快。

Answer 2

然后使用原来的二分搜索。对随机位置的数组访问并不比分支未命中好多少，特别是因为在这种情况下编译器无法使用变量的寄存器。