0

I am developing a java program in which I'm using a big array of instances of a Class. I have to make some calculations for every object of the array (using its Class methods). When I order the array using Arrays.Sort or other methods I notice an increment of the calculation time to perform my computations, that is excluding the time to do the sort!

If I comment the Arrays.sort function, prior to the other computation the time of calculation is about 1 or 2 milliseconds, while uncommenting it increases to 5 or 6 ms.

I have to do this work for huge number of steps (even 300,000) so the increment changes a lot my performances.

Is there any explanation for this strange behaviour?

AncientSwordRage
  • 7,086
  • 19
  • 90
  • 173
Nadir
  • 139
  • 1
  • 3
  • 11
  • Are you using ArrayList ? – Kamen Stoykov Jun 26 '13 at 15:22
  • 2
    Sorting a big array is a lot of work, and it takes time to do that work. – Joni Jun 26 '13 at 15:24
  • @KamenStoykov No, I'm using a normal array (an array of objects of a specific class), i.e., Reaction[] r; – Nadir Jun 26 '13 at 15:26
  • @Joni that is not the problem (the sort took just 160 ms!). The affected time is of the whole program, not the time required for sorting. – Nadir Jun 26 '13 at 15:29
  • 1
    Oh, you mean that the program runs faster if you don't sort the array first? Sounds like it could have something to with the CPU cache... which is basically what Christian says in his answer. – Joni Jun 26 '13 at 15:31
  • possible duplicate of [Why is processing a sorted array faster than an unsorted array?](http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array) – om-nom-nom Jun 26 '13 at 15:50
  • So getting rid of arrays.sort slows you down, is what you're saying? This could be because operating on an ordered Collection is faster than operating on an unordered one (for your specific function). Again, I don't really understand what your seeing, and what your program is meant to do. – higgs241 Jun 26 '13 at 15:24

2 Answers2

5

Here's my best guess, given what little I know about the code:

Objects are usually, though not always, placed on the heap in roughly the order they are allocated. GC will move them around, but there is some chance that the order will be roughly preserved.

Then, when you access each on turn to do calculations on their data, you may end up with roughly linear memory access. Or more importantly, memory access that is somewhat predictable. This makes your CPU caches and memory subsystem more efficient.

If the objects are not allocated in sorted order, and you then sort them, you turn this somewhat predictable memory access into unpredictable random access, which is slower.

Chris Vest
  • 8,642
  • 3
  • 35
  • 43
  • Of course, I am assuming that the call to Arrays.sort is not part of the measured time in either case. – Chris Vest Jun 26 '13 at 15:31
  • Thank you very much, your answer is reasonable. I didn't took into accounts the fact that they are Objects and hence in the Heap space! :) – Nadir Jun 26 '13 at 15:40
  • 1
    Not only linear access in memory (and thus cache works effectively), but also it could be [branch prediction](http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array) – om-nom-nom Jun 26 '13 at 15:52
  • @ChrisVest How can I sort an array of objects keeping a fast access? Have I to create new objects and copy on them the old ones? – Nadir Jun 26 '13 at 17:18
  • First of all, you need to make sure that you actually have a need for more performance. If that is the case, you just have to approach it scientifically by trying things out, measuring their effects, profiling, etc. – Chris Vest Jun 26 '13 at 20:12
  • 1
    Note that this effect might even change in the future, while your program is running. The GC might move objects around your measured effect might change after a couple of GC cycles. You are using a microbenchmark, which is a false measure. If possible, try changing the array of Class to a linked list, since the locality might be better that way. You might also want to read about the train algorithm to get a better understanding of how objects are moved around. – Joa Ebert Jun 27 '13 at 14:39
  • @JoaEbert a linked list can potentially also avoid a reference look-up per step if we can read the reference to the next object directly from the current object, and don't have to look it up in the array. This, however, only works if the linked nodes are the actual objects we want to work on, and not just a couple of references like in java.util.LinkedList. – Chris Vest Jun 27 '13 at 17:42
0

Could you tell us what are you doing exactly. Actually this is just normal array and accessing elements is CONST time.

Let's look at following scenario. Let's look at your unsorted order. You are at element 'i' and u are searching with 'for loop' some other element. If this element comes to be at index 'i+1' this will cost just 1 step. Now let's look at sorted list. The same element which u are looking for won't be at i+1, but somewhere else, which will slow down calculation. I want to say that this is just GUESS cos I do not know the code. It all depends on what exactly u are doing in calculations.

Kamen Stoykov
  • 1,715
  • 3
  • 17
  • 31