为什么在Java中，(a*b != 0)比(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 或 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 Runtime Environment (build 1.8.0_45-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.45-b02, mixed mode)

- Maljam

---

如果 !(a == 0 || b == 0) 怎么办？微基准测试极不可靠，这很难真正测量出来（大约3%听起来像是误差范围）。 - Elliott Frisch

或者 a != 0 & b != 0。 - Louis Wasserman

如果预测的分支错误，那么分支会变慢。 a*b！= 0 少了一个分支。 - Erwin Bolwidt

(1<<16) * (1<<16) == 0，但它们都不等于零。 - CodesInChaos

@GeneпјҡжӮЁжҸҗеҮәзҡ„дјҳеҢ–ж–№жЎҲж— ж•ҲгҖӮеҚідҪҝеҝҪз•ҘжәўеҮәпјҢеҰӮжһң a е’Ң b дёӯжңүдёҖдёӘдёәйӣ¶пјҢеҲҷ a*b з»“жһңдёәйӣ¶пјӣеҸӘжңүеҪ“дёӨиҖ…йғҪдёәйӣ¶ж—¶пјҢa|b з»“жһңжүҚдёәйӣ¶гҖӮ - hmakholm left over Monica

Answer 1

我会忽略你的基准测试可能存在缺陷这个问题，并直接采用结果。

是编译器的问题还是硬件水平的问题？

我认为是后者：

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

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

  if (a * b != 0)

这段代码将编译成2个内存加载、一个乘法和一个条件分支。

如果硬件级别的分支预测无效，那么乘法很可能比第二个条件分支快。随着比率的增加，分支预测变得越来越不起作用。

条件分支较慢的原因是它们会导致指令执行流水线停顿。分支预测的目的是通过预测分支走向并基于此做出下一条指令的猜测，以避免停顿。如果预测失败，则需要延迟加载另一个方向的指令。

（注意：上述解释过于简化。要了解更准确的解释，您需要查看CPU制造商为汇编语言编写者和编译器编写者提供的文献。维基百科关于分支预测器的页面是良好的背景知识。）

---

然而，使用这种优化方法需要小心。当计算乘积导致整数溢出时，是否存在 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有效的优点。

- Stephen C

---

@DebosmitRay - 1) 不应该有软件。中间结果将保存在寄存器中。2）在第二种情况下，有两个可用的分支：一个执行“一些代码”，另一个跳过if后面的下一条语句。 - Stephen C

@StephenC 你对于 a+b 和 a|b 感到困惑是正确的，因为曲线确实是相同的，我认为是颜色非常接近。对于色盲的人表示歉意！ - Maljam

从概率的角度来看，这些情况应该在50%的轴上对称（即 a&b 和 a|b 的零概率）。它们确实是对称的，但不是完全对称的，这就是这个谜题。 - Antonín Lejsek

@StephenC “a * b != 0”和“a + b != 0”基准测试结果不同的原因是因为它们并不等价，也永远不应该被基准测试。例如，当“a=1, b=0”时，第一个表达式的值为假，但第二个表达式的值为真。乘法运算类似于“and”运算符，而加法运算类似于“or”运算符。 - JS1

@AntonínLejsek 我认为概率会有所不同。如果你有 n 个零，那么 a 和 b 都是零的可能性会随着 n 的增加而增加。在一个 AND 操作中，随着 n 的增加，它们中有一个 非零 的概率会增加，从而满足条件。对于一个 OR 操作来说则相反（其中任意一个都 为零 的概率会随着 n 的增加而增加）。这是基于数学角度的。我不确定硬件是否是这样工作的。 - WYSIWYG

Answer 2

我认为你的基准测试存在一些缺陷，可能不适用于推断真实程序。以下是我的想法：

• (a|b)!=0和(a+b)!=0测试是否有任意一个值为非零，而a != 0 && b != 0和(a*b)!=0测试是否两个值都为非零。因此，您不仅比较算术的时间：如果条件更经常为真，则会导致更多的if体执行，这也需要更多的时间。

• (a+b)!=0对于相加为零的正数和负数将产生错误结果，因此在一般情况下不能使用它，即使它在这里起作用。此外，对于a=b=0x80000000（MIN_VALUE），唯一的设置位将溢出到顶部。

• 同样，(a*b)!=0对于溢出的值将产生错误结果。随机示例：196608 * 327680为0，因为真实结果恰好可被2³²整除，因此其低32位为0，如果它是一个int操作，则只能获得这些位。

• 虚拟机将在外部(fraction)循环的前几次运行期间优化表达式，当fraction为0时，分支几乎从不被执行。如果您从0.5开始fraction，优化器可能会执行不同的操作。

• 除非虚拟机能够消除这里的一些数组边界检查，否则由于边界检查，表达式中还有四个其他分支，这是在试图弄清楚低级别发生的事情时的一个复杂因素。如果将二维数组分成两个平面数组，将nums[0][i]和nums[1][i]更改为nums0[i]和nums1[i]，则可能会获得不同的结果。

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

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

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

由于这些微观优化技巧在不同的虚拟机或CPU上可能会产生不同效果，因此很难确切地说出什么是最好的。如果使用32位的HotSpot JVM而非64位版本，则应注意它有两种类型：具有不同（较弱）优化的“客户端”VM和“服务器”VM。

如果您能够反汇编由VM生成的机器代码, 那就尽量这样做，而不是去猜测它的作用！

- Boann

---

我认为仍然值得提到的是，a|b != 0 没有 a+b 的任何问题。无论 C++ 编译器是否将 a||b 优化为 a|b（当它是安全的时候），例如 NULL 解引用不可能。（https://dev59.com/OlEG5IYBdhLWcg3wMGEK）（https://godbolt.org/z/EKnYbo7En）这是 Java 实现可以做的事情；如果现在还没有，那么将来要注意这一点。 - Peter Cordes

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 */ }

原因在于，按照短路规则，如果第一个布尔值为false，第二个布尔值就不应该被评估。它必须执行额外的分支来避免在nums[0][i]为false时评估nums[1][i]。现在，您可能不关心nums[1][i]是否被评估，但是编译器无法确定在这样做时它不会引发超出范围或空引用异常。通过将if块简化为简单的bool值，编译器可以聪明地意识到不必要地评估第二个布尔值不会产生负面影响。

- Pagefault

---

虽然我有一种感觉这并没有完全回答问题，但我还是点了赞。 - Pierre Arlaud

这是一种引入分支的方法，而不改变非分支逻辑（如果获取 a 和 b 的方式具有副作用，则应保留它们）。你仍然有 &&，因此你仍然有一个分支。 - Jon Hanna

如果组合条件比单独的条件更可预测，那么应该避免短路评估。例如，执行 aZero = (nums[0][i] == 0) 等操作和 if (! (aZero | bZero) ) 或其他操作。或者我猜在没有隐式布尔->整数转换的Java中需要 nums[...] == 0 ? 1 : 0。这可能需要几个汇编指令来实际实现，因此如果第一个（或两个）分支预测良好，则会比2个分支慢。 - Peter Cordes

请注意，Java没有“bool”类型；它被称为“boolean”。 - Peter Cordes

Answer 4

你正在使用随机输入数据，这使得分支变得不可预测。在实践中，分支通常是（约90％）可预测的，因此在真实代码中，带分支的代码很可能会更快。

话虽如此，我不明白为什么 a*b != 0 比 (a|b) != 0 更快。一般情况下，整数乘法比按位或更昂贵。但有时候事情会变得奇怪。例如，请参见来自处理器缓存效应画廊的“示例7：硬件复杂性”示例。

- StackedCrooked

---

& 不是“按位或”，而是（在本例中）“逻辑与”，因为两个操作数都是布尔值，并且不是 | :-) - siegi

@siegi 今天我学到了 Java 中的 '&' 实际上是一个没有短路的逻辑 AND。 - StackedCrooked

& 不是逻辑 AND，而是按位 AND。与 C 语言相同。因此，a & b 不等同于 a && b。但是，由于“任何一方设置的位”与“没有设置的位”与“没有交集的位”的差异，a|b 等同于 a || b。 - Peter Cordes

@PeterCordes：在Siegi明确指出的“两个操作数都是布尔值”的特殊情况下，逻辑AND和按位AND之间没有区别。对于布尔值来说，可以正确地说&是没有短路行为的逻辑AND，而&&是具有短路行为的逻辑AND。 - Ben Voigt

是的，但回复siegi的正确评论时省略了提到“今天我学到了（TIL）”的特殊情况。有趣的是，由于Java不会在boolean和int之间进行隐式转换，因此它不仅仅是带引号的“逻辑AND”，即不像在C++中一样用于1位操作数的按位AND。在Java中，当在boolean操作数上使用时，它确实是一个逻辑AND，并且您不能执行true＆123。 - Peter Cordes

Answer 5

当我们进行乘法运算时，即使其中一个数字为0，积也会等于0。在编写代码时，请确保考虑到这一点。

    (a*b != 0)

它评估产品的结果，从而消除了从0开始的前几次迭代。因此，当条件为时，比较会少一些。

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

每个元素与0进行比较并计算。因此所需时间更短。但我认为第二个条件可能会给您更准确的解决方案。

- Sanket Gupte

---

如果a为零，则第二个表达式不需要评估b，因为整个表达式已经是false。因此，“每个元素都被比较”并不正确。 - Kuba Wyrostek

Answer 6

我知道这个问题有点老了，但出于好奇和训练目的，我使用了JMH进行了一些测试。结果略有不同：

• 按位或（a | b != 0）和乘法（a * b != 0）速度最快；
• 普通与运算（a!=0 & b!=0）几乎和乘法一样快；
• 短路与与短路或（a!=0 && b!=0、!(a!=0 || b!=0)）速度最慢。

免责声明：我甚至不是JMH的专家。

以下是代码，我尝试复制了问题中发布的代码，并添加了按位或操作：

@Warmup(iterations = 5, time = 100, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 100, timeUnit = TimeUnit.MILLISECONDS)
@Fork(value = 3)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@State(Scope.Benchmark)
public class MultAnd {
    
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
            .include(MultAnd.class.getSimpleName())
            .build();
        
        new Runner(opt).run();
    }

    private static final int size = 50_000_000;
    
    @Param({"0.00", "0.10", "0.20", "0.30", "0.40", "0.45", 
            "0.50", "0.55", "0.60", "0.70", "0.80", "0.90", 
            "1.00"})
    private double fraction;

    private int[][] nums;

    @Setup
    public void setup() {
        nums = new int[2][size];
        for(int i = 0 ; i < 2 ; i++) {
            for(int j = 0 ; j < size ; j++) {
                double random = Math.random();
                if (random < fraction) 
                    nums[i][j] = 0;
                else 
                    nums[i][j] = (int) (random*15 + 1);
            }
        }
    }
    
    @Benchmark
    public int and() {
        int s = 0;
        for (int i = 0; i < size; i++) {
            if ((nums[0][i]!=0) & (nums[1][i]!=0))
                s++;
        }
        return s;
    }
    
    @Benchmark
    public int andAnd() {
        int s = 0;
        for (int i = 0; i < size; i++) {
            if ((nums[0][i]!=0) && (nums[1][i]!=0))
                s++;
        }
        return s;
    }
    
    @Benchmark
    public int bitOr() {
        int s = 0;
        for (int i = 0; i < size; i++) {
            if ((nums[0][i] | nums[1][i]) != 0)
                s++;
        }
        return s;
    }
    
    @Benchmark
    public int mult() {
        int s = 0;
        for (int i = 0; i < size; i++) {
            if (nums[0][i]*nums[1][i] != 0)
                s++;
        }
        return s;
    }
    
    @Benchmark
    public int notOrOr() {
        int s = 0;
        for (int i = 0; i < size; i++) {
            if (!((nums[0][i]!=0) || (nums[1][i]!=0)))
                s++;
        }
        return s;
    }
}

结果如下：

REMEMBER: The numbers below are just data. To gain reusable insights, you need to follow up on
why the numbers are the way they are. Use profilers (see -prof, -lprof), design factorial
experiments, perform baseline and negative tests that provide experimental control, make sure
the benchmarking environment is safe on JVM/OS/HW level, ask for reviews from the domain experts.
Do not assume the numbers tell you what you want them to tell.

Benchmark        (fraction)  Mode  Cnt    Score    Error  Units
MultAnd.and            0.00  avgt   30   33.238 ±  0.883  ms/op
MultAnd.and            0.10  avgt   30   48.011 ±  1.635  ms/op
MultAnd.and            0.20  avgt   30   48.284 ±  1.797  ms/op
MultAnd.and            0.30  avgt   30   47.969 ±  1.463  ms/op
MultAnd.and            0.40  avgt   30   48.999 ±  2.881  ms/op
MultAnd.and            0.45  avgt   30   47.804 ±  1.053  ms/op
MultAnd.and            0.50  avgt   30   48.332 ±  1.990  ms/op
MultAnd.and            0.55  avgt   30   47.457 ±  1.210  ms/op
MultAnd.and            0.60  avgt   30  127.530 ±  3.104  ms/op
MultAnd.and            0.70  avgt   30   92.630 ±  1.471  ms/op
MultAnd.and            0.80  avgt   30   69.458 ±  1.609  ms/op
MultAnd.and            0.90  avgt   30   55.421 ±  1.443  ms/op
MultAnd.and            1.00  avgt   30   30.672 ±  1.387  ms/op
MultAnd.andAnd         0.00  avgt   30   33.187 ±  0.978  ms/op
MultAnd.andAnd         0.10  avgt   30  110.943 ±  1.435  ms/op
MultAnd.andAnd         0.20  avgt   30  177.527 ±  2.353  ms/op
MultAnd.andAnd         0.30  avgt   30  226.247 ±  1.879  ms/op
MultAnd.andAnd         0.40  avgt   30  266.316 ± 18.647  ms/op
MultAnd.andAnd         0.45  avgt   30  258.120 ±  2.638  ms/op
MultAnd.andAnd         0.50  avgt   30  259.727 ±  3.532  ms/op
MultAnd.andAnd         0.55  avgt   30  248.706 ±  1.419  ms/op
MultAnd.andAnd         0.60  avgt   30  229.825 ±  1.256  ms/op
MultAnd.andAnd         0.70  avgt   30  177.911 ±  2.787  ms/op
MultAnd.andAnd         0.80  avgt   30  121.303 ±  2.724  ms/op
MultAnd.andAnd         0.90  avgt   30   67.914 ±  1.589  ms/op
MultAnd.andAnd         1.00  avgt   30   15.892 ±  0.349  ms/op
MultAnd.bitOr          0.00  avgt   30   33.271 ±  1.896  ms/op
MultAnd.bitOr          0.10  avgt   30   35.597 ±  1.536  ms/op
MultAnd.bitOr          0.20  avgt   30   42.366 ±  1.641  ms/op
MultAnd.bitOr          0.30  avgt   30   58.385 ±  0.778  ms/op
MultAnd.bitOr          0.40  avgt   30   85.567 ±  1.678  ms/op
MultAnd.bitOr          0.45  avgt   30   32.152 ±  1.345  ms/op
MultAnd.bitOr          0.50  avgt   30   32.190 ±  1.357  ms/op
MultAnd.bitOr          0.55  avgt   30   32.335 ±  1.384  ms/op
MultAnd.bitOr          0.60  avgt   30   31.910 ±  1.026  ms/op
MultAnd.bitOr          0.70  avgt   30   31.783 ±  0.807  ms/op
MultAnd.bitOr          0.80  avgt   30   31.671 ±  0.745  ms/op
MultAnd.bitOr          0.90  avgt   30   31.329 ±  0.708  ms/op
MultAnd.bitOr          1.00  avgt   30   30.530 ±  0.534  ms/op
MultAnd.mult           0.00  avgt   30   30.859 ±  0.735  ms/op
MultAnd.mult           0.10  avgt   30   33.933 ±  0.887  ms/op
MultAnd.mult           0.20  avgt   30   34.243 ±  0.917  ms/op
MultAnd.mult           0.30  avgt   30   33.825 ±  1.155  ms/op
MultAnd.mult           0.40  avgt   30   34.309 ±  1.334  ms/op
MultAnd.mult           0.45  avgt   30   33.709 ±  1.277  ms/op
MultAnd.mult           0.50  avgt   30   37.699 ±  4.029  ms/op
MultAnd.mult           0.55  avgt   30   36.374 ±  2.948  ms/op
MultAnd.mult           0.60  avgt   30  100.354 ±  1.553  ms/op
MultAnd.mult           0.70  avgt   30   69.570 ±  1.441  ms/op
MultAnd.mult           0.80  avgt   30   47.181 ±  1.567  ms/op
MultAnd.mult           0.90  avgt   30   33.552 ±  0.999  ms/op
MultAnd.mult           1.00  avgt   30   30.775 ±  0.548  ms/op
MultAnd.notOrOr        0.00  avgt   30   15.701 ±  0.254  ms/op
MultAnd.notOrOr        0.10  avgt   30   68.052 ±  1.433  ms/op
MultAnd.notOrOr        0.20  avgt   30  120.393 ±  2.299  ms/op
MultAnd.notOrOr        0.30  avgt   30  177.729 ±  2.438  ms/op
MultAnd.notOrOr        0.40  avgt   30  229.547 ±  1.859  ms/op
MultAnd.notOrOr        0.45  avgt   30  250.660 ±  4.810  ms/op
MultAnd.notOrOr        0.50  avgt   30  258.760 ±  2.190  ms/op
MultAnd.notOrOr        0.55  avgt   30  258.010 ±  1.018  ms/op
MultAnd.notOrOr        0.60  avgt   30  254.732 ±  2.076  ms/op
MultAnd.notOrOr        0.70  avgt   30  227.148 ±  2.040  ms/op
MultAnd.notOrOr        0.80  avgt   30  180.193 ±  4.659  ms/op
MultAnd.notOrOr        0.90  avgt   30  112.212 ±  3.111  ms/op
MultAnd.notOrOr        1.00  avgt   30   33.458 ±  0.952  ms/op

或者以图表形式呈现：

- user16320675