6

As part of a school exercise I would like to compare and contrast sorting algorithms as a Java exercise.

I implemented the sorting algorithms myself and we sort objects of a class Person which implements the Comparable interface.

So far so good, but what I can't explain is why during the first call to my sorting methods, the sorting takes longer than on subsequent calls?
The output bellow represents my results.
Best, Worst and Avg refer to the unsorted array that is passed to the sorting method:

  • Best: the array is already sorted
  • Worst: the array is sorted in reverse order
  • Avg: the objects in the array are at random order

This is my output:

1-call of the sorting methods 
InsertionSort Best:1799ms    Worst:78ms  Avg:789ms   
MergeSort     Best:10ms      Worst:3ms   Avg:5ms     

2-call of the sorting methods 
InsertionSort Best:1065ms    Worst:39ms  Avg:691ms   
MergeSort     Best:3ms       Worst:2ms   Avg:5ms     

3-call of the sorting methods 
InsertionSort Best:1066ms    Worst:39ms  Avg:692ms   
MergeSort     Best:3ms       Worst:2ms   Avg:5ms     

4-call of the sorting methods 
InsertionSort Best:1065ms    Worst:39ms  Avg:691ms   
MergeSort     Best:3ms       Worst:2ms   Avg:5ms

Is the JVM doing any optimizations on subsequent calls?
I am puzzled and would greatly appreciate any help!

Edit: Thanks for suggestions and answers so far! To make a few points clear - each of the calls in my output refer to the time it take for a complete sorting!
After each sorting I make a new call with UNSORTED arrays again!

My source code can be downloaded as an eclipse project as a zip file, at the following Dropbox link: dropbox link to eclipse project.zip

P.S. I have no experience with profilers - if you could point me to a tutorial or so that would be great.

Nakilon
  • 34,866
  • 14
  • 107
  • 142
erik.eilif
  • 93
  • 4
  • 2
    Can you post the code? – Alex Weitz Mar 12 '16 at 17:12
  • 4
    Did you re-shuffle your data between runs? – user1676075 Mar 12 '16 at 17:13
  • 2
    This is hard to say without any code; and for example; it might depend on how you do measure. There are quite some pitfalls that one can ran into regarding performance measurement. Sometimes for example, the Java just-in-time compiler does interesting things. – GhostCat Mar 12 '16 at 17:16
  • 1
    I will suggest using a Profiler. – user3437460 Mar 12 '16 at 17:17
  • Hi - yes I am re-shuffling the data between runs – erik.eilif Mar 12 '16 at 18:05
  • I'm flagging this as "unclear what you're asking" because "*Questions seeking debugging help ( "why isn't this code working?" ) must **include the desired behavior, a specific problem or error and the shortest code necessary to reproduce it in the question itself.** Questions without a clear problem statement are not useful to other readers. See: [mcve].*" – cat Mar 13 '16 at 00:11

2 Answers2

8

There are many things at work here, as the variety of responses indicate.

But the first run's long runtime is probably explained by JIT (just-in-time) compilation. As discussed here, your algorithm will run in the JVM for a while as interpreted bytecode. When the Hotspot monitor determines that your sort's loops are costly, the JVM will compile them to native code. After that, they'll run considerably faster. The first run is getting the disadvantage of running in the interpreter for a while plus the extra costs of compilation. This is why "warming up" is a common term in Java benchmarks.

The differences in performance on different inputs are tied to the sort algorithm. Many algorithms behave differently based on initial data organization, and many are deliberately organized to do well on initially sorted or nearly sorted data. Here is a brilliant demonstration for the case of nearly sorted input. E.g. insertion sort is quadratic time in general, but linear time on nearly sorted input (actually O((k+1)n) for input of size n where elements are no more than k positions from correctly sorted).

Then there is the branch prediction issue already referenced by link. Modern processors have various mechanisms that attempt to "guess" which way a branch (essentially an "if" statement at the machine level) will go based on recent history gathered as the program runs. The cost of a bad guess is high. The goodness of the guess is likely to be affected by both algorithm and data details.

Community
  • 1
  • 1
Gene
  • 46,253
  • 4
  • 58
  • 96
6

Processing a sorted array is faster than processing an un-sorted one due to Branch Prediction.
This has been covered extensively in the most famous Stack Overflow question.

Community
  • 1
  • 1
Idos
  • 15,053
  • 14
  • 60
  • 75
  • hi, i know this, but it is not my question! I think you read through my post too quickly. – erik.eilif Mar 12 '16 at 18:24
  • 1
    Hi Erik, I thought that's exactly was the case. If I was (somewhat) wrong I apologize, but from how the question is phrased this seems to be the answer. Branch Prediction is the reason *sorting second time round is faster* (question title verbatim) :) – Idos Mar 12 '16 at 18:28
  • hi Idos, no need to apologize! Maybe my questions is a bit unclear - english is not my native language! I understood you answer that there is a differnence if I try to sort an unsorted or already sorted array - and this i understand! However - are you saying that if I send an unsorted array to a method to sort it, and after it is finished I send the same original UNSORTED array again to the method, then it will be faster due to branch prediction? I dont know much about branch predicition :( – erik.eilif Mar 12 '16 at 18:34