java - 了解 Java 对 int 数组的 native 排序为什么/如何在连续排序上进行优化......所以我可以停止它

Question

我的程序简而言之:

我有一个程序可以针对一个整数数组依次运行多个排序算法，并对每个算法进行计时。 GUI 允许用户选择数组大小和各种随机数范围来填充要排序的数组。每次单击“排序”按钮都会获取用户的数组值，构建一个新数组，然后使用 .clone() 为每个排序算法创建该数组的克隆。

问题:

当第二次点击“排序”按钮时，排序会自行改善。

某处发生了我不明白的优化。

这是一个问题的原因:如果用户不更改他们的数组设置并再次运行排序方法，则确实会使用新的随机数构造一个新数组，但随机数范围保持不变，因此运行时间，超过 125k 的列表，应该保持大致相同....而不是提高 300%。

所以这是我所面对的演示程序。它仅使用一种类型，即 Java 的 native 类型来演示该问题。它还使用硬编码值来构造要排序的随机 int 数组 - 但每次“输入”时都会这样做。我认为这个模拟准确地反射(reflect)了我的程序，因为这里也发生了同样的“错误”。

为什么第二次排序更快？

...每次运行都会使用新值重建数组，那么它如何才能变得更快呢？

package sortTooFast;

import java.util.Arrays;
import java.util.Scanner;

public class SortTooFast {
    public static final int ARRAY_SIZE = 500000;
    public static final int MIN_RANGE = 0;
    public static final int MAX_RANGE = 100;
    public static final int INCLUSIVE = 1;
    
    int[] sortingArray;

    public static void main(String[] args) {
        SortTooFast test = new SortTooFast();
        test.run();
    }
    
    // Run program.
    public void run(){
        while(true){    
            
            // Assign int[] filled with random numbers.
            sortingArray = getArray();                  

            // Inform user.
            System.out.println("\nPress return key to run sort!");
            
            // Wait for user.
            new Scanner(System.in).nextLine();
            
            System.out.println("First 15 elements to be sorted:");
            
            // Print a small section of the array; prove not sorted
            for (int i = 0; i < 15; i++){
                System.out.printf("%4d", sortingArray[i]);
            }
            
            // Perform sort.
            runNativeSort(sortingArray);
        }
    }

    // Run native java sort.
    private void runNativeSort(int[] array) {
        // Start timer
        long startTime = System.currentTimeMillis();
        
        // Perform sort.
        Arrays.sort(array);
        
        // End timer
        long finishTime = System.currentTimeMillis();
        
        // Running time.
        long runTime = finishTime - startTime;
        
        // Report run time.
        System.out.println("\nRun time: " +runTime);        
    }

    // Obtain an array filled with random int values.
    private int[] getArray() {
        // Make int array.
        int[] mArray = new int[ARRAY_SIZE];
        
        // Length of array.
        int length = mArray.length;
        
        // Fill array with random numbers.
        for(int counter = 0; counter < length; counter++){
            int random = MIN_RANGE + (int)(Math.random() * ((MAX_RANGE - MIN_RANGE) + INCLUSIVE));
            mArray[counter] = random;
        }
        return mArray;
    }
}

Answer 1

Why is the sort faster the second time?

因为到那时，JIT 已经将字节码优化为更快的 native 代码。

在对此类事物进行基准测试时，您需要应对两种影响:

1. 首先 JIT 代码所花费的时间
2. 随着 JIT 越来越努力地优化 native 代码，它随着时间的推移而改进。

通常，您可以在开始计时之前运行代码足够长的时间以使其完全优化，从而降低这种影响以达到稳定状态。

此外，在进行基准测试时，您应该使用 System.nanoTime 而不是 System.currentTimeMillis:System.currentTimeMillis 旨在为您提供合理的准确的“挂钟”时间，如果操作系统发现时钟不同步，则可能会对其进行调整，而 nanoTime 专门设计用于测量自特定时刻以来耗时，无论更改如何到系统时钟。