我正在用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 != 0a!=0 && b!=0快:

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

我很想知道为什么.有人能解释一下吗?它是编译器还是硬件级的?

Edit: Out of curiosity...现在我了解了分支预测,我想知道模拟比较会显示a OR b是非零的:

Graph of a or b non-zero

我们确实看到了与预期相同的分支预测效果,有趣的是,图形在X轴上有点翻转.

使现代化

1-我在分析中加了!(a==0 || b==0),看看会发生什么.

2-在学习了分支预测之后,出于好奇,我还收录了a != 0 || b != 0(a+b) != 0(a|b) != 0.但它们在逻辑上并不等同于其他表达式,因为只有ORb需要非零才能返回TRUE,因此它们不是用来比较处理效率的.

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

4-一些人建议将a != 0 & b != 0分为a != 0 & b != 0分,而不是a != 0 && b != 0分,他们预测它的表现将更接近a*b != 0分,因为我们将消除分支预测效应.我不知道&可以用于布尔变量,我以为它只用于整数的二进制运算.

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

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

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)

推荐答案

我忽略了一个问题,即你的基准测试might可能存在缺陷,并从表面上看结果.

它是编译器还是硬件级的?

我认为后者:

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

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

  if (a * b != 0)

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

如果硬件级分支预测无效,乘法很可能比第二个条件分支快.随着比例的增加...分支预测的效果越来越差.

条件分支速度较慢的原因是它们会导致指令执行流水线停止.分支预测是关于通过预测分支要go 往哪个方向并在此基础上推测性地 Select 下一条指令来避免停顿.如果预测失败,则在加载另一个方向的指令时会有延迟.

(注:以上解释过于简单.要获得更准确的解释,你需要查看CPU制造商为汇编语言程序员和编译器编写者提供的文献.Branch Predictors页上的维基百科页面是很好的背景.)


但是,对于此优化,有一件事需要注意.是否存在a * b != 0会给出错误答案的值?考虑计算乘积导致整数溢出的情况.


UPDATE

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

  • 在条件分支a * b != 0的情况下,也有一个"分支预测"效应,这在图中可以看出.

  • 如果在X轴上将曲线投影到0.9以上,看起来1)它们将在约1.0处相交,2)相交点的Y值与X=0.0时的Y值大致相同.


UPDATE 2

我不明白为什么a + b != 0例和a | b != 0例的曲线不同.分支预测器逻辑中有一些巧妙的东西.或者它可能预示着其他事情.

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

然而,它们都有适用于所有非负值ab的优点.

Java相关问答推荐

泽西岛:退回到不注射的客户"

在Java Stream上调用collect方法出现意外结果

关于泛型的覆盖规则

在Java Swing Paint应用程序中捕获快速鼠标移动时遇到困难

将关键字与正文中的_Allowed匹配,但带有__Signing可选后缀

GSON期间的Java类型擦除

使用Spring和ActiveMQ的侦听器方法引发属性名称不能重复为空警告

使用UTC时区将startDatetime转换为本地时间

与不同顺序的组进行匹配,不重复组但分开

Jenv-相同的Java版本,但带有前缀

使用正则表达式从字符串中提取多个值

如何在透视表中添加对计数列的筛选?

对从Spring Boot 3.1.5升级到3.2.0的方法的查询验证失败

try 使用预准备语句占位符获取信息时出现Try-With-Resources错误

在应用程序运行时更改LookAndFeel

Java HashMap保留所有时间复杂性

为什么没有加载java.se模块?

如何在Struts2中使用操作类中的结果注释重定向到不同的命名空间

如果c不为null,Arrays.sort(T[]a,Comparator<;?super T>;c)是否会引发ClassCastException?

java中的网上购物车解析错误