- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我问了一个关于减少未命中预测的问题。
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/
我使用 Git 有一段时间了,但尽管在博客和教程上花了很多时间,但我仍然无法理解某些功能...:) 我正在与其他人合作一个项目,我的老板为此在 bitBucket 上创建了一个存储库。 我在本地克隆了
有时我会遇到以下问题: 在功能分支中添加一些提交。 从上游更新 master。 想要查看功能分支和 master 之间的差异,但是 git diff master 显示了在 master 中添加/删除
我使用的是 Gerrit 2.4.2 版。我有一个分支 master,我创建了一个名为 newbranch 的新分支。然后我将一些更改推送到远程(Gerrit 的)newbranch。在 Gerrit
假设我们有一个远程存储库并在本地克隆它。 我们 checkout master 分支,所以现在我们有本地 master 和一个 Remote remotes/origin/master . 然后我必须
我有一个项目,其中开发分支使用 CocoaPods,但其中一位开发人员决定删除它并改用 Carthage。 feature 分支使用的是 CocoaPods,因为它是在 develop 分支转换之前一
我有一个有问题的 master 分支需要调试。为此,我想插入一堆调试程序(例如,打印变量),查明错误并应用修复程序。稍后,我想将修复 merge 到 master 分支中,但我不想跳过调试更改。 #
我有一个 master 分支,我正在其中 push 我的最新开发。 现在在某个时候,我确实从 master 分支发布并创建了名为 release1 的新分支。 现在我在master分支上做新的开发 与
我正在尝试使我的一些标准工作流程自动化,我发现自己经常做的一件事是将对远程 master 分支的更改 merge 到我自己的本地分支并推送结果。 所以步骤如下: 转为大师 从远程 pull 更改 切换
使用 Gerrit 很容易意外地将开发分支中的不稳定代码 merge 到稳定分支中: $ git checkout develop $ commit $ git push origin HEAD:re
我有一个正在进行的项目,我正在雇用承包商来帮助我处理代码的某些部分。问题是我不想让任何一个承包商看到所有这些。 我可以在 GitHub 上为他们分配私有(private)存储库下的分支吗?这需要命令行
SVN 分支 Branch 选项会给开发者创建出另外一条线路。当有人希望开发进程分开成两条不同的线路时,这个选项会非常有用。我们先假设你已经发布了一个产品的 1.0 版本,你可能想创建一个新的分支,
关闭。这个问题是opinion-based .它目前不接受答案。 想改进这个问题?更新问题,以便 editing this post 提供事实和引用来回答它. 2年前关闭。 Improve this
有没有办法从特定的修订版中创建(svn)分支, 因为我想跳过提交历史中的一些修订(在新分支中)。 例如,我有从 1 到 1590 的修订,我想创建一个新分支并跳过提交(从 1504 到 1574 )和
到目前为止我看到的所有 svn 分支的例子都是这样的 svn cp -m 'Making test branch' svn://svnrepo/hellosite svn://svnrepo/hell
当我尝试使用 Sonar 扫描仪分析我的项目时,扫描失败并显示以下错误消息: Caused by: Branch does not exist on server: develop 显然,这只发生在它
在我的 Mercurial 存储库中,不知何故,有人输入了空白分支名称: 如果我hg id -r 2004,我确实得到空白文本。现在的问题是,这会导致我们的Redmine安装出现问题,因为它无法同步存
我有以下代码片段: srcaddr >= inet_ntoa . fromJust dstaddr >= inet_ntoa . fromJust -- I want to perform actio
在我的项目中,我有用于工作的本地分支和网络驱动器上的分支我在本地一号和网络一号之间做了“绑定(bind)分支”我的想法是使用绑定(bind)选项自动备份每个本地提交。 我在本地分支提交文件后,我在网络
我想创建一个脚本,根据变量的状态使用不同的表和命令执行不同的操作。在 T-SQL 中,我会这样做: DECLARE @whatToDo INT = 1; IF @whatToDo = 1 BEGIN
Write a program that reads input up to # and reports the number of times that the sequence ei occurs
我是一名优秀的程序员,十分优秀!