为什么(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"在0%~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出于好奇,了解分支预测之后.但它们在逻辑上并不等同于其他表达式,因为只有OR b需要非零才能返回true,因此它们并不意味着要比较处理效率.

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

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

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

CPU:Intel Core 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,混合模式)

Answer 1

我忽略了你的基准测试可能存在缺陷的问题,并将结果视为面值.

它是编译器还是硬件级别？

后者,我想:

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

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

  if (a * b != 0)

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

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

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

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

但是,使用此优化需要注意一件事.是否有任何值a * b != 0会给出错误的答案？考虑计算产品导致整数溢出的情况.

UPDATE

你的图表倾向于证实我说的话.

• 在条件分支a * b != 0情况下还存在"分支预测"效果,这在图中出现.

• 如果在X轴上投影超过0.9的曲线,它看起来像1)它们将在约1.0和2处相遇,会合点将与X = 0.0大致相同的Y值.

更新2

我不明白为什么曲线a + b != 0和a | b != 0案例不同.有可能是一些在分支预测逻辑聪明.或者它可能表明别的东西.

(请注意,此类事物可能特定于特定芯片型号甚至版本.您的基准测试结果可能在其他系统上有所不同.)

然而,它们都具有对所有非负值工作的优势a和b.

Answer 2

我认为你的基准测试有一些缺陷,可能对推断真正的程序没有用.这是我的想法:

• (a|b)!=0对于溢出的值(a+b)!=0会做错误的事情,并且对于总和为零的正值和负值也会做错误的事情,所以你不能在一般情况下使用这些表达式中的任何一个,即使它们在这里工作.

• a != 0 && b != 0和(a*b)!=0正在测试,如果任一值是非零的,而if与(a+b)!=0被测试,如果两者都是非零的.对于相同百分比的数据,这两种条件不会成立.

• VM将在外部((a*b)!=0)循环的前几次运行期间优化表达式,当int为0时,几乎从不采用分支.如果从fraction0.5 开始,优化器可能会执行不同的操作.

• 除非VM能够在这里消除一些数组边界检查,否则表达式中还有四个其他分支只是由于边界检查,这在尝试找出低级别发生的事情时是一个复杂的因素.如果你的二维数组分成两个扁平阵列,改变您可能会得到不同的结果fraction,并fraction以nums[0][i]和nums[1][i].

• CPU分支预测器尝试检测数据中的短模式,或者采取或不采用所有分支的运行.您随机生成的基准数据是分支预测器尝试处理的最糟糕的事情.如果您的实际数据具有可预测的模式,或者它具有全零和全非零值的长期运行,那么分支可能会花费更少的成本.

• 满足条件后执行的特定代码会影响评估条件本身的性能,因为它会影响循环是否可以展开,哪些CPU寄存器可用以及是否nums0[i]需要任何获取的值在评估条件后重复使用.仅仅增加基准测试中的计数器并不是真正的代码可以做的完美占位符.

• nums1[i]在大多数系统上,并不比+/- 10 ms更准确.nums通常更准确.

正如您所看到的那样,存在许多不确定因素,并且很难用这些微优化来说明一切,因为在一个VM或CPU上更快的技巧在另一个VM或CPU上可能更慢.如果您的VM是HotSpot,请注意还有两种类型,"客户端"VM与"服务器"VM相比具有不同(较弱)的优化.

如果您可以反汇编VM生成的机器代码,那么请尝试猜测它的作用!

Answer 3

这里的答案很好,虽然我有一个想法可以改善一些事情.

由于两个分支和相关的分支预测可能是罪魁祸首,我们可能能够在不改变逻辑的情况下将分支减少到单个分支.

bool aNotZero = (nums[0][i] != 0);
bool bNotZero = (nums[1][i] != 0);
if (aNotZero && bNotZero) { /* Some code */ }

它也可能有用

int a = nums[0][i];
int b = nums[1][i];
if (a != 0 && b != 0) { /* Some code */ }

原因是,根据短路规则,如果第一个布尔值为假,则不应评估第二个布尔值.它必须执行额外的分支以避免评估nums[1][i]是否nums[0][i]为假.现在,您可能并不关心是否nums[1][i]会进行评估,但编译器无法确定它是否会在您执行时抛出超出范围或null ref.通过将if块简化为简单bool,编译器可能足够聪明,可以意识到不必要地评估第二个布尔值不会产生负面影响.

Answer 4

当我们进行乘法运算时,即使一个数字为0,那么乘积为0

    (a*b != 0)

它评估产品的结果,从而消除从0开始的迭代的前几次出现.结果,比较小于条件时的比较.

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

将每个元素与0进行比较并进行评估.因此,所需时间较少.但我相信第二个条件可能会给你更准确的解决方案.

Answer 5

您正在使用随机输入数据,这使得分支不可预测.实际上,分支通常是(~90%)可预测的,因此在实际代码中,分支代码可能更快.

那就是说.我不知道怎么a*b != 0可能比快(a|b) != 0.通常,整数乘法比按位OR更昂​​贵.但像这样的事情偶尔会变得奇怪.例如,参见处理器缓存效果库中的"示例7:硬件复杂性"示例.