Tại sao (n mod const) nhanh hơn (const mod n)?

Question

Trong khi chơi với jmh tôi đã gặp một điều kỳ lạ mà tôi không thể giải thích.

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

Kết quả là dưới

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 

Tôi đang chạy trên JDK 1.8.0_101, VM 25,101-b13, Intel (R) Core (TM) i7-4770 CPU @ 3.40GHz (gia đình: 0x6, model: 0x3c, bước: 0x3)

Nếu tôi đặt giá trị bằng giá trị hoặc nếu tôi đặt giá trị thành 0xffffffff, không có gì thay đổi.

Answer 1

của CPU DIV và MOD hướng dẫn là rất tốn kém, chi phí 50 chu kỳ trở lên. Khi bạn sử dụng một ước số biến, sử dụng các hướng dẫn này là không thể tránh khỏi. Tuy nhiên, khi bạn sử dụng ước số không đổi, điều này có thể được biên dịch thành một chuỗi ngắn với các hướng dẫn rẻ hơn nhiều như MUL, ADD và SHR.

Hacker's delight, chapter 10 bao gồm một số thuật toán giải quyết vấn đề này.

Answer 2

Hãy coi chừng câu trả lời này nó chỉ trực giác

Đó là vì bản chất của toán tử %

Trong testNModConst() 1230 ít hơn 12345, vì vậy mô đun chỉ cần nội bộ kiểm tra kích thước của chúng và nhận ra rằng 12345 lớn hơn (một hoạt động)

Trong testConstModN() 12345 lớn hơn 1230, vì vậy modulus sẽ phải thực hiện một loạt phép toán (phép trừ) để tính toán câu trả lời.

Nó phụ thuộc vào kích thước của số nguyên so với hằng số