Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: Trying to repeat experiment 100 times but results vary for elapsed time

  1. #1
    Member
    Join Date
    May 2011
    Posts
    61
    My Mood
    Busy
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Trying to repeat experiment 100 times but results vary for elapsed time

    Hi, I'm trying to time my sorting methods for my class, and I'm unsure why the elapsed time for each one after the first is wrong, I'm updating the start and end times. I'm currently timing my merge sort.

    this is what I do using command lines and save to all the running times to a text file: run_times.txt
    For example: >java Insertion_sort >> run_times.txt

    When I check the run_times.txt I get for example:
    elapsed time: 6000ms

    run time: 1000ms

    run time: 1020ms

    run time: 1080ms

    *I know the running time of approximatley 6000ms is correct, but why are the other times not timed properly. I reset start and end times after the inner for loop done inserting 1,000,000 items. I hope it's a silly mistake I made...

    public static void main(String[] args)
    	{
    		int array = create_array(size);
     
    		long start = 0;
    		long end = 0;
     
    		for ( int j=0; i<50; i++ )//run a total of 50 times
    		{
    			start = System.currentTimeMillis();//restarting time after all 1 000 000 items sorted
     
    			for ( int j = 0; j < 1_000_000; ++j )//turn this into a method, don't do more work by reading values from an array
    				mergeSort(array, 1_000_000);
     
    			end = System.currentTimeMillis();
     
    			System.out.println("Run time: " + (end - start) );
    	}


  2. #2
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Trying to repeat experiment 100 times but results vary for elapsed time

    Quote Originally Posted by IHeartProgramming View Post
    ...
    When I check the run_times.txt I get for example:
    elapsed time: 6000ms

    run time: 1000ms

    run time: 1020ms

    run time: 1080ms

    *I know the running time of approximately 6000ms is correct, but why are the other times not timed properly?
    I scratched my head over the same phenomenon when I started looking at Java a few months ago. Repeated calls should "even out" minor timing differences due to operating system busyness. At least that's the way that I did things with C++. Time slot granularity was different between Linux and Windows, so "minor" variations amounted to a couple of milliseconds on one system and 50 milliseconds on another. Different Linux kernels gave different granularity. None of this amounted to factors of 2 to 4 for successive loops in the same program.

    Well...

    See this paper: Interpreting Java Runtimes

    Not the part about merge sort hashtable, etc. But the part that discusses how the Java Virtual Machine very helpfully isolates you from the hardware and makes precise timing a little problematic.

    Anyhow...

    The JVM loads classes as it needs them. (I'm talking about Java 1.6.0_22 here. Older and newer versions of the JVM might actually differ from my observations.)

    So...

    The first call to whatever routine you are using to sort loads a bunch of class stuff into the JVM. Successive loops with calls to the same class (and underlying classes) have less overhead, so they are faster.

    Bottom line: Using times from loops like yours doesn't always tell you what you would like to know.


    Cheers!

    Z
    Last edited by Zaphod_b; October 21st, 2012 at 10:07 PM.

  3. #3
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,895
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Trying to repeat experiment 100 times but results vary for elapsed time

    Quote Originally Posted by Zaphod_b View Post
    I scratched my head over the same phenomenon when I started looking at Java a few months ago. Repeated calls should "even out" minor timing differences due to operating system busyness. At least that's the way that I did things with C++. Time slot granularity was different between Linux and Windows, so "minor" variations amounted to a couple of milliseconds on one system and 50 milliseconds on another. Different Linux kernels gave different granularity. None of this amounted to factors of 2 to 4 for successive loops in the same program.

    Well...

    See this paper: Interpreting Java Runtimes

    Not the part about merge sort hashtable, etc. But the part that discusses how the Java Virtual Machine very helpfully isolates you from the hardware and makes precise timing a little problematic.

    Anyhow...

    The JVM loads classes as it needs them. (I'm talking about Java 1.6.0_22 here. Older and newer versions of the JVM might actually differ from my observations.)

    So...

    The first call to whatever routine you are using to sort loads a bunch of class stuff into the JVM. Successive loops with calls to the same class (and underlying classes) have less overhead, so they are faster.

    Bottom line: Using times from loops like yours doesn't always tell you what you would like to know.


    Cheers!

    Z
    The reality for modern VM's and computers is actually much more complex, but the same recommendation holds.

    Luckily, there are many good resources for benchmarking Java:

    How do I write a Correct Micro Benchmark in Java?, in particular the first answer highlights the key factors/steps any good micro-benchmarking code should follow.

    The Caliper Project, a benchmarking tool for Java.

    VisualVM - From what I've read it's basically the profiling tool separated from the Netbeans IDE

    For basic benchmarking, here's the general approach i usually take:

    Time the code you want to benchmark several times (I would recommend at least 5 or 10 times, more is better statistically). Optimally you'd want each trial run to be at least 100ms to get rid of any small discrepancies. Use the basic statistical tools such as min/max, standard deviation, mean (average), and median. Sometimes I discard the min/max trials before performing any other analysis such as mean and standard deviation. When benchmarking you want to make sure you have as many background programs closed as possible (not just minimized). The main reason for this is to help get consistent caching, which sometimes is responsible for significant timing differences. If you're standard deviation is rather large, you may want to consider adding more trials, or follow more of the recommendations for the first link I posted about writing a good micro-benchmark in Java.

    edit:

    Two last consideration I forgot to bring up is to run your code in release mode. This allows the compiler/runtime to make certain optimizations it won't in debug mode. Also make sure you're running all trials on the same computer ideally with the same software installed/running.
    Last edited by helloworld922; October 21st, 2012 at 10:52 PM.

  4. The Following User Says Thank You to helloworld922 For This Useful Post:

    Zaphod_b (October 21st, 2012)

  5. #4
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,318
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Trying to repeat experiment 100 times but results vary for elapsed time

    To add to the great advice already received, just a note regarding the code posted: for me it is unclear how the sort is operating on the array, but from what is posted I can make a guess you are passing the same array to the sort method - eg that the array becomes sorted on the first loop iteration and from then on each call to the sort is sorting an already sorted array: in other words you may be measuring the best case time for each of your algorithms (I'm presuming you wish to measure average time - I'll leave it up to you to see if doing so impacts your results dramatically).

  6. The Following User Says Thank You to copeg For This Useful Post:

    helloworld922 (October 22nd, 2012)

Similar Threads

  1. Simple Repeat.
    By Tecness2 in forum Java Theory & Questions
    Replies: 3
    Last Post: May 30th, 2012, 01:35 PM
  2. Replies: 15
    Last Post: November 4th, 2011, 03:52 AM
  3. How to repeat a while loop?
    By BITmixit in forum What's Wrong With My Code?
    Replies: 4
    Last Post: October 12th, 2011, 12:51 PM
  4. How to display the results + repeat to the number entered by user?
    By TheBattousaixx in forum What's Wrong With My Code?
    Replies: 1
    Last Post: September 17th, 2011, 11:56 PM
  5. Wanting to repeat my program...
    By Shaybay92 in forum What's Wrong With My Code?
    Replies: 4
    Last Post: August 8th, 2011, 08:29 AM