- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
引用this问题,答案指定未排序的数组需要更多时间,因为它未通过分支预测测试。但是如果我们对程序做一个小改动:
import java.util.Arrays;
import java.util.Random;
public class Main{
public static void main(String[] args) {
// Generate data
int arraySize = 32768;
int data[] = new int[arraySize];
Random rnd = new Random(0);
for (int c = 0; c < arraySize; ++c) {
data[c] = rnd.nextInt() % 256;
}
// !!! With this, the next loop runs faster
Arrays.sort(data);
// Test
long start = System.nanoTime();
long sum = 0;
for (int i = 0; i < 100000; ++i) {
// Primary loop
for (int c = 0; c < arraySize; ++c) {
if (data[c] >= 128) {
sum = data[c];
}
}
}
System.out.println((System.nanoTime() - start) / 1000000000.0);
System.out.println("sum = " + sum);
}
}
这里我已经替换了(来自原始问题)
if (data[c] >= 128)
sum += data[c];
与
if (data[c] >= 128)
sum = data[c];
未排序的数组给出了大约。同样的结果,我想问一下为什么分支预测在这种情况下不起作用?
最佳答案
这个我用jmh分析过。这是我的代码:
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@BenchmarkMode(Mode.AverageTime)
@Warmup(iterations = 2, time = 1)
@Measurement(iterations = 3, time = 1)
@State(Scope.Thread)
@Fork(2)
public class Comparison
{
static final int SIZE = 1<<15;
final int[] data = new int[SIZE];
@Setup
public void setup() {
int i = 1;
for (int c = 0; c < SIZE; ++c) data[c] = (i*=611953);
for (int c = 0; c < SIZE; ++c) data[c] = data[c] >= 128? 128 : 127;
}
@GenerateMicroBenchmark
public long sum() {
long sum = 0;
for (int c = 0; c < SIZE; ++c) if (data[c] >= 128) sum += data[c];
return sum;
}
}
请注意,我既不使用排序也不使用随机数生成;它们是不必要的并发症。使用上面代码中使用的公式:
data[c] = (i*=611953);
我得到 132 微秒的运行时间。如果我注释掉涉及
的行data[c] = data[c] >= 128? 128 : 127;
时间没有变化。这消除了所有算术考虑并专注于分支预测。如果我使用
data[c] = 127;
我得到 13 微秒,如果我使用
data[c] = 128;
我得到 16 微秒。这是“基本情况”,强调不断分支决策之间的差异。
我的结论:这肯定是低级分支预测的效果。
现在让我们分析一下您的干预。如果我使用上面代码中提供的公式,但更改
if (data[c] >= 128) sum += data[c];
到
if (data[c] >= 128) sum = data[c];
然后时间确实从 132 µs 下降到 27 µs。
这是我对下降的解释的猜测:JIT 编译器可以做的优化技巧是反转循环的方向。现在你的代码变成了
for (int c = SIZE-1; c <= 0; --c) if (data[c] >= 128) { sum = data[c]; break; }
循环已短路至达到与原始循环相同的结果所需的最少迭代次数。
我加了这个
data[SIZE-1] = 128;
到 setup()
方法的末尾,但它并没有改变时间。这似乎会使“循环反转”猜想的天真版本无效。
cmovl
在分析程序集时我发现了这一点:
cmp edx, 0x80
cmovl eax, ebx
cmovl
是一条条件移动指令,它将执行发生在then
分支中的赋值效果,但不涉及任何跳转,因此消除了与分支预测失败相关的任何惩罚。这很好的解释了实际效果。
关于java - 分支预测不起作用?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21432400/
我使用 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
我是一名优秀的程序员,十分优秀!