原始类型和对象的 Java Arrays.sort 性能

Question

我在这里阅读了一些关于 Arrays.sort 的文章，对原始类型使用“调整快速排序”，对对象使用合并排序。我做了一个小测试来证明这一点，但我发现恰恰相反。

            int a[] = new int[50000];
    //Integer a[] = new Integer[50000];

    for(int i=0; i<50000; i++) {
        //a[i] = new Integer(new Random().nextInt(5000)); 
        a[i] = new Random().nextInt(5000);
    }
    System.out.println(System.currentTimeMillis());

    Arrays.sort(a);

    System.out.println(System.currentTimeMillis());

对于原始类型数组，它花费了 22 毫秒，而对于带有对象的数组，它花费了 98 毫秒。我的笔记本电脑是 i7，具有 8 个内核和 8GB 内存。我是否运行错误？

非常感谢!

Answer 1

这对我来说一点也不奇怪。

首先，你有原语 vs. 需要追查引用的间接寻址，两个原语之间的比较会更快，等等。

其次，原始数组将非常适合 CPU 缓存。非基本数组不一定是因为不能保证引用的对象在内存中是连续的(不太可能)，此外，referrent 对象更大，这意味着更少 它们中的任何一个都可以在任何时候放入缓存。

请看，在这两种情况下，数组 中的值都将适合缓存，但是 Integer[] 的问题是您仍然必须离开缓存并命中内存总线以追踪引用并在主内存中找到它们；这些引用可能指向堆上的所有地方。这将使可怜的 CPU 只能等待并等待，因为现在缓存未命中的可能性变得更大。

也就是说，你有这样的原语数组

  _   _   _   _       _
 |5| |7| |2| |1| ... |4|

并且这些都在内存中并排放置。当一个值从内存中被拉入缓存时，邻居也被拉入缓存。 Quicksort 和 mergesort 对数组的连续部分进行操作，因此它们非常受益于这里很好的 CPU 缓存(这是 locality of reference)

但是当你有一个像这样的 Integer 数组时

           _               _
     |--->|7|     ______> |1| 
 _   |   _       |   _
| | |_| | | ... |_| | |         _
 |     _ |_____      |________>|4|
 |___>|5|      |    _           
               |__>|2|

引用 的存储位置在内存中是连续的，因此它们 可以很好地与缓存配合使用。问题是 *indirection，referrent Integer 对象在内存中被碎片化的可能性以及它们中的 less 将适合的事实缓存。这种额外的间接寻址、碎片和大小问题将不能很好地与缓存一起使用。

同样，对于在数组的连续部分上运行的快速排序或合并排序之类的东西，这是巨大的，巨大的，巨大的，几乎肯定是性能差异的绝大部分。

Have I run it incorrectly?

是的，请在下次需要进行基准测试时使用System.nanoTime。 System.currentTimeMillis 分辨率很差，不适合基准测试。