Algorithm's execution time evaluation issue

Hello all,
I'm fairly new to the forum so I really hope this is the right section to post my issue :)!

Consider that i have this big array with lets say 1million elements in it, i made a program to sort those elements with BucketSort algorithm using ArrayList to allocate buckets. Everytime I execute (I've made a for cycle) the sorting algorithm's subroutine I evaluate how much time it takes and save the information inside another array. Everything works fine but my question is : why the more times I sort the array the less time it takes??

Let's put it like that :

First sorting call - 10 seconds (just random numbers tho..)
Second sorting call - 5 sec
..
..
..
N-ish sorting call - < 1 sec

It doesn't really makes a lot of sense to me.. are there some Java VM's hidden operation that come into play boosting performances the more times I call a specific subroutine(caching?) or is it related to a better memory access? It can't be bound to the algorithm code, it's always the same and data are always cleaned before a new call.

Ty in advance for your help and sorry for my bad english :).

Is your input the exact same for every call of the algorithm? Bucketsort depends on the content of the items to be sorted as far as I can see. And yes, java appears to be slower at the first start... so maybe it is a feature.

Yes the input is always of the same size, only values change but they are always extracted from a uniform distribution [0,1). The only thing that could happen is that values inside buckets are already correctly sorted so the insertion sort is extremely fast but it cant happen all the times, it's against probability :D!

Seems like this anomaly doesn't happen when I start to sort an array with dim >= 100000 values. But problem is still there, it's kinda ruining my performance evaluation -.-.

Maybe I should ask for more details to Sun itself, I think it's related to how the VM works and allocate data/execute operations.

Timing runs in the VM generally requires you to "warm" it up.
This is because, as you suspect, the VM optimises stuff as it goes.
The first run will always be the slowest, as it's also loading all the classes...
The next few runs will see it optimise the more commonly executed parts of the code.

So how you decide to measure performance really comes down to how your app is used.

If it's something that crunches lots of data in a loop then you'd want to time the algorithm after you've given it a few dozen run throughs.

One thing I learned about Java is that there is nothing like "performance"... ^^
(just joking but with a grain of truth...)
You can't measure/predict memory usage or speed accurately from within.

Java code is difficult to measure w.r.t. speed; there's the JIT (Just In Time) compiler together with the HotSpot mechanism. The JIT compiler compiles byte code to native machine code and the HotSpot mechanism decides which byte code sequences need to be compiled (by the JIT compiler) to machine code. The 'best' (mind the quotes) thing is to 'warm up' your code before you start measuring its performance; i.e. let the code run for a short while first so the HotSpot mechanism wakes up and fires up the JIT compiler so you can be (almost) sure that you're measuring compiled code.

kind regards,

Jos

Thank you very much for your answers, I'll definitely follow your advice to let the code "warm up" and then start storing the information that I need.