Java Arrays.sort performance for primitive types and objects -

i read few threads here arrays.sort using "tuned quick-sort" primitive types , merge-sort objects. did small test prove found quiet 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 took 22ms array objects took 98ms. laptop i7 8 cores , 8gb of ram. have run incorrectly?

many thanks!

this not surprising me @ all.

first, have primitives vs. indirection of needing chase references down, comparisons between 2 primitives faster, etc.

second, primitive array play extremely nicely cpu cache. non-primitive array not because there no guarantee referenced objects contiguous in memory (unlikely) and, additionally, referrent objects larger means less of them can fit in cache @ 1 time.

see, in both cases, values in arrays fit in cache, problem integer[] still have leave cache , hit memory bus chase down references , find them in main memory; references pointing on place on heap. going make poor cpu wait , wait now cache misses become more likely.

that is, have array of primitives this

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

and these sit next each other in memory. when 1 value pulled cache memory, neighbors pulled cache too. quicksort , mergesort operate on contiguous sections of array, benefit very cpu cache being nice here (this locality of reference)

but when have array of integer this

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

the storage locations references contiguous in memory, they play nicely cache. problem *indirection, possibility of referrent integer objects being fragmented in memory , fact less of them fit in cache. indirection, fragmentation, , size issue not play nicely cache.

again, quicksort or mergesort plays on contiguous sections of array, huge, huge, huge , surely accounts vast majority of performance difference.

have run incorrectly?

yes, please use system.nanotime next time need benchmark. system.currenttimemillis has terrible resolution , not benchmarking.