4

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

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

关于减少分支未命中预测

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

更新：

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

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

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

4

4 回答 4

5

当数组很大并且内存访问时间相对于分支错误预测很大时，就会出现条件移动（无分支）搜索的问题。

条件移动搜索类似于：

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 个周期，因此在这种情况下，无分支通常会更快结束。

于 2019-01-20T03:06:10.567 回答
1

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

像这样的紧密循环中的分支预测通常没有效果，因为处理器有多个流水线。在评估分支测试时，两个代码路径都已被解码和评估。只保留一条路径的结果 - 但通常不会有来自分支的管道停顿。

另一方面，写入内存可能会产生影响。通常您正在写入 CPU 上的内存缓存，但 MMU 必须保持缓存线与系统的其余部分同步缓存未命中并使 CPU 重新加载内存缓存。

于 2012-07-06T11:46:01.983 回答
1

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

将内存需求增加两倍实际上可以加快搜索速度，这似乎非常违反直觉，但显然更早开始获取弥补了额外的内存命中。

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

于 2015-11-09T02:52:40.350 回答
0

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

于 2012-07-06T11:11:18.713 回答