java - 埃拉托色尼筛法算法 N 次运行期间执行时间出现峰值的原因

Question

我用 Java 开发了埃拉托斯特尼筛法算法，我想测量它的性能。

基本上，我运行“核心算法”(不是整个应用程序)5000 次(使用 for 循环)并测量其执行时间。

这是我使用的代码:

int N = 100000;
int m;
long[] microseconds = new long[5000];

for (int k = 0; k < 5000; k++) {
    long start = System.nanoTime();

    // Core algorithm
    boolean[] isPrime = new boolean[N + 1];
    for (int i = 2; i <= N; i++) {
        isPrime[i] = true;
    }

    for (int i = 2; i * i <= N; i++) {
        if (isPrime[i]) {
            for (int j = i; (m = i * j) <= N; j++) {
                isPrime[m] = false;
            }
        }
    }

    long end = System.nanoTime();
    microseconds[k] = (end - start) / 1000;
}

// Output of the execution times on file
PrintWriter writer = null;
try {
    writer = new PrintWriter("ex.txt");
} catch (FileNotFoundException ex) {
    Logger.getLogger(EratosthenesSieve.class.getName()).log(Level.SEVERE, null, ex);
}

// iterate through array, write each element of array to file
for (int i = 0; i < microseconds.length; i++) {
    // write array element to file
    writer.print(microseconds[i]);
    // write separator between array elements to file
    writer.print("\n");
}

// done writing, close writer
writer.close();

结果如下:

正如您所看到的，有一些较大的初始峰值(7913 和 1548)和一些“周期性”峰值。我该如何解释这些尖峰？我已经禁用了互联网连接(硬件板)和所有可能在后台运行的服务(Windows 7；这意味着没有防病毒软件等)。此外，我将 -Xmx 和 -Xms 参数设置为非常大的内存量。所以我基本上是“单独”运行应用程序。

我知道这是一个很难的问题，但如果能提供一些提示，我将不胜感激。

编辑:我已经根据“beny23”建议修改了我的算法，现在不再有周期性峰值。然而，最初出现了一些大的峰值。

或者(N=1000，不再是 N=10000):

Answer 1

很有可能

• 您会因垃圾收集而出现峰值，请使用 -verbose:gc 查看它们何时发生。
• 代码在未预热时运行速度较慢。循环或方法需要调用 10000 次才能触发后台编译。您可以使用
  -XX:CompileThreshold=10000
更改此阈值
• 由于调度程序的工作方式，您的机器将会出现明显的抖动。除非您将线程绑定(bind)到隔离的 CPU，否则仅由于这个原因，您就可能会出现 2-10 毫秒的抖动。 http://vanillajava.blogspot.com/2013/07/micro-jitter-busy-waiting-and-binding.html

我会改变你的循环以避免使用*它在现代CPU上速度很快，但不像+那么便宜

for (int j = i, m = i * i; m <= N; j++, m += i) {