Java中的时间混淆问题

Question

在我参与的一个项目中，我负责记录两种不同搜索算法的搜索时间：二分查找和顺序查找。对于每个算法，我都要记录排序输入和未排序输入的时间。当我将排序后的输入和未排序输入进行顺序查找的搜索时间比较时，我发现了一些奇怪的问题。根据我先对哪一个进行排序，搜索时间将会明显大于另一个。因此，如果我先对已排序的进行顺序查找，则花费的时间将比在未排序的上进行的顺序查找多得多。

这让我感到困惑，也是我的疑惑所在。由于关键词是从输入中获取的（通过顺序搜索），所以可以保证在数据输入中找到这些关键词。

以下是引起问题的代码。在这种情况下，seqOnUnsorted的搜索时间将远远大于seqOnSorted，但实际上不应该如此。

public void sequentialSearchExperiment(){
    seqOnUnsorted = sequentialSearchSet(keys, unsortedArray);
    writeOutExperimentResults(seqOnUnsorted, seqOnUnsortedFilename, "Sequential Sort on Unsorted: ");

    seqOnSorted = sequentialSearchSet(keys, sortedArray);
    writeOutExperimentResults(seqOnSorted, seqOnSortedFilename, "Sequential Sort on Sorted: ");

}

sequentialSearchSet() 方法如下：

public SearchStats[] sequentialSearchSet(int[] keys, int[] toSearch){
    SearchStats[] stats = new SearchStats[keys.length];

    for (int i = 0; i < keys.length; i++){
        stats[i] = sequentialSearch(keys[i], toSearch);
    }

    return stats;
}

这里是sequentialSearch()函数：

public SearchStats sequentialSearch(int key, int[] toSearch){

    long startTime = System.nanoTime(); // start timer

    // step through array one-by-one until key found
    for (int i = 0; i < toSearch.length; i++){
        if (toSearch[i] == key){
            return new SearchStats(key, i, System.nanoTime() - startTime);
        }
    }

    // did not find key
    return new SearchStats(key, -1, System.nanoTime() - startTime);
}

以下是SearchStats构造函数：

public SearchStats(int keySearchedFor, int indexOfFound, long searchTime){
    this.keySearchedFor = keySearchedFor;
    this.indexOfFound = indexOfFound;
    this.searchTime = searchTime;
}

如果我进行测试运行，我得到的平均搜索时间是:

sequential search on sorted: 21,080 ns
sequential search on unsorted: 2,137,465 ns

正如你所看到的，因为我先在未排序的列表中进行了搜索，所以搜索时间显著较长。有人能解释一下这是为什么吗？此外，我该如何避免这种奇怪的情况呢？

- jtan

---

尝试反复运行测试，直到您看不到任何性能改进为止。通常需要运行10,000次方法/循环才能完全优化。搜索“-XX：CompileThreshold =”选项以获取更多详细信息。 - Peter Lawrey

Answer 1

这是由于虚拟机“预热”的原因。简要概述一下，现代虚拟机将常见代码路径编译为本机代码，并在运行时对其进行优化。因此，在循环的前几次迭代中，代码正在被解释执行，比优化后的代码慢几个数量级。

这是Java性能剖析时的常见问题，通常的解决方法是在执行任何测试之前多次运行待测代码（数百万次）。

有关更多详细信息和建议，请阅读一个有缺陷的微基准测试的剖析。

- Andrzej Doyle

---

另外，最好不要在热身之后单次循环运行计时，而是进行多次运行并取测量值的平均值。这可以减少类似操作系统中的其他进程抢占CPU时间等你无法控制的问题。总体而言，最好使用分析器来检查这种情况，这样您只能获取分配给JVM实际时间的方法计时。 - G_H

谢谢！那解释了一切。 - jtan

Answer 2

微基准测试很难：http://www.ibm.com/developerworks/java/library/j-jtp02225/index.html

- ptyx