5

我在这里阅读了一些关于 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 内存。我运行不正确吗？

非常感谢！

4

3 回答 3

13

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

首先，你有原语与需要追踪引用的间接性，两个原语之间的比较会更快，等等。

其次，原始数组将与 CPU 缓存完美配合。非原始数组不一定是因为不能保证被引用的对象在内存中是连续的（不太可能），此外，引用的对象更大，这意味着它们中的任何时候都不能容纳在缓存中。

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

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

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

这些都在记忆中彼此相邻。当一个值从内存中拉入缓存时，邻居也会被拉入缓存。快速排序和合并排序在数组的连续部分上运行，因此它们从这里的 CPU 缓存中受益匪浅（这是参考的局部性）

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

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

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

同样，对于在数组的连续部分上播放的快速排序或合并排序之类的东西，这是巨大的，巨大的，巨大的，几乎可以肯定地解释了绝大多数的性能差异。

我运行不正确吗？

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

于 2013-08-08T17:06:20.873 回答
10

您的 int[] 适合您的 L2 缓存。它大约是 4 B * 50K，即 200 KB，您的 L2 缓存为 256 KB。这将比将在 L3 缓存中的 Object[] 运行得快得多，因为它的大小约为 28 B * 50K 或 1400 KB。

L2 缓存（约 11 个时钟周期）比 L3 缓存（约 45 - 75 个时钟周期）快 4-6 倍

我敢打赌，如果你不止一次地运行它，随着代码的升温，你会得到更好的结果。

public static void test_int_array() {
    int a[] = new int[50000];
    //Integer a[] = new Integer[50000];

    Random random = new Random();
    for (int i = 0; i < 50000; i++) {
        //a[i] = new Integer(new Random().nextInt(5000));
        a[i] = random.nextInt(5000);
    }
    long start = System.nanoTime();
    Arrays.sort(a);
    long time = System.nanoTime() - start;
    System.out.printf("int[] sort took %.1f ms%n", time / 1e6);
}

public static void test_Integer_array() {
    Integer a[] = new Integer[50000];

    Random random = new Random();
    for (int i = 0; i < 50000; i++) {
        a[i] = random.nextInt(5000);
    }
    long start = System.nanoTime();
    Arrays.sort(a);
    long time = System.nanoTime() - start;
    System.out.printf("Integer[] sort took %.1f ms%n", time / 1e6);
}

public static void main(String... ignored) {
    for (int i = 0; i < 10; i++) {
        if (test_int_array()[0] > 0) throw new AssertionError();
        if (test_Integer_array()[0] > 0) throw new AssertionError();
    }
}

印刷

int[] sort took 32.1 ms
Integer[] sort took 104.1 ms
int[] sort took 4.0 ms
Integer[] sort took 83.8 ms
int[] sort took 33.4 ms
Integer[] sort took 76.7 ms
int[] sort took 4.4 ms
Integer[] sort took 40.5 ms
int[] sort took 3.8 ms
Integer[] sort took 17.4 ms
int[] sort took 4.7 ms
Integer[] sort took 22.4 ms
int[] sort took 4.4 ms
Integer[] sort took 12.1 ms
int[] sort took 3.7 ms
Integer[] sort took 11.2 ms
int[] sort took 3.9 ms
Integer[] sort took 10.7 ms
int[] sort took 3.6 ms
Integer[] sort took 11.9 ms

您可以看到预热代码有多大的不同。

于 2013-08-08T17:07:24.497 回答
0

我运行不正确吗？

您的基准测试非常原始，它并没有真正建立任何东西。对于每种情况，排序时间如何随着数组大小的增加而增长？原始排序和对象排序之间的差异有多少可以归因于比较原始排序和比较对象的不同成本？（这将与排序算法的性能无关，但会通过您的测试归因于排序算法。）

正如其他人所指出的那样，如果您正在计时需要几十毫秒的时间，您应该使用System.nanoTime; System.currentTimeMillis分辨率通常不超过 10 毫秒。然而，简单地切换计时技术并不能解决测试中更严重的问题。

于 2013-08-08T17:11:41.587 回答