问题
在用 Java 对一个简单的 QuickSort 实现进行基准测试时，我在n vs time绘制的图形中遇到了意想不到的问题：
我知道 HotSpot 在某些方法似乎被大量使用后会尝试将代码编译为本机，因此我使用-XX:+PrintCompilation. 经过反复试验，它似乎总是以相同的方式编译算法的方法：
@ iteration 6 -> sorting.QuickSort::swap (15 bytes)
@ iteration 7 -> sorting.QuickSort::partition (66 bytes)
@ iteration 7 -> sorting.QuickSort::quickSort (29 bytes)
我用这个添加的信息重复上面的图形，只是为了让事情更清楚一点：
在这一点上，我们都必须问自己：为什么在编译代码之后我们仍然会遇到那些丑陋的驼峰？也许它与算法本身有关？当然可以，幸运的是，我们有一种快速的方法来解决这个问题，使用-XX:CompileThreshold=0：
无赖！它确实必须是 JVM 在后台执行的操作。但是什么？我推测，虽然代码正在编译，但可能需要一段时间才能真正开始使用已编译的代码。也许在这里和那里添加几个Thread.sleep()s 可以帮助我们解决这个问题？
哎哟! 绿色函数是 QuickSort 的代码，每次运行之间的内部间隔为 1000 毫秒（详见附录），而蓝色函数是我们的旧函数（仅用于比较）。
首先，给 HotSpot 时间似乎只会让事情变得更糟！也许它看起来只是因为其他一些因素而变得更糟，比如缓存问题？
免责声明：我正在对所示图形的每个点进行 1000 次试验，并System.nanoTime()用于测量结果。
编辑
在这个阶段，你们中的一些人可能想知道使用sleep()可能会如何扭曲结果。我再次运行 Red Plot（没有本地编译），现在中间有睡眠：
可怕的！
附录
在这里我展示QuickSort我正在使用的代码，以防万一：
public class QuickSort {
public <T extends Comparable<T>> void sort(int[] table) {
quickSort(table, 0, table.length - 1);
}
private static <T extends Comparable<T>> void quickSort(int[] table,
int first, int last) {
if (first < last) { // There is data to be sorted.
// Partition the table.
int pivotIndex = partition(table, first, last);
// Sort the left half.
quickSort(table, first, pivotIndex - 1);
// Sort the right half.
quickSort(table, pivotIndex + 1, last);
}
}
/**
* @author http://en.wikipedia.org/wiki/Quick_Sort
*/
private static <T extends Comparable<T>> int partition(int[] table,
int first, int last) {
int pivotIndex = (first + last) / 2;
int pivotValue = table[pivotIndex];
swap(table, pivotIndex, last);
int storeIndex = first;
for (int i = first; i < last; i++) {
if (table[i]-(pivotValue) <= 0) {
swap(table, i, storeIndex);
storeIndex++;
}
}
swap(table, storeIndex, last);
return storeIndex;
}
private static <T> void swap(int[] a, int i, int j) {
int h = a[i];
a[i] = a[j];
a[j] = h;
}
}
以及我用来运行我的基准测试的代码：
public static void main(String[] args) throws InterruptedException, IOException {
QuickSort quickSort = new QuickSort();
int TRIALS = 1000;
File file = new File(Long.toString(System.currentTimeMillis()));
System.out.println("Saving @ \"" + file.getAbsolutePath() + "\"");
for (int x = 0; x < 30; ++x) {
// if (x > 4 && x < 17)
// Thread.sleep(1000);
int[] values = new int[x];
long start = System.nanoTime();
for (int i = 0; i < TRIALS; ++i)
quickSort.sort(values);
double duration = (System.nanoTime() - start) / TRIALS;
String line = x + "\t" + duration;
System.out.println(line);
FileUtils.writeStringToFile(file, line + "\r\n", true);
}
}
