为什么（a * b！= 0）比Java更快（a！= 0& b！= 0）？ [英] Why is (a*b != 0) faster than (a != 0 && b != 0) in Java?

问题描述

我正在用Java编写一些代码，在某些时候，程序的流程由两个int变量a和b是否为非零来确定（注意：a和b从不否定，并且从不在整数溢出范围内。）

我可以用

 <$来评估它c $ c> if（a！= 0&& b！= 0）{/ *一些代码* /} 
  

或者

  if（a * b！= 0）{/ *一些代码* /} 
  

因为我希望这段代码每次运行数百万次，所以我想知道哪一条会是快点。我通过在一个巨大的随机生成的数组上进行比较来做实验，我也很想知道数组的稀疏性（数据的分数= 0）将如何影响结果：

 很长一段时间; 
 final int len = 50000000; 
 int arbitrary = 0; 
 int [] [] nums = new int [2] [len]; 
 
 for（double fraction = 0; fraction< = 0.9; fraction + = 0.0078125）{
 for（int i = 0; i< 2; i ++）{
 for（int j = 0; j< len; j ++）{
 double random = Math.random（）; 
 
 if（random< fraction）nums [i] [j] = 0; 
 else nums [i] [j] =（int）（random * 15 + 1）; 
} 
} 
 
 time = System.currentTimeMillis（）; 
 
 for（int i = 0; i< len; i ++）{
 if（/ * insert nums [0] [i] * nums [1] [i]！= 0或者nums [0] [i]！= 0&& nums [1] [i]！= 0 * /）任意++; 
} 
 System.out.println（System.currentTimeMillis（） -  time）; 
} 
  

结果显示，如果你期望a或b到等于0％~3％的时间， a * b！= 0 比 a！= 0&& b！= 0 ：

我们确实看到了与预期相同的分支预测效果，有趣的是图形沿X轴略微翻转。

更新

1-我添加了！（a == 0 || b == 0）分析看看会发生什么。

2-我还包括 a！= 0 | | b！= 0 ，（a + b）！= 0 和（a | b）！= 0 出于好奇心，在了解了分支预测之后。但它们在逻辑上并不等同于其他表达式，因为只有 OR b需要非零才能返回true，因此它们并不意味着要比较处理效率。

3-我还添加了用于分析的实际基准，它只是迭代一个任意的int变量。

4-有些人建议包括 a！= 0& b！= 0 而不是 a！= 0&& b！= 0 ，预测它会更接近 a * b！= 0 ，因为我们会删除分支预测效果。我不知道& 可以和布尔变量一起使用，我认为它只用于带整数的二进制运算。

注意：在我考虑所有这些的上下文中，int溢出不是问题，但在一般情况下这绝对是一个重要的考虑因素。

CPU ：英特尔酷睿i7-3610QM @ 2.3GHz

Java版本：1.8.0_45

Java（TM）SE运行时环境（版本1.8.0_45- b14）

Java HotSpot（TM）64位服务器VM（版本25.45-b02，混合模式）

解决方案

我忽略了您的基准可能存在缺陷的问题，并将结果视为面值。

是编译器还是硬件级？

后者，我认为：

  if（a！= 0&& b！= 0）
  

将编译为2个内存加载和两个conditio nal branches

  if（a * b！= 0）
  

将编译为2个内存加载，一个乘法和一个条件分支。

乘法可能更快如果硬件级分支预测无效，则比第二条件分支。当你增加比率......分支预测变得不那么有效了。

条件分支较慢的原因是它们导致指令执行管道停止。分支预测是通过预测分支将走哪条路并且基于此推测性地选择下一条指令来避免失速。如果预测失败，则在加载另一个方向的指令时会有延迟。

（注意：上面的解释过于简单。为了更准确的解释，你需要查看CPU制造商为汇编语言编码器和编译器编写者提供的文献。 Branch Predictors 上的Wikipedia页面是好的背景。）

---

但是，有一件事你需要注意这个优化。是否有任何值 a * b！= 0 会给出错误的答案？考虑计算产品导致整数溢出的情况。

---

更新

您的图表倾向于确认我所说的内容。

• 条件分支中还有分支预测效果 a * b！= 0 大小写，这在图表中显示。




• 如果在X轴上投影超过0.9的曲线，它看起来比如1）他们将在大约1.0和2）相遇会面点将与X = 0.0大致相同的Y值。

---

更新2

我不明白为什么曲线是不同的 a + b！= 0 和 a | b！= 0 个案。在分支预测器逻辑中，可能是聪明的东西。或者它可能表明其他东西。

（请注意，这种东西可能特定于特定的芯片型号甚至版本。您的基准测试结果可能会有所不同在其他系统上。）

然而，它们都具有为 a 的所有非负值工作的优势和 b 。

I'm writing some code in Java where, at some point, the flow of the program is determined by whether two int variables, "a" and "b", are non-zero (note: a and b are never negative, and never within integer overflow range).

I can evaluate it with

if (a != 0 && b != 0) { /* Some code */ }

Or alternatively

if (a*b != 0) { /* Some code */ }

Because I expect that piece of code to run millions of times per run, I was wondering which one would be faster. I did the experiment by comparing them on a huge randomly generated array, and I was also curious to see how the sparsity of the array (fraction of data = 0) would affect the results:

long time;
final int len = 50000000;
int arbitrary = 0;
int[][] nums = new int[2][len];

for (double fraction = 0 ; fraction <= 0.9 ; fraction += 0.0078125) {
    for(int i = 0 ; i < 2 ; i++) {
        for(int j = 0 ; j < len ; j++) {
            double random = Math.random();

            if(random < fraction) nums[i][j] = 0;
            else nums[i][j] = (int) (random*15 + 1);
        }
    }

    time = System.currentTimeMillis();

    for(int i = 0 ; i < len ; i++) {
        if( /*insert nums[0][i]*nums[1][i]!=0 or nums[0][i]!=0 && nums[1][i]!=0*/ ) arbitrary++;
    }
    System.out.println(System.currentTimeMillis() - time);
}

And the results show that if you expect "a" or "b" to be equal to 0 more than ~3% of the time, a*b != 0 is faster than a!=0 && b!=0:

I'm curious to know why. Could anyone shed some light? Is it the compiler or is it at the hardware level?

Edit: Out of curiosity... now that I learned about branch prediction, I was wondering what the analog comparison would show for a OR b is non-zero:

We do see the same effect of branch prediction as expected, interestingly the graph is somewhat flipped along the X-axis.

Update

1- I added !(a==0 || b==0) to the analysis to see what happens.

2- I also included a != 0 || b != 0, (a+b) != 0 and (a|b) != 0 out of curiosity, after learning about branch prediction. But they are not logically equivalent to the other expressions, because only a OR b needs to be non-zero to return true, so they are not meant to be compared for processing efficiency.

3- I also added the actual benchmark that I used for the analysis, which is just iterating an arbitrary int variable.

4- Some people were suggesting to include a != 0 & b != 0 as opposed to a != 0 && b != 0, with the prediction that it would behave more closely to a*b != 0 because we would remove the branch prediction effect. I didn't know that & could be used with boolean variables, I thought it was only used for binary operations with integers.

Note: In the context that I was considering all this, int overflow is not an issue, but that's definitely an important consideration in general contexts.

CPU: Intel Core i7-3610QM @ 2.3GHz

Java version: 1.8.0_45
Java(TM) SE Runtime Environment (build 1.8.0_45-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.45-b02, mixed mode)

解决方案

I'm ignoring the issue that your benchmarking might be flawed, and taking the result at face value.

Is it the compiler or is it at the hardware level?

That latter, I think:

  if (a != 0 && b != 0)

will compile to 2 memory loads and two conditional branches

  if (a * b != 0)

will compile to 2 memory loads, a multiply and one conditional branch.

The multiply is likely to be faster than the second conditional branch if the hardware-level branch prediction is ineffective. As you increase the ratio ... the branch prediction is becoming less effective.

The reason that conditional branches are slower is that they cause the instruction execution pipeline to stall. Branch prediction is about avoiding the stall by predicting which way the branch is going to go and speculatively choosing the next instruction based on that. If the prediction fails, there is a delay while the instruction for the other direction is loaded.

(Note: the above explanation is oversimplified. For a more accurate explanation, you need to look at the literature provided by the CPU manufacturer for assembly language coders and compiler writers. The Wikipedia page on Branch Predictors is good background.)

---

However, there is one thing that you need to be careful about with this optimization. Are there any values where a * b != 0 will give the wrong answer? Consider cases where computing the product results in integer overflow.

---

UPDATE

Your graphs tend to confirm what I said.

• There is also a "branch prediction" effect in the conditional branch a * b != 0 case, and this comes out in the graphs.

• If you project the curves beyond 0.9 on the X-axis, it looks like 1) they will meet at about 1.0 and 2) the meeting point will be at roughly the same Y value as for X = 0.0.

---

UPDATE 2

I don't understand why the curves are different for the a + b != 0 and the a | b != 0 cases. There could be something clever in the branch predictors logic. Or it could indicate something else.

(Note that this kind of thing can be specific to a particular chip model number or even version. The results of your benchmarks could be different on other systems.)

However, they both have the advantage of working for all non-negative values of a and b.

这篇关于为什么（a * b！= 0）比Java更快（a！= 0& b！= 0）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！