为什么 (n mod const) 比 (const mod n) 快？

Question

在玩 jmh 的时候，我遇到了一件我无法解释的怪事。

@BenchmarkMode(Mode.SingleShotTime)
@Measurement(iterations = 10, batchSize = Integer.MAX_VALUE)
@Warmup(iterations = 5, batchSize = Integer.MAX_VALUE)
@State(Scope.Thread)
public class Tests {
    private int value;

    @Setup(Level.Iteration)
    public void setUp() {
        value = 1230;
    }

    @Benchmark
    public boolean testConstModN() {
        return 12345 % value == 0;
    }

    @Benchmark
    public boolean testNModConst() {
       return value % 12345 == 0;
   }
}

结果如下

Benchmark                  Mode  Cnt   Score   Error  Units
Tests.testConstModN          ss   10  10.789 ± 0.305   s/op
Tests.testNModConst          ss   10   7.550 ± 0.067   s/op

我运行 JDK 1.8.0_101，VM 25.101-b13，Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz （系列：0x6，型号：0x3c，步进：0x3）

如果我将 const 设置为等于该值，或者如果我将值设置为 0xffffffff，则没有任何变化。

Answer 1

注意这个答案只是直觉

这是因为 % 运算符的性质

在testNModConst()中1230小于12345，所以modulus只需要在内部检查它们的大小并实现12345更大（一次操作）

在testConstModN()中12345大于1230，所以模数必须做一系列运算（减法）才能计算出答案。

这取决于整数相对于常数的大小

Answer 2

CPU 的 DIV 和 MOD 指令非常昂贵，需要 50 个周期或更多。当您使用可变除数时，使用这些指令是不可避免的。但是，当您使用常数除数时，它可以编译成一个短序列，其中包含更便宜的指令，例如 MUL、ADD 和 SHR.

Hacker's delight, chapter 10 涵盖了解决此问题的几种算法。

为什么 (n mod const) 比 (const mod n) 快？

Why (n mod const) is faster than (const mod n)?

java

x86-64

jmh