java - 为什么 (a*b != 0) 在 Java 中比 (a != 0 && b != 0) 快？

Question

我正在用 Java 编写一些代码，在某些时候，程序的流程取决于两个 int 变量“a”和“b”是否非零(注意:a 和 b 永远不会负数，并且永远不会在整数溢出范围内)。

我可以评估它

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

或者

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

因为我预计这段代码每次运行会运行数百万次，所以我想知道哪一个会更快。我通过在一个巨大的随机生成的数组上比较它们来进行实验，我也很想知道数组的稀疏性(数据的分数 = 0)会如何影响结果:

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);
}

而且结果表明，如果您期望“a”或“b”在大约 3% 的时间内等于 0，则 a*b != 0 比 更快>a!=0 && b!=0:

我很想知道为什么。任何人都可以解释一下吗？是编译器还是硬件级别的？

编辑: 出于好奇...... 现在我了解了分支预测，我想知道模拟比较对于 OR b 非零:

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

更新

1- 我在分析中添加了 !(a==0 || b==0) 以查看会发生什么。

2- 我还包括了 a != 0 || b != 0, (a+b) != 0 和 (a|b) != 0 出于好奇，在学习了分支预测之后。但是它们在逻辑上并不等同于其他表达式，因为只有a OR b 需要非零才能返回true，所以它们不打算用于比较处理效率。

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

4- 有人建议在预测中包含 a != 0 & b != 0 而不是 a != 0 && b != 0它会表现得更接近于 a*b != 0 因为我们会移除分支预测效应。我不知道 & 可以与 boolean 变量一起使用，我以为它只用于整数的二进制操作。

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

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

Java 版本:1.8.0_45
Java(TM) SE 运行时环境 (build 1.8.0_45-b14)
Java HotSpot(TM) 64 位服务器 VM(内部版本 25.45-b02，混合模式)

Answer 1

我忽略了您的基准测试可能存在缺陷的问题，并从表面上看结果。

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

我认为后者:

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

将编译为 2 个内存负载和两个条件分支

  if (a * b != 0)

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

如果硬件级分支预测无效，则乘法可能比第二个条件分支更快。随着比率的增加……分支预测的效果越来越差。

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

(注意:上面的解释过于简单化了。要更准确的解释，你需要查看CPU制造商为汇编语言编码器和编译器编写器提供的文献。维基百科页面Branch Predictors是很好的背景。)

---

但是，在进行此优化时，您需要注意一件事。是否存在 a * b != 0 会给出错误答案的值？考虑计算乘积导致整数溢出的情况。

---

更新

您的图表倾向于证实我所说的。

• 在条件分支 a * b != 0 的情况下还有一个“分支预测”效应，这在图中可以看出。

• 如果你在 X 轴上投影超过 0.9 的曲线，看起来 1) 它们将在大约 1.0 处相交，并且 2) 相交点的 Y 值将与 X = 0.0 大致相同。

---

更新 2

我不明白为什么 a + b != 0 和 a | 的曲线不同。 b != 0 个案例。在分支预测器逻辑中可能有一些巧妙之处。或者它可能表明其他东西。

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

但是，它们都具有适用于 a 和 b 的所有非负值的优点。