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

Question

While playing with jmh I came across a weird thing I cannot explain.

@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;
   }
}

The results are below

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

I am running on JDK 1.8.0_101, VM 25.101-b13, Intel(R) Core(TM) i7-4770 CPU @ 3.40GHz (family: 0x6, model: 0x3c, stepping: 0x3)

If I set the const equal to the value or if I set the value to 0xffffffff, nothing changes.

Answer 1

The CPU's DIV and MOD instructions are very expensive, costing 50 cycles or more. When you use a variable divisor, using these instructions is unavoidable. However, when you use a constant divisor, this can be compiled into a short sequence of much cheaper instructions such as MUL, ADD, and SHR.

Hacker's delight, chapter 10 covers several algorithms that solve this problem.

Answer 2

Beware this answer it's only intuition

It's because of the nature of the % operator

In testNModConst() 1230 is less than 12345, so modulus only needs to internally check their size and realize that 12345 is bigger (one operation)

In testConstModN() 12345 is greater than 1230, so modulus will have to do a series of operations (subtraction) to calculate the answer.

It depends on the size of the integer relative to the constant