Results 1 to 8 of 8
  1. #1
    EngineerVic is offline Member
    Join Date
    Dec 2012
    Posts
    7
    Rep Power
    0

    Question 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 :).

  2. #2
    Sierra is offline AN21XX
    Join Date
    Mar 2012
    Location
    Munich
    Posts
    297
    Rep Power
    3

    Default Re: Algorithm's execution time evaluation issue

    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.
    I like likes!

  3. #3
    EngineerVic is offline Member
    Join Date
    Dec 2012
    Posts
    7
    Rep Power
    0

    Default Re: Algorithm's execution time evaluation issue

    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!

  4. #4
    EngineerVic is offline Member
    Join Date
    Dec 2012
    Posts
    7
    Rep Power
    0

    Default Re: Algorithm's execution time evaluation issue

    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.

  5. #5
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,949
    Rep Power
    19

    Default Re: Algorithm's execution time evaluation issue

    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.
    Please do not ask for code as refusal often offends.

    ** This space for rent **

  6. #6
    Sierra is offline AN21XX
    Join Date
    Mar 2012
    Location
    Munich
    Posts
    297
    Rep Power
    3

    Default Re: Algorithm's execution time evaluation issue

    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.
    I like likes!

  7. #7
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,436
    Blog Entries
    7
    Rep Power
    20

    Default Re: Algorithm's execution time evaluation issue

    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
    cenosillicaphobia: the fear for an empty beer glass

  8. #8
    EngineerVic is offline Member
    Join Date
    Dec 2012
    Posts
    7
    Rep Power
    0

    Default Re: Algorithm's execution time evaluation issue

    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.

Similar Threads

  1. Best way to Time Execution
    By tabchas in forum New To Java
    Replies: 2
    Last Post: 06-13-2011, 09:20 AM
  2. threading execution time question
    By centenial in forum Threads and Synchronization
    Replies: 4
    Last Post: 09-09-2010, 05:49 AM
  3. Need help with Process execution time display
    By murali18 in forum New To Java
    Replies: 5
    Last Post: 03-18-2010, 11:19 PM
  4. Replies: 25
    Last Post: 06-28-2008, 05:08 PM
  5. Method execution time
    By javaplus in forum Advanced Java
    Replies: 3
    Last Post: 11-26-2007, 09:51 AM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •