0

我用 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）和一些“周期性”尖峰。我该如何解释这些尖峰？我已经禁用了 Internet 连接（硬件板）和所有可能在后台运行的服务（Windows 7；这意味着没有防病毒等）。此外，我将 -Xmx 和 -Xms 参数设置为非常大的内存量。所以我基本上是“单独”运行应用程序。

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

编辑：我已经根据“beny23”的建议修改了我的算法，现在不再有周期性的尖峰。然而，有一些很大的初始峰值。 在此处输入图像描述

或者（N=1000 而不再是 N=10000）： 在此处输入图像描述

4

1 回答 1

1

最有可能的

  • 由于垃圾收集，您会出现峰值，请使用-verbose:gc它们来查看它们何时发生。
  • 代码未预热时运行速度较慢。一个循环或方法需要被调用 10000 次才能触发后台编译。您可以使用更改此阈值
    -XX:CompileThreshold=10000
  • 由于调度程序的工作方式，您的机器会有很大的抖动。除非您将线程绑定到一个隔离的 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) {
于 2013-11-13T13:07:02.970 回答