Java Arrays.sort基本类型和对象的性能

Question

我在这里阅读了一些关于Arrays.sort的线程,使用"tuned quick-sort"作为原始类型,并使用merge-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());

对于原始类型数组,它需要22ms,对于带有对象的数组需要98ms.我的笔记本电脑i7配备8核和8GB内存.我运行不正确吗？

非常感谢!

Answer 1

这对我来说并不奇怪.

首先,你有原语与需要追逐引用的间接,两个原语之间的比较会更快,等等.

其次,原始数组将与CPU缓存非常匹配.非基本数组不一定会因为没有保证所引用的对象在存储器(不可能)和连续的,附加地,referrent对象是较大的,这意味着较少的人可以在任何一个时间装入高速缓存.

在这两种情况下,看看数组中的值都适合缓存,但问题Integer[]是你仍然必须离开缓存并点击内存总线来追逐引用并在主内存中找到它们; 那些引用可能指向堆上的所有位置.这将使可怜的CPU等待并等待,因为现在缓存未命中变得更有可能.

也就是说,你有这样的基元数组

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

这些都在记忆中彼此相邻.当一个值从内存中拉入缓存时,邻居也会被拉入缓存.快速排序和归并排序的阵列的邻接的部分工作,让他们受益非常从CPU高速缓存是好的这里多少(这是访问的局部性)

但是当你有一个Integer像这样的阵列

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

引用的存储位置在内存中是连续的,因此它们可以很好地与缓存配合使用.问题是*间接,引用 Integer对象在内存中碎片化的可能性以及它们中较少的适合缓存的事实.这种额外的间接,碎片和大小问题是缓存不能很好地发挥作用的.

同样,对于像在阵列的连续部分上播放的quicksort或mergesort这样的东西,这是巨大的,巨大的,巨大的并且几乎肯定地占据了绝大多数的性能差异.

我运行不正确吗？

是的,请System.nanoTime在下次需要进行基准测试时使用.System.currentTimeMillis具有可怕的分辨率,并不适合基准测试.

Answer 2

你的int []适合你的L2缓存.它大约是4 B*50K,它是200 KB,你的L2缓存是256 KB.这将比您的L3 []运行速度快得多,因为它大约是28 B*50K或1400 KB.

L2缓存(~11个时钟周期)比L3缓存快约4-6倍(约45-75个时钟周期)

我敢打赌,如果你不止一次地运行它,你会得到更好的结果,因为代码会变暖.

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

你可以看到代码升温有多大差异.