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

Question

While playing with jmh, I came across a strange thing that 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; } } 

Results 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 a constant to a value or if I set a value to 0xffffffff , nothing changes.

Answer 1

CPU DIV and MOD instructions are very expensive, cost 50 cycles or more. When you use a variable divider, the use of these instructions is inevitable. However, when you use a constant divider, this can be compiled into a shorter sequence of much cheaper instructions such as MUL , ADD and SHR .

Hacking enthusiasm, chapter 10 covers several algorithms that solve this problem.

Answer 2

Beware of this answer only by intuition.

This is due to the nature of the % operator

In testNModConst() 1230 is less than 12345, so the module should only internally check its size and understand that 12345 is larger (one operation)

In testConstModN() 12345 is greater than 1230, therefore, to calculate the response, the module will have to perform a series of operations (subtraction).

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