Dlaczego mój algorytm staje się szybszy po kilkukrotnym wykonaniu? (Java)

Question

Mam algorytm rozwiązywania sudoku, dla którego moim celem jest dokonanie tak szybko, jak to możliwe. Aby przetestować ten algorytm, uruchamiam go wiele razy i obliczam średnią. Po zauważeniu kilka numerów dziwne, postanowiłem wydrukować wszystkie czasy i dostał ten wynik:

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 

po 10 do 15 egzekucji (waha się losowo), wydajność algorytmu jest drastycznie poprawia. Jeśli uruchomię to kilkaset razy, to ostatecznie ustabilizuje się na poziomie około 0.3ms. Zauważ, że uruchamiam algorytm raz przed tą pętlą, aby JIT mógł to zrobić.

Ponadto, jeśli wątek zostanie uśpiony na 2 sekundy przed uruchomieniem pętli, wszystkie moje czasy wynoszą 1ms (+/- 0,2).

Ponadto, jeśli rozwiązałem typowe Sudoku (siatka o przekątnej 1-9) około 500 razy przed moją pętlą, wszystkie moje czasy wynoszą około 0.3ms (+/- 0.02).

Każde rozwiązanie jest identyczne. Wszystkie wartości są resetowane.

Więc moje pytanie jest wiele razy:

-Dlaczego nie za każdym razem rozwiązać poprawę po kolejnych rozwiązuje?

-Dlaczego mam nagły spadek czasu rozwiązywania po 10-15 rozwiązaniach?

Answer 1

To dlatego JIT kompiluje tę metodę po JVM sprawia pewną liczbę częstych połączeń do tej metody. W praktyce metody nie są kompilowane przy pierwszym wywołaniu. Dla każdej metody JVM utrzymuje liczbę połączeń, która jest zwiększana za każdym razem, gdy wywoływana jest metoda. JVM interpretuje metodę, dopóki jej liczba połączeń nie przekroczy JIT compilation threshold. Gdy liczba połączeń osiągnie próg, JIT kompiluje i optymalizuje bytecodes, aby działał szybciej, gdy następnym razem zostanie wywołany przez JVM. Dlatego w twoim przypadku wydajność algorytmu drastycznie poprawia się po każdych 10-15 (przypadkowych) wykonaniach.

Answer 2

Najprawdopodobniej - JVM zoptymalizował wykonanie po kilku uruchomieniach.

Oprócz tego sama aplikacja mogła zrobić coś, co poprawiłoby wyniki wykonania.

Bez szczegółowej wiedzy na temat tego, co należy uruchomić, trudno jest powiedzieć coś bardziej precyzyjnie.

Czy korzystasz z zasobów zewnętrznych - połączeń z bazami danych, kolejki/tematów JMS itp.? Czy używasz buforowania?

Liczy ...