为什么(变量1% 变量2 = = 0)效率低下?

我是 Java 的新手,昨晚运行了一些代码,这真的让我很困扰。我正在构建一个简单的程序来显示 for 循环中的每个 X 输出,当我使用 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秒左右。如果你的电脑比我的电脑更有效率,你可能不得不增加或减少 stopNumprogressCheck

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

编辑: 我没想到我的问题这么受欢迎,我很感激所有的答案。我确实在每一半的时间内执行了一个基准测试,低效的代码花费了相当长的时间,1/4秒与10秒左右。虽然他们使用 println,但是他们做的是相同的事情,所以我不认为这会造成很大的偏差,特别是因为这种差异是可重复的。至于答案,由于我是 Java 新手,我将让投票来决定哪个答案是最好的。我会尽量在周三之前挑一个。

编辑2: 今晚我要做另一个测试,它不是模数,而是增加一个变量,当它达到 ProgressCheck 时,它将执行一个,然后将该变量重置为0。第三个选择。

编辑3.5:

我使用了这段代码,下面将显示我的结果。.谢谢你们所有人的帮助!我还尝试将 long 的 short 值与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毫秒
  • Final 变量 = 1944ms (使用50000时为 ~ 1000ms)
  • 增量 = 1904毫秒
  • 短转换 = 679毫秒

不足为奇的是,由于缺乏除法,短转换是23% 的速度比“快”的方式。这很有趣。如果你需要每256次展示或者比较一些东西,你可以这样做,并且使用

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

最后一个有趣的提示,使用65536的“最终声明变量”的模数(不是一个好数字)是速度(比固定值慢)的一半。在此之前,它几乎是以同样的速度进行基准测试。

18355 次浏览

看到上述代码的性能,我也感到惊讶。它是关于编译器根据声明的变量执行程序所花费的时间。在第二个(效率低下的)例子中:

for (long i = startNum; i <= stopNum; i++) {
if (i % progressCheck == 0) {
System.out.println(i)
}
}

您正在执行两个变量之间的模运算。在这里,编译器必须检查 stopNumprogressCheck的值,以便在每次迭代之后进入这些变量所在的特定内存块,因为它是一个变量,其值可能会发生变化。

这就是为什么每次迭代之后,编译器都会到内存位置检查变量的最新值。因此,在编译时,编译器无法创建有效的字节码。

在第一个代码示例中,在一个变量和一个常数值之间执行模运算符,这个常数值在执行过程中不会改变,编译器不需要从内存位置检查该数值的值。这就是为什么编译器能够创建高效的字节码。如果你声明 progressCheckfinalfinal static变量,那么在运行时/编译时编译器知道它是最终变量,它的值不会改变,那么编译器在代码中用 50000替换 progressCheck:

for (long i = startNum; i <= stopNum; i++) {
if (i % 50000== 0) {
System.out.println(i)
}
}

现在您可以看到,这段代码看起来也像第一个(有效的)代码示例。第一个代码的性能和我们上面提到的两个代码将有效地工作。这两个代码示例的执行时间没有太大差别。

@ phuclv 评论的后续工作中,我检查了由 JIT1生成的代码,结果如下:

对于 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

你在测量 OSR (栈上替换)存根。

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

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

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

特别是这意味着 JIT 不能用 乘法代替 整数除法。(如果启用了这些优化,当值是内联/常量传播之后的编译时常量时,请参阅 为什么 GCC 在实现整数除法时使用奇数乘法?了解提前编译器的提前优化技巧。%表达式中右边的整数文字也由 gcc -O0优化,类似于这里的情况,即使在 OSR 存根中也由 JITer 优化。)

但是,如果多次运行相同的方法,第二次和随后的运行将执行完全优化的常规(非 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

divVar的第一次迭代确实要慢得多,因为编译的 OSR 存根效率不高。但是一旦方法从一开始重新运行,就会执行新的无约束版本,该版本利用了所有可用的编译器优化。

正如其他人所指出的,一般模运算需要进行除法。在某些情况下,除法可以(由编译器)替换为乘法。但与加减法相比,这两种方法都很慢。因此,最好的表现可以通过以下方式来预期:

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)或者其他东西只会增加1,你并不关心模数给你的实际余数,只是看看增加1的计数器是否会达到某个值。

另一个“技巧”是使用两次幂的值/极限,例如 progressCheck = 1024;。通过按位 and,即 if ( (i & (1024-1)) == 0 ) {...},可以快速计算出2的幂模。这也应该非常快,并且在某些体系结构上可能比上面的显式 counter表现得更好。