为什么 if (variable1 % variable2 == 0) 效率低下？

Question

我是java新手，昨晚正在运行一些代码，这真的让我很困扰。variable % variable我正在构建一个简单的程序来在 for 循环中显示每个 X 输出，当我使用模数作为vsvariable % 5000或诸如此类时，我注意到性能大幅下降。有人可以向我解释为什么会这样以及是什么原因造成的吗？所以我可以变得更好...这是“高效”的代码（对不起，如果我有一些语法错误，我现在不在电脑上使用代码）long startNum = 0;long stopNum = 1000000000L;for (long i = startNum; i <= stopNum; i++){    if (i % 50000 == 0) {        System.out.println(i);    }}这是“低效的代码”long startNum = 0;long stopNum = 1000000000L;long progressCheck = 50000;for (long i = startNum; i <= stopNum; i++){    if (i % progressCheck == 0) {        System.out.println(i);    }}请注意，我有一个日期变量来测量差异，一旦它变得足够长，第一个需要 50 毫秒，而另一个需要 12 秒或类似的时间。如果您的 PC 比我的效率更高，您可能需要增加stopNum或减少。progressCheck我在网上寻找这个问题，但我找不到答案，也许我只是问得不对。编辑：我没想到我的问题如此受欢迎，我感谢所有答案。我确实在每一半所花费的时间上执行了一个基准测试，效率低下的代码花费了相当长的时间，1/4 秒与 10 秒的给予或接受。当然，他们正在使用 println，但他们都在做相同的数量，所以我不认为这会产生太大的偏差，特别是因为差异是可重复的。至于答案，由于我是 Java 新手，我现在让投票决定哪个答案是最好的。我会尽量在星期三之前挑一个。EDIT2：今晚我将进行另一次测试，它不是模数，而是增加一个变量，当它到达progressCheck时，它将执行一个，然后将该变量重置为0。对于第三个选项。EDIT3.5：我使用了这段代码，下面我将展示我的结果。谢谢大家的帮助！我还尝试将 long 的 short 值与 0 进行比较，因此我所有的新检查都会发生“65536”次，使其重复相等。结果：固定 = 874 毫秒（通常在 1000 毫秒左右，但由于它是 2 的幂而更快）变量 = 8590 毫秒最终变量 = 1944 毫秒（使用 50000 时约为 1000 毫秒）增量 = 1904 毫秒短转换 = 679 毫秒不足为奇的是，由于缺乏划分，短转换比“快速”方式快 23%。这很有趣。如果您需要每 256 次（或大约在那里）显示或比较一些东西，您可以这样做，并使用if ((byte)integer == 0) {'Perform progress check code here'}最后一个有趣的说明，在“最终声明的变量”上使用 65536（不是一个漂亮的数字）的模数是（慢）固定值速度的一半。之前它以接近相同的速度进行基准测试。

Answer 1

您正在测量OSR（堆栈上替换）存根。

OSR 存根是一种特殊版本的编译方法，专门用于在方法运行时将执行从解释模式转移到编译代码。

OSR 存根不像常规方法那样优化，因为它们需要与解释帧兼容的帧布局。我已经在以下答案中展示了这一点：1 , 2 , 3。

类似的事情也发生在这里。当“低效代码”运行一个长循环时，该方法是专门为循环内的堆栈替换而编译的。状态从解释帧转移到 OSR 编译方法，该状态包括progressCheck局部变量。此时 JIT 无法用常量替换变量，因此无法应用某些优化，如强度降低。

特别是这意味着 JIT 不会用乘法代替整数除法。（请参阅为什么 GCC 在实现整数除法时使用乘以一个奇怪的数字？对于提前编译器的 asm 技巧，当值是内联/常量传播后的编译时常量时，如果启用了这些优化.表达式中的整数文字也通过 优化，类似于此处由 JITer 优化的地方，即使在 OSR 存根中也是如此。）%gcc -O0

但是，如果您多次运行相同的方法，则第二次和后续运行将执行常规（非 OSR）代码，这是完全优化的。这是证明理论的基准（使用 JMH 进行基准测试）：

@State(Scope.Benchmark)

public class Div {

    @Benchmark

    public void divConst(Blackhole blackhole) {

        long startNum = 0;

        long stopNum = 100000000L;

        for (long i = startNum; i <= stopNum; i++) {

            if (i % 50000 == 0) {

                blackhole.consume(i);

            }

        }

    }

    @Benchmark

    public void divVar(Blackhole blackhole) {

        long startNum = 0;

        long stopNum = 100000000L;

        long progressCheck = 50000;

        for (long i = startNum; i <= stopNum; i++) {

            if (i % progressCheck == 0) {

                blackhole.consume(i);

            }

        }

    }

}

结果：

# Benchmark: bench.Div.divConst

# Run progress: 0,00% complete, ETA 00:00:16

# Fork: 1 of 1

# Warmup Iteration   1: 126,967 ms/op

# Warmup Iteration   2: 105,660 ms/op

# Warmup Iteration   3: 106,205 ms/op

Iteration   1: 105,620 ms/op

Iteration   2: 105,789 ms/op

Iteration   3: 105,915 ms/op

Iteration   4: 105,629 ms/op

Iteration   5: 105,632 ms/op

# Benchmark: bench.Div.divVar

# Run progress: 50,00% complete, ETA 00:00:09

# Fork: 1 of 1

# Warmup Iteration   1: 844,708 ms/op          <-- much slower!

# Warmup Iteration   2: 105,893 ms/op          <-- as fast as divConst

# Warmup Iteration   3: 105,601 ms/op

Iteration   1: 105,570 ms/op

Iteration   2: 105,475 ms/op

Iteration   3: 105,702 ms/op

Iteration   4: 105,535 ms/op

Iteration   5: 105,766 ms/op

由于 OSR 存根编译效率低下，第一次迭代divVar确实慢得多。但是，只要方法从头开始重新运行，就会执行新的不受约束的版本，该版本会利用所有可用的编译器优化。

Answer 2

在跟进@phuclv comment时，我检查了JIT 1生成的代码，结果如下：

对于variable % 5000（除以常数）：

mov     rax,29f16b11c6d1e109h

imul    rbx

mov     r10,rbx

sar     r10,3fh

sar     rdx,0dh

sub     rdx,r10

imul    r10,rdx,0c350h    ; <-- imul

mov     r11,rbx

sub     r11,r10

test    r11,r11

jne     1d707ad14a0h

对于variable % variable：

mov     rax,r14

mov     rdx,8000000000000000h

cmp     rax,rdx

jne     22ccce218edh

xor     edx,edx

cmp     rbx,0ffffffffffffffffh

je      22ccce218f2h

cqo

idiv    rax,rbx           ; <-- idiv

test    rdx,rdx

jne     22ccce218c0h

因为除法总是比乘法花费更长的时间，所以最后一个代码片段的性能较低。

爪哇版：

java version "11" 2018-09-25

Java(TM) SE Runtime Environment 18.9 (build 11+28)

Java HotSpot(TM) 64-Bit Server VM 18.9 (build 11+28, mixed mode)

Answer 3

正如其他人所指出的，一般的模运算需要进行除法。在某些情况下，除法可以（由编译器）用乘法代替。但与加法/减法相比，两者都可能很慢。因此，可以通过以下方式获得最佳性能：

long progressCheck = 50000;

long counter = progressCheck;

for (long i = startNum; i <= stopNum; i++){

    if (--counter == 0) {

        System.out.println(i);

        counter = progressCheck;

    }

}

（作为一个小的优化尝试，我们在这里使用一个预递减递减计数器，因为在许多架构上0，与算术运算之后的立即比较成本正好为 0 指令/CPU 周期，因为 ALU 的标志已经由前面的操作适当地设置。一个体面的优化但是，即使您编写了 .，编译器也会自动进行优化if (counter++ == 50000) { ... counter = 0; }。）

i请注意，您通常并不真正想要/需要模数，因为您知道循环计数器（如果加一计数器达到某个值。

另一个“技巧”是使用二次幂值/限制，例如progressCheck = 1024;. 模数 2 的幂可以通过按位快速计算and，即if ( (i & (1024-1)) == 0 ) {...}. 这也应该很快，并且在某些架构上可能会优于上面的显式counter。