问题
当用 Java 对一个简单的 QuickSort 实现进行基准测试时,我在绘制的 n vs time
图形中遇到了意想不到的颠簸:
我知道 HotSpot 会在某些方法似乎被大量使用后尝试将代码编译为 native 代码,因此我使用 -XX:+PrintCompilation
运行 JVM。经过反复试验,似乎总是以相同的方式编译算法的方法:
@ 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()
可以帮助我们解决这个问题?
哎呀!绿色函数是 QuickSort 的代码,每次运行之间有 1000 毫秒的内部间隔(附录中有详细信息),而蓝色函数是我们的旧函数(仅供比较)。
首先,给 HotSpot 时间似乎只会让事情变得更糟!也许它只是因为某些其他因素(例如缓存问题)而看起来更糟?
免责声明:我正在对所示图形的每个点运行 1000 次试验,并使用 System.nanoTime()
测量结果。
编辑
在这个阶段,有些人可能想知道使用 sleep()
会如何扭曲结果。我再次运行了 Red Plot(没有本地编译),现在中间有 sleep :
吓人!
附录
这里我展示了我正在使用的 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);
}
}
最佳答案
好吧,看来我自己解决了这个问题。
关于编译代码可能需要一段时间才能生效的想法,我是对的。问题是我实际实现基准测试代码的方式存在缺陷:
if (x > 4 && x < 17)
Thread.sleep(1000);
在这里,我假设唯一“受影响”的区域在 4 到 17 之间,我可以继续,只是对这些值进行 sleep 。根本不是这样。以下情节可能很有启发性:
这里我将原始无编译函数(红色)与另一个无编译函数进行比较,但中间有 hibernate 。如您所见,它们以不同的数量级工作,这意味着混合使用和不使用 sleep 的代码结果将产生不合理的结果,正如我所做的那样。
最初的问题仍未得到解答。是什么导致即使在编译发生后也会出现驼峰?让我们尝试找出答案,在所有得分中 hibernate 1 秒:
这会产生预期的结果。奇怪的驼峰正在发生, native 代码仍然没有启动。
比较 sleep 50ms 和 sleep 1000ms 函数再次产生预期结果:
(灰色的好像还是有点延迟)
关于java - Jvm native 代码编译疯狂 - 即使在编译代码后,我似乎也会在一段时间内遭受奇怪的性能损失。为什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10036280/