java - 为什么对随机填充的数组进行排序变得越来越快

Question

在一次编程练习中，我们被告知要实现插入、选择和冒泡排序(用 Java 实现)。 我想测试排序的执行速度，因此我编写了一个循环来随机填充数组并对其进行 10 次排序。前两次排序花费的时间大约是最后 8 次迭代的两倍......为什么？

这里我放置了相关部分的代码

// class fields
public static final int POPULATE_MAX = 1000000000;
public static final int POPULATE_MIN = -1000000000;

public static void populateRandom(int[] toPopulate)
{
    // populate array with random integers within bounds set by class fields
    for (int i = 0; i < toPopulate.length; i++)
    {
        toPopulate[i] = (int)(Math.random() * (POPULATE_MAX - POPULATE_MIN))
            + POPULATE_MIN;
    }
} // end of method populateRandom(int[] toPopulate)

public static void insertionSort(int[] toSort) throws IllegalArgumentException
{
    if (toSort == null)
    {
        throw new IllegalArgumentException();
    }
    if (toSort.length <= 1) return;

    int temp;

    // Index i points to the next unsorted element; assigned to temp
    for (int i = 1; i < toSort.length; i++)
    {
        temp = toSort[i];

        // This loop searches through the sorted portion of the array and
        // determines where to put the aforementioned unsorted element
        for (int j = i - 1; j >= 0; j--)
        {
            if (temp < toSort[j])
            {
                toSort[j + 1] = toSort[j];
                if(j == 0)
                    toSort[j] = temp;
            }
            else
            {
                toSort[j + 1] = temp;
                break;
            } // end of if (temp < toSort[j])
        } // end of for (int j = i - 1; j >= 0; j--)
    } // end of for (int i = 1; i < toSort.length; i++)
} // end of method insertionSort(int[] toSort) throws IllegalArgumentException

public static void main(String[] args)
{
    long time;
    for (int testRun = 0; testRun < 10; testRun++)
    {
        int[] array = new int[100000];
        System.out.print(testRun + "...");
        populateRandom(array);
        time = System.currentTimeMillis();
        insertionSort(array);
        time = System.currentTimeMillis() - time;
        for (int i = 0; i < array.length - 1; i++)
        {
            if (array[i] > array[i+1]) System.out.println(i + ". Bad");
        }
        System.out.println(time + " Done");
    }
    System.out.println("ABS Done");
}

我猜测这与分支预测有关，但我不确定为什么后续排序明显更快。

Answer 1

很可能您的 JVM 在前几次迭代中以解释模式运行，然后它会注意到您重复运行相同的方法并将其编译为 native 代码。如果您调用同一方法的次数更多，甚至可能会导致进一步的优化“启动”。

由于 JVM 以这种方式工作，因此您应该在进行性能测量之前始终预热 JVM。基本上，在循环中多次运行您想要进行基准测试的代码，然后进行测量。 (注意:这应该发生在单个 JVM 进程运行的空间内 - 如果 JVM 退出并再次启动，您将回到第一个位置。)