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

2022-08-31 06:45:30

我是Java的新手,昨晚正在运行一些代码,这真的困扰着我。我正在构建一个简单的程序来显示for循环中的每个X输出,当我使用模量作为vs或其他东西时,我注意到性能会大幅下降。有人可以向我解释为什么会这样以及导致这种情况的原因吗?所以我可以做得更好...variable % variablevariable % 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比我的PC更有效或什么没有。stopNumprogressCheck

我在网上寻找这个问题,但我找不到答案,也许我只是问得不对。

编辑:我没想到我的问题如此受欢迎,我很欣赏所有的答案。我确实对每半场进行了基准测试,并且效率低下的代码花费了相当长的时间,1/4秒而不是10秒的给予或采取。当然,他们正在使用println,但他们都在做相同的数量,所以我不认为这会扭曲它,特别是因为差异是可重复的。至于答案,由于我是Java的新手,我现在就让投票决定哪个答案最好。我会尽量在周三之前选择一个。

EDIT2:我今晚要做另一个测试,它不是模量,它只是递增一个变量,当它达到progressCheck时,它将执行一个,然后将该变量重置为0。对于第三个选项。

编辑3.5:

我用了这段代码,下面我将展示我的结果。谢谢大家的精彩帮助!我还尝试将多头的短值与 0 进行比较,因此我的所有新检查都发生在“65536”次,使其在重复中相等。

public class Main {


    public static void main(String[] args) {

        long startNum = 0;
        long stopNum = 1000000000L;
        long progressCheck = 65536;
        final long finalProgressCheck = 50000;
        long date;

        // using a fixed value
        date = System.currentTimeMillis();
        for (long i = startNum; i <= stopNum; i++) {
            if (i % 65536 == 0) {
                System.out.println(i);
            }
        }
        long final1 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();
        //using a variable
        for (long i = startNum; i <= stopNum; i++) {
            if (i % progressCheck == 0) {
                System.out.println(i);
            }
        }
        long final2 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();

        // using a final declared variable
        for (long i = startNum; i <= stopNum; i++) {
            if (i % finalProgressCheck == 0) {
                System.out.println(i);
            }
        }
        long final3 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();
        // using increments to determine progressCheck
        int increment = 0;
        for (long i = startNum; i <= stopNum; i++) {
            if (increment == 65536) {
                System.out.println(i);
                increment = 0;
            }
            increment++;

        }

        //using a short conversion
        long final4 = System.currentTimeMillis() - date;
        date = System.currentTimeMillis();
        for (long i = startNum; i <= stopNum; i++) {
            if ((short)i == 0) {
                System.out.println(i);
            }
        }
        long final5 = System.currentTimeMillis() - date;

                System.out.println(
                "\nfixed = " + final1 + " ms " + "\nvariable = " + final2 + " ms " + "\nfinal variable = " + final3 + " ms " + "\nincrement = " + final4 + " ms" + "\nShort Conversion = " + final5 + " ms");
    }
}

结果:

  • 固定 = 874 毫秒(通常约为 1000 毫秒,但由于它的幂为 2,因此速度更快)
  • 变量 = 8590 ms
  • 最终变量 = 1944 ms(使用 50000 时为 ~1000ms)
  • 增量 = 1904 ms
  • 短路转换 = 679 ms

不足为奇的是,由于缺乏划分,短换算比“快速”方式快23%。这很有趣。如果您需要每256次(或大约在那里)显示或比较一些内容,则可以执行此操作,并使用

if ((byte)integer == 0) {'Perform progress check code here'}

最后一个有趣的说明,在“最终声明的变量”上使用模量,65536(不是一个漂亮的数字)是固定值(慢)的一半速度。在此之前,它以接近相同的速度进行基准测试。


答案 1

您正在测量 OSR(堆栈上替换)存根。

OSR 存根是已编译方法的特殊版本,专门用于在方法运行时将执行从解释模式传输到已编译代码。

OSR 存根不像常规方法那样优化,因为它们需要与解释的帧兼容的帧布局。我已经在以下答案中证明了这一点:123

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

特别是这意味着JIT不会用乘法取代整数除法。(请参阅为什么 GCC 在实现整数除法时使用乘以奇数?对于来自提前编译器的 asm 技巧,当值是内联/常量传播后的编译时常量时,如果启用了这些优化。表达式中的整数文本也由 优化,类似于此处,即使在 OSR 存根中,它也由 JITer 优化。%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


答案 2

@phuclv注释的后续,我检查了JIT1生成的代码,结果如下:

for (除以常量):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 版本:

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)

1 - 使用的 VM 选项: -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,src/java/Main.main


推荐