为什么 Java 中的 (a*b != 0) 比 (a != 0 && b != 0) 快?

我正在用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”等于0的时间超过〜3%,则比:a*b != 0a!=0 && b!=0

Graphical graph of the results of a AND b non-zero

我很想知道为什么。谁能透露一些光明?是编译器还是在硬件级别?

编辑:出于好奇......现在我了解了分支预测,我想知道模拟比较会显示什么,因为OR b是非零:

Graph of a or b non-zero

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

更新

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

2-我也包括,出于好奇,在了解了分支预测之后。但它们在逻辑上并不等价于其他表达式,因为只有 OR b 需要为非零才能返回 true,因此不应比较它们的处理效率。a != 0 || b != 0(a+b) != 0(a|b) != 0

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

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

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

中央处理器: 英特尔酷睿 i7-3610QM @ 2.3GHz

Java 版本: 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)


答案 1

我忽略了你的基准测试可能有缺陷的问题,并把结果看得面。

是编译器还是在硬件级别?

我认为后者:

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

将编译为 2 个内存加载和 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 != 0a | b != 0

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

但是,它们都具有为 和 的所有非负值工作的优势。ab


答案 2

我认为您的基准测试存在一些缺陷,对于推断真实程序可能没有用。以下是我的想法:

  • (a|b)!=0并测试任何一个值是否为非零,而并测试两者是否均为非零。因此,您不是在比较算术的时间:如果条件更频繁地为真,则会导致更多的身体执行,这也需要更多的时间。(a+b)!=0a != 0 && b != 0(a*b)!=0if

  • (a+b)!=0对于总和为零的正值和负值,您将做错事,因此在一般情况下您不能使用它,即使它在这里工作。同样对于(MIN_VALUE),唯一的设置位将溢出顶部。a=b=0x80000000

  • 同样,将为溢出的值执行错误操作。随机示例:196608 * 327680 为 0,因为真实结果恰好可被 232 整除,因此其低 32 位为 0,如果是操作,则这些位就是您得到的全部。(a*b)!=0int

  • VM 将在外部 () 循环的最初几次运行期间优化表达式,当 为 0 时,当分支几乎从不被采用时。如果从 0.5 开始,优化程序可能会执行不同的操作。fractionfractionfraction

  • 除非 VM 能够在此处消除某些数组边界检查,否则表达式中还有其他四个分支,仅由于边界检查,这在尝试找出低级别发生的情况时是一个复杂的因素。如果将二维数组拆分为两个平面数组,则可能会得到不同的结果,将 更改为 和 。nums[0][i]nums[1][i]nums0[i]nums1[i]

  • CPU 分支预测变量检测数据中的短模式,或者检测正在获取或未获取的所有分支的运行。随机生成的基准数据是分支预测器的最坏情况。如果真实世界的数据具有可预测的模式,或者它具有全零值和全非零值的长时间运行,则分支的成本可能会低得多

  • 满足条件后执行的特定代码可能会影响评估条件本身的性能,因为它会影响循环是否可以展开、哪些 CPU 寄存器可用以及是否有任何提取的值在评估条件后需要重用。仅仅在基准测试中递增一个计数器并不是实际代码所要做的完美占位符。nums

  • System.currentTimeMillis()在大多数系统上,精度不超过 +/- 10 毫秒。 通常更准确。System.nanoTime()

有很多不确定性,并且很难说这些微优化有什么确定的,因为在一个VM或CPU上更快的技巧在另一个VM或CPU上可能会更慢。如果运行 32 位 HotSpot JVM,而不是 64 位版本,请注意它有两种类型:与“服务器”VM 相比,“客户端”VM 具有不同(较弱)的优化。

如果可以反汇编 VM 生成的机器代码,请执行此操作,而不是尝试猜测它的作用!


推荐