用ChatGPT解决这个技术问题 Extra ChatGPT

为什么 (a*b != 0) 在 Java 中比 (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”在大约 3% 的时间内等于 0，则 a*b != 0 比 a!=0 && b!=0 快：

https://i.stack.imgur.com/POHYD.png

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

编辑：出于好奇......现在我了解了分支预测，我想知道模拟比较会显示 a OR b 非零：

https://i.stack.imgur.com/GpJoM.png

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

更新

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

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

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

4- 有些人建议包含 a != 0 & b != 0 而不是 a != 0 && b != 0，预测它的行为会更接近 a*b != 0，因为我们将消除分支预测效应。我不知道 & 可以与布尔变量一起使用，我认为它仅用于整数的二进制操作。

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

CPU：英特尔酷睿 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，混合模式)

if (!(a == 0 || b == 0)) 呢？微基准是出了名的不可靠，这不太可能真正可衡量（~3% 对我来说听起来像是一个误差范围）。
或a != 0 & b != 0。
如果预测的分支错误，则分支会很慢。 a*b!=0 少了一个分支
(1<<16) * (1<<16) == 0 但两者都不为零。
@Gene：您提出的优化无效。即使忽略溢出，如果 a 的 一个 且 b 为零，则 a*b 为零； a|b 只有当两者都为零时才为零。

S
Stephen C

我忽略了您的基准测试可能存在缺陷的问题，并从表面上看结果。

是编译器还是硬件级别？

后者，我认为： 

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

将编译为 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 != 0 和 a | b != 0 情况的曲线不同。在分支预测器逻辑中可能有一些巧妙之处。或者它可能表明其他东西。

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

但是，它们都具有适用于 a 和 b 的所有非负值的优势。

@DebosmitRay - 1）不应该有软件。中间结果将保存在寄存器中。 2) 在第二种情况下，有两个可用的分支：一个执行“一些代码”，另一个跳到 if 之后的下一条语句。
@StephenC您对a + b和a | b感到困惑是对的，因为曲线是相同的，我认为颜色非常接近。向色盲人士道歉！
@njzk2 从概率的角度来看，这些情况应该根据 50% 的轴对称（a&b 和 a|b 的概率为零）。他们是，但不完美，这就是难题。
@StephenC a*b != 0 和 a+b != 0 基准测试不同的原因是因为 a+b != 0 根本不等效，不应该进行基准测试。例如，对于 a = 1, b = 0，第一个表达式的计算结果为 false，但第二个表达式的计算结果为 true。乘法有点像 and 运算符，而加法有点像 or 运算符。
@AntonínLejsek 我认为概率会有所不同。如果您有 n 个零，那么 a 和 b 都为零的可能性随着 n 的增加而增加。在 AND 操作中，n 越高，其中一个 非零 的概率增加并且满足条件。这与 OR 操作相反（其中任何一个操作为零的概率随着 n 而增加）。这是基于数学的观点。我不确定硬件是否是这样工作的。
B
Boann

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

(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，因为真正的结果恰好可以被 232 整除，所以它的低 32 位为 0，如果它是一个 int 操作，这些位就是你得到的全部。

VM 将在外部（分数）循环的前几次运行期间优化表达式，当分数为 0 时，几乎从不采用分支。如果你从 0.5 开始，优化器可能会做不同的事情。

除非 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 相比具有不同（较弱）的优化。

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

我认为仍然值得一提的是，a|b != 0 没有任何 a+b 的问题。不管关于 C++ 编译器将 a||b 优化为 a|b when it's safe 的脚注如何，例如 NULL deref 是不可能的。 (godbolt.org/z/EKnYbo7En) Java 实现可以做到这一点；如果不是现在，将来需要注意的事情。
P
Pagefault

这里的答案很好，尽管我有一个可能会改善事情的想法。

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

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] 被评估，但编译器不能确定它不会在您这样做时抛出超出范围或空引用。通过将 if 块简化为简单的布尔值，编译器可能足够聪明，可以意识到不必要地评估第二个布尔值不会产生负面影响。

赞成，尽管我觉得这并不能完全回答问题。
这是一种在不改变非分支逻辑的情况下引入分支的方法（如果您获得 a 和 b 的方式有副作用，您会保留它们）。您仍然有 &&，所以您仍然有一个分支。
如果组合条件比单独条件更可预测，则应避免短路评估。例如做aZero = (nums[0][i] == 0)等和if (! (aZero | bZero) )之类的。或者我猜想没有隐式 bool->int 转换的 Java 需要 nums[...] == 0 ? 1 : 0。这可能需要几个 asm 指令才能实际实现，因此如果第一个（或两者）预测良好，则将比 2 个分支慢。
请注意，Java 没有 bool 类型；它被称为 boolean。
S
Sanket Gupte

当我们乘法时，即使一个数是0，那么乘积也是0。在写的时候 

    (a*b != 0)

它评估乘积的结果，从而消除从 0 开始的前几次迭代。因此，比较少于条件为 

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

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

在第二个表达式中，如果 a 为零，则不需要评估 b，因为整个表达式已经为假。所以每个元素都比较是不正确的。
S
StackedCrooked

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

那就是说。我看不出 a*b != 0 如何比 (a|b) != 0 快。通常整数乘法比按位或更昂贵。但是这样的事情偶尔会变得很奇怪。例如，参见 Gallery of Processor Cache Effects 中的“示例 7：硬件复杂性”示例。

& 不是“按位或”，而是（在这种情况下）是“逻辑与”，因为两个操作数都是布尔值，它不是 | ;-)
@siegi TIL Java '&' 实际上是一个没有短路的逻辑与。
& 不是逻辑与，而是按位与。与 C 中的相同。所以 a & b 不 等同于 a && b。但 a|b 等同于 a || b，只是因为“任何一个中设置的任何位”与“未设置位”与“无相交位”的工作方式不同。
@PeterCordes：在siegi明确声称的特殊情况下“两个操作数都是布尔值”，逻辑AND和按位AND之间没有区别。对于布尔值，正确地说 & 是没有短路的逻辑 AND，而 && 是具有短路行为的逻辑 AND。
是的，但是对 siegi 正确评论的回复在说“今天我学会了（TIL）”时省略了提到那个特殊情况。有趣的是，由于 Java 不会在 boolean 和 int 之间进行隐式转换，因此它不仅仅是引号中的“逻辑与”，即不是碰巧在 C++ 中的 1 位操作数上使用的按位与.在 Java 中，当用于 boolean 操作数时，它确实是一个逻辑与，而您不能使用 true & 123。
u
user16320675

我知道这个问题很老，但出于好奇和培训，我使用 JMH 做了一些测试。结果略有不同：

按位或 (a | b != 0) 和乘法 (a * b != 0) 最快；

正常 AND (a!=0 & b!=0) 几乎和乘法一样好

短路 AND 和 OR (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

https://i.stack.imgur.com/WJUZK.png

关注公众号,不定期副业成功案例分享
关注公众号

不定期副业成功案例分享

想领先一步获取最新的外包任务吗？

立即订阅

HuntsBot(狩猎机器人)，一站式外包任务、远程工作、产品创意分享与订阅平台，支持钉钉、飞书、企业微信、邮箱、Telegram机器人订阅。平台会以及时、稳定、可靠的技术把外包任务需求、远程工作机会、产品创意等推送给每一位订阅的用户。

简体中文 English

平台

支持

联系我们

在使用过程中有任何问题或建议，可以通过以下方式联系我们：

微信公众号: 火星来客

Email: huntsbot@xinbeitime.com

Copyright© 2022-2023 www.huntsbot.com 浙ICP备2022000860号-4 All Rights Reserved.