关于无分支的二进制搜索

Question

我问了一个关于减少预测失误的问题。

曾傑瑞咖啡给了我一个令人印象深刻的答案。

About reducing the branch miss prediciton

二进制搜索是无分支的，但是当我在集合交集算法中使用它时，我发现它比原来的二进制搜索要慢得多。理由是什么呢？

更新：

我使用以下事件测试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额外的访问飞行超过目前的一个。这不仅仅是理论上的:尝试对随机数据进行二进制搜索，您可能会看到基于分支的搜索在无分支搜索上的2x加速比，这是由于并行性的翻倍。

对于许多数据集，分支方向并不完全是随机的，所以您可以看到超过2倍的加速比，就像在您的例子中一样。

对于适合高速缓存的小数组，情况正好相反。无分支搜索仍然存在同样的“串行依赖”问题，但是加载延迟很小:几个周期。另一方面，基于分支的搜索经常出现错误预测，这需要花费大约20周的时间，因此在这种情况下，无分支搜索的速度通常更快。

Answer 2

因为那个版本正在做大量的装载和存储。

这样的紧循环中的分支预测通常没有效果，因为处理器有多个管道。在评估分支测试时，已经对这两个代码路径进行了解码和评估。只保留一条路径的结果--但通常不存在分支的管道失速。

另一方面，写到记忆中也会产生影响。通常您正在写入CPU上的内存缓存，但是如果数组很大，并且访问它的顺序基本上是随机的，则MMU必须保持缓存线与系统其他部分的同步，这样就会丢失常量缓存并使CPU重新加载内存缓存。

Answer 3

不久前，我看到了一种有趣的方法，可能也是关于堆栈溢出的，它是关于避免数据获取成本的。有人以这样的方式编写了二进制搜索，他们将数组视为隐式树，并预取左子和右子。这是在将当前元素与测试值进行比较之前完成的。

增加两倍的内存需求确实可以加快搜索速度，这似乎是非常违背直觉的，但显然，提前开始抓取可以弥补额外的内存不足。

如果我没记错的话，一半的读取实际上是不依赖的，因为没有使用这些值。它可以通过投机预取负载、非依赖负载或普通负载来完成，在这些加载中，获取的一个值在循环时被移动到保存当前元素的寄存器中。