为什么 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 {&nbsp; &nbsp; @Benchmark&nbsp; &nbsp; public void divConst(Blackhole blackhole) {&nbsp; &nbsp; &nbsp; &nbsp; long startNum = 0;&nbsp; &nbsp; &nbsp; &nbsp; long stopNum = 100000000L;&nbsp; &nbsp; &nbsp; &nbsp; for (long i = startNum; i <= stopNum; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (i % 50000 == 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; blackhole.consume(i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; @Benchmark&nbsp; &nbsp; public void divVar(Blackhole blackhole) {&nbsp; &nbsp; &nbsp; &nbsp; long startNum = 0;&nbsp; &nbsp; &nbsp; &nbsp; long stopNum = 100000000L;&nbsp; &nbsp; &nbsp; &nbsp; long progressCheck = 50000;&nbsp; &nbsp; &nbsp; &nbsp; for (long i = startNum; i <= stopNum; i++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (i % progressCheck == 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; blackhole.consume(i);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}结果：# Benchmark: bench.Div.divConst# Run progress: 0,00% complete, ETA 00:00:16# Fork: 1 of 1# Warmup Iteration&nbsp; &nbsp;1: 126,967 ms/op# Warmup Iteration&nbsp; &nbsp;2: 105,660 ms/op# Warmup Iteration&nbsp; &nbsp;3: 106,205 ms/opIteration&nbsp; &nbsp;1: 105,620 ms/opIteration&nbsp; &nbsp;2: 105,789 ms/opIteration&nbsp; &nbsp;3: 105,915 ms/opIteration&nbsp; &nbsp;4: 105,629 ms/opIteration&nbsp; &nbsp;5: 105,632 ms/op# Benchmark: bench.Div.divVar# Run progress: 50,00% complete, ETA 00:00:09# Fork: 1 of 1# Warmup Iteration&nbsp; &nbsp;1: 844,708 ms/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <-- much slower!# Warmup Iteration&nbsp; &nbsp;2: 105,893 ms/op&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <-- as fast as divConst# Warmup Iteration&nbsp; &nbsp;3: 105,601 ms/opIteration&nbsp; &nbsp;1: 105,570 ms/opIteration&nbsp; &nbsp;2: 105,475 ms/opIteration&nbsp; &nbsp;3: 105,702 ms/opIteration&nbsp; &nbsp;4: 105,535 ms/opIteration&nbsp; &nbsp;5: 105,766 ms/op由于 OSR 存根编译效率低下，第一次迭代divVar确实慢得多。但是，只要方法从头开始重新运行，就会执行新的不受约束的版本，该版本会利用所有可用的编译器优化。

Answer 2

在跟进@phuclv comment时，我检查了JIT 1生成的代码，结果如下：对于variable % 5000（除以常数）：mov&nbsp; &nbsp; &nbsp;rax,29f16b11c6d1e109himul&nbsp; &nbsp; rbxmov&nbsp; &nbsp; &nbsp;r10,rbxsar&nbsp; &nbsp; &nbsp;r10,3fhsar&nbsp; &nbsp; &nbsp;rdx,0dhsub&nbsp; &nbsp; &nbsp;rdx,r10imul&nbsp; &nbsp; r10,rdx,0c350h&nbsp; &nbsp; ; <-- imulmov&nbsp; &nbsp; &nbsp;r11,rbxsub&nbsp; &nbsp; &nbsp;r11,r10test&nbsp; &nbsp; r11,r11jne&nbsp; &nbsp; &nbsp;1d707ad14a0h对于variable % variable：mov&nbsp; &nbsp; &nbsp;rax,r14mov&nbsp; &nbsp; &nbsp;rdx,8000000000000000hcmp&nbsp; &nbsp; &nbsp;rax,rdxjne&nbsp; &nbsp; &nbsp;22ccce218edhxor&nbsp; &nbsp; &nbsp;edx,edxcmp&nbsp; &nbsp; &nbsp;rbx,0ffffffffffffffffhje&nbsp; &nbsp; &nbsp; 22ccce218f2hcqoidiv&nbsp; &nbsp; rax,rbx&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;; <-- idivtest&nbsp; &nbsp; rdx,rdxjne&nbsp; &nbsp; &nbsp;22ccce218c0h因为除法总是比乘法花费更长的时间，所以最后一个代码片段的性能较低。爪哇版：java version "11" 2018-09-25Java(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++){&nbsp; &nbsp; if (--counter == 0) {&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(i);&nbsp; &nbsp; &nbsp; &nbsp; counter = progressCheck;&nbsp; &nbsp; }}（作为一个小的优化尝试，我们在这里使用一个预递减递减计数器，因为在许多架构上0，与算术运算之后的立即比较成本正好为 0 指令/CPU 周期，因为 ALU 的标志已经由前面的操作适当地设置。一个体面的优化但是，即使您编写了 .，编译器也会自动进行优化if (counter++ == 50000) { ... counter = 0; }。）i请注意，您通常并不真正想要/需要模数，因为您知道循环计数器（如果加一计数器达到某个值。另一个“技巧”是使用二次幂值/限制，例如progressCheck = 1024;. 模数 2 的幂可以通过按位快速计算and，即if ( (i & (1024-1)) == 0 ) {...}. 这也应该很快，并且在某些架构上可能会优于上面的显式counter。