首页 文章

为什么（a * b！= 0）比Java中的（a！= 0 && b！= 0）更快？

提问于
浏览 次
363

我正在用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 快：

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

Edit: 出于好奇......现在我学会了分支预测，我想知道模拟比较会显示 OR b是非零的：

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

更新

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

在了解了分支预测之后，我还出于好奇而包含了 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，混合模式）

java performance processing-efficiency microbenchmark branch-prediction

5 回答

  • 21

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

    那就是说 . 我不知道 a*b != 0 如何比 (a|b) != 0 更快 . 通常，整数乘法比按位OR更昂贵 . 但像这样的事情偶尔会变得奇怪 . 例如，参见Gallery of Processor Cache Effects中的"Example 7: Hardware complexities"示例 .

    回复于
  • 6

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

    (a*b != 0)

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

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

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

    回复于
  • 219

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

    是编译器还是硬件级别？

    后者，我想：

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

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

    if (a * b != 0)

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

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

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

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

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

    UPDATE

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

    • 在条件分支 a * b != 0 情况下还有"branch prediction"效果，这在图中显示 .

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

    UPDATE 2

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

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

    但是，它们都具有为 a 和 b 的所有非负值工作的优势 .

    回复于
  • 10

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

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

    • (a|b)!=0 和 (a+b)!=0 正在测试任一值是否为非零，而 (a*b)!=0 和 a != 0 && b != 0 正在测试两者是否为非零 . 在相同百分比的数据中，这两种条件不会成立 .

    • VM将在外部（ fraction ）循环的前几次运行期间优化表达式，当 fraction 为0时，几乎从不采用分支 . 如果以0.5开始 fraction ，优化器可能会执行不同的操作 .

    • 除非VM能够在这里消除一些数组边界检查，否则表达式中有四个其他分支只是由于边界检查，并且's a complicating factor when trying to figure out what'发生在低级别 . 如果将二维数组拆分为两个平面数组，将 nums[0][i] 和 nums[1][i] 更改为 nums0[i] 和 nums1[i] ，则可能会得到不同的结果 .

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

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

    • System.currentTimeMillis() 在大多数系统上并不比/ - 10 ms更准确 . System.nanoTime() 通常更准确 .

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

    如果你能disassemble the machine code generated by the VM，那就做，而不是试图猜测它的作用！

    回复于
  • 63

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

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

    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[0][i] 为假，它必须执行额外的分支以避免评估 nums[1][i] . 现在，您可能并不关心 nums[1][i] 是否会被评估，但是当您这样做时，编译器可能会抛出超出范围或null ref . 通过将if块简化为简单bool，编译器可能足够聪明，可以意识到不必要地评估第二个布尔值不会产生负面影响 .

    回复于

相关问题