Tại sao thuật toán của tôi trở nên nhanh hơn sau khi thực hiện nhiều lần? (Java)

Question

Tôi có một thuật toán giải Sudoku mà mục tiêu của tôi là thực hiện càng nhanh càng tốt. Để kiểm tra thuật toán này, tôi chạy nó nhiều lần và tính trung bình. Sau khi nhận thấy một số con số lạ, tôi quyết định để in tất cả các lần và nhận được kết quả này:

Execution Time : 4.257746 ms (#1) 
Execution Time : 7.610686 ms (#2) 
Execution Time : 6.277609 ms (#3) 
Execution Time : 7.595707 ms (#4) 
Execution Time : 7.610131 ms (#5) 
Execution Time : 5.011104 ms (#6) 
Execution Time : 3.970937 ms (#7) 
Execution Time : 3.923783 ms (#8) 
Execution Time : 4.070238 ms (#9) 
Execution Time : 4.765347 ms (#10) 
Execution Time : 0.818264 ms (#11) 
Execution Time : 0.620216 ms (#12) 
Execution Time : 0.679021 ms (#13) 
Execution Time : 0.643516 ms (#14) 
Execution Time : 0.718408 ms (#15) 
Execution Time : 0.744481 ms (#16) 
Execution Time : 0.760569 ms (#17) 
Execution Time : 0.80384 ms (#18) 
Execution Time : 0.75946 ms (#19) 
Execution Time : 0.802176 ms (#20) 
Execution Time : 66.032508 ms : average = 3.3016254000000003 

Sau 10 đến 15 hành (nó thay đổi một cách ngẫu nhiên), hiệu suất của thuật toán là đáng kể cải thiện. Nếu tôi chạy nó vài trăm lần, nó sẽ ổn định vào khoảng 0.3ms. Lưu ý rằng tôi chạy thuật toán một lần trước vòng lặp này cho JIT để làm điều đó.

Hơn nữa, nếu tôi làm cho luồng ngủ trong 2 giây trước khi chạy vòng lặp của tôi, tất cả thời gian của tôi là 1ms (+/- 0,2).

Hơn nữa, nếu tôi giải quyết một Sudoku chung (một lưới với 1-9 theo đường chéo) một số 500 lần trước vòng lặp của tôi, tất cả thời gian của tôi là khoảng 0,3ms (+/- 0,02).

Mọi giải pháp đều giống nhau. Tất cả các giá trị được đặt lại.

Vì vậy, câu hỏi của tôi là nhiều lần:

-Tại sao mỗi lần giải quyết được cải thiện sau khi giải quyết liên tiếp?

-Tại sao tôi có thời gian giải quyết đột ngột sau 10-15 lần giải quyết?

Answer 1

Điều này là do JIT đang soạn thảo phương pháp mà sau JVM làm cho số lượng nhất định các cuộc gọi thường xuyên với phương pháp đó. Trong phương pháp thực hành không được biên dịch lần đầu tiên chúng được gọi. Đối với mỗi phương thức, JVM duy trì một số lượng cuộc gọi, được tăng lên mỗi khi phương thức được gọi. JVM diễn giải một phương thức cho đến khi số lượng cuộc gọi của nó vượt quá JIT compilation threshold. Khi số lượng cuộc gọi đạt đến ngưỡng, JIT biên dịch và tối ưu hóa bytecodes để nó chạy nhanh hơn khi lần sau được gọi là JVM. Vì vậy, trong trường hợp của bạn, hiệu suất của thuật toán được cải thiện đáng kể sau mỗi 10 đến 15 lần thực hiện ngẫu nhiên.

Answer 2

Rất có thể - JVM đã tối ưu hóa việc thực thi sau một vài lần chạy.

Ngoài ra, bản thân ứng dụng có thể đã thực hiện điều gì đó đã cải thiện kết quả thực hiện.

Nếu không biết chi tiết những gì bạn chạy thì khó nói điều gì đó chính xác hơn.

Bạn có sử dụng tài nguyên bên ngoài - kết nối cơ sở dữ liệu, hàng đợi/chủ đề JMS, v.v. không? Bạn có sử dụng bộ đệm ẩn không?

Tất cả những gì quan trọng ...