Java Arrays.sort performance for primitive types and objects

java, performance

Solution

This is not surprising to me at all.

First, you have primitives vs. the indirection of needing to chase references down, the comparisons between two primitives will be faster, etc.

Second, a primitive array will play extremely nicely with the CPU cache. A non-primitive array will not necessarily because there is no guarantee that the referenced objects are contiguous in memory (unlikely) and, additionally, the referrent objects are larger which means that less of them can fit in cache at any one time.

See, in both cases, the values in the arrays will fit in the cache, but the problem with the `Integer[]` is that you still have to leave the cache and hit the memory bus to chase down the references and find them in main memory; those references could be pointing all over the place on the heap. This is going to make the poor CPU just wait and wait as now cache misses become much more likely.

That is, you have this array of primitives like this

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

and these all sit next to each other in memory. When one value is pulled into cache from memory, the neighbors get pulled into the cache too. Quicksort and mergesort operate on contiguous sections of the array, so they benefit very much from the CPU cache being nice here (this is locality of reference)

But when you have an array of `Integer` like this

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

the storage locations for the references are contiguous in memory, so they play nicely with the cache. The problem is the *indirection, the possibility of the referrent `Integer` objects being fragmented in memory and the fact that less of them will fit in the cache. This extra indirection, the fragmentation, and the size issue is what will not play nicely with the cache.

Again, for something like quicksort or mergesort which plays on contiguous sections of the array, this is huge, Huge, HUGE and almost surely accounts for the vast majority of the performance difference.

Have I run it incorrectly?

Yes, please use `System.nanoTime` the next time that you need to do a benchmark. `System.currentTimeMillis` has terrible resolution and is not good for benchmarking.

Problem

I read a few threads here about Arrays.sort using "tuned quick-sort" for primitive types and merge-sort for objects. I did a small test just to prove that but I found is quiet the opposite. ``` 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()); ``` For primitive type array it took 22ms where as for array with objects it took 98ms. My laptop it i7 with 8 cores and 8GB of RAM. Have I run it incorrectly? Many Thanks!

Original source