为什么我的算法在执行几次后变得更快？ （JAVA） [英] Why does my algorithm become faster after having executed several times? (Java)

问题描述

我有一个数独求解算法，我的目标是尽可能快地制作。为了测试这个算法，我多次运行它并计算平均值。在注意到一些奇怪的数字之后，我决定打印所有时间并得到这个结果：

I have a Sudoku solving algorithm for which my goal is to make as fast as possible. To test this algorithm, I run it multiple times and calculate the average. After noticing some weird numbers, I decided to print all times and got this result:

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

Afte r 10到15次执行（随机变化），算法的性能大大提高。如果我跑了几百次，最终会稳定在0.3ms左右。请注意，我在此循环之前运行算法一次，以便JIT执行此操作。

After 10 to 15 executions (it varies randomly), the performance of the algorithm is drastically improves. If I run it several hundred times, it will eventually steady at around 0.3ms. Note that I run the algorithm once before this loop for JIT to do it's thing.

此外，如果我在运行循环之前使线程休眠2秒，那么我的所有时间是1ms（+/- 0.2）。

Furthermore, if I make the thread sleep for 2 seconds before running my loop, all my times are at 1ms (+/- 0.2).

此外，如果我在循环之前解决了一个普通数独（对角线1-9的网格）约500次，我的所有时间都在0.3ms左右（+/- 0.02）。

Furthermore, if I solved a generic Sudoku (a grid with 1-9 diagonally) some 500 times before my loop, all my times are around 0.3ms (+/- 0.02).

每个解决方案都是相同的。重置所有值。

Every solve is identical. All values are reset.

所以我的问题是多方面的：

So my question is many-fold:

- 为什么每个解决时间都会改善连续解决后？

-Why does each solve time improve after consecutive solves?

- 为什么10-15解决后解决时间会突然下降？

-Why do I have a sudden drop in solve time after 10-15 solves?

推荐答案

这是因为 JIT 在 JVM 对该方法进行一定数量的频繁调用之后编译该方法。实际上，方法在第一次调用时不会被编译。对于每个方法，JVM维护一个调用计数，每次调用该方法时都会递增。 JVM解释方法，直到其调用计数超过 JIT编译阈值。当调用计数达到阈值时， JIT 编译并优化字节码，以便下次调用时运行速度更快通过 JVM 。因此，在您的情况下，每执行10到15次（随机）后，算法的性能会大幅提升。

This is because JIT is compiling that method after JVM makes certain number of frequent calls to that method. In practice methods are not compiled the first time they are called. For each method JVM maintains a call count ,which is incremented every time the method is called. The JVM interprets a method until its call count exceeds a JIT compilation threshold. As the call count reaches threshold , JIT compiles and optimizes the bytecodes so that it run faster when next time it is called by JVM. Therefore, in your case the performance of the algorithm is drastically improving after every 10 to 15(at random) executions.

这篇关于为什么我的算法在执行几次后变得更快？ （JAVA）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！