gpt4 book ai didi

algorithm - 关于无分支二分查找

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:52:46 24 4
gpt4 key购买 nike

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

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

About reducing the branch miss prediciton

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

更新:

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

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

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

最佳答案

条件移动(无分支)搜索的问题发生在 then 数组很大且内存访问时间相对于分支预测错误而言较长时。

条件移动搜索类似于:

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

关于algorithm - 关于无分支二分查找,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11360831/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com