Jvm本机代码编译疯狂 - 即使代码编译后,我似乎也遭受了一段时间的奇怪性能惩罚.为什么？

Question

问题

在Java中使用简单的QuickSort实现进行基准测试时,我在n vs time绘制的图形中面临意外的突变:

我知道HotSpot会尝试在某些方法被大量使用之后将代码编译为native.所以我运行了JVM -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()在这里添加几个可以帮助我们解决这个问题？

哎哟! 绿色功能是QuickSort的代码运行,每次运行之间内部为1000ms(附录中的详细信息),而蓝色功能是我们的旧功能(仅用于比较).

在拳头上,给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);
    }
}

Answer 1

好吧,似乎我自己整理了这个问题.

我认为编译代码可能需要一段时间才能完成,这是正确的.问题是我实际实现基准测试代码的方式存在缺陷:

if (x > 4 && x < 17)
    Thread.sleep(1000);

在这里我假设作为唯一的"受影响"区域将在4到17之间,我可以继续,只是对这些值进行睡眠.事实并非如此.以下情节可能具有启发性:

在这里,我将原始的无编译功能(红色)与另一个无编译功能进行比较,但是在中间进行了睡眠.正如您所看到的,它们工作在不同的数量级,这意味着混合使用和不使用睡眠的代码结果将产生不正确的结果,因为我犯了这样的错误.

原来的问题仍然没有答案.甚至在编译之后导致驼峰出现的原因是什么？让我们试着找出这一点,在所有得分点上进行1次睡眠:

这产生了预期的结果.奇怪的驼峰正在发生,原生代码仍未启动.

比较睡眠50ms和睡眠1000ms函数再次产生预期结果:

(灰色似乎仍显示有点延迟)