2

I have a Java program that calculates an n-body problem. At every iteration it checks the forces each body exerts on every other body, and then moves them according to the forces.

The bodies always start in the same spot (I have them arranged in a circle, from body 0 to body n), they are always inspected and moved in the same order (from body 0 to n). However, when I run the program 30 times, I get drastically different running times. One running time would be 2,947,188 milliseconds (49 minutes), while another would be 920,967 milliseconds (15 minutes). I'm not surprised by the order of magnitude of these times because I'm using brute force method (O(n^2)) on A LOT of bodies. But I'm wondering why is there such a variance for a deterministic algorithm? if it's the same algorithm time after time, shouldn't the running time be the same (or at least close)?

Before you ask, yes, I'm measuring the time of the thread that does the calculation, not wall-clock time.

Edit - I'm measuring time like this:

ThreadMXBean bean = ManagementFactory.getThreadMXBean();
long startUserTimeNano = bean.getCurrentThreadCpuTime();

// ... Code to do the stuff...

double taskUserTimeNano = (bean.getCurrentThreadCpuTime() - startUserTimeNano);
CPUmillisecondsElapsed += taskUserTimeNano/1000000.0;

Does this measure anything other than the calculation step?

Second Edit - Now I changed it to measure time like this:

ThreadMXBean bean = ManagementFactory.getThreadMXBean();
long startUserTimeNano = bean.getCurrentThreadUserTime();

// ... Code to do the stuff...

double taskUserTimeNano = (bean.getCurrentThreadUserTime() - startUserTimeNano);
CPUmillisecondsElapsed += taskUserTimeNano/1000000.0;

However, the results are still not repeatable. I also tried to run my program with the flag -Xint, and the results were STILL not repeatable.

Is it safe to assume the issue is within the algorithm and multithreading? or can it still be an issue relating to Java?

Rob
  • 45,296
  • 24
  • 122
  • 150
WhiteTiger
  • 758
  • 1
  • 7
  • 21
  • Do the conditions you run under somehow change? – ldog Apr 01 '11 at 18:48
  • 1
    Try an eval copy of JProfiler ? http://www.ej-technologies.com/products/jprofiler/overview.html - you could connect to your prog. Save snapshots of runs, look at memory, cpu utilisation etc. A hunch might be memory & garbage collection is your issue. – David Victor Apr 01 '11 at 18:50
  • You say you are timing just one thread. Are there other threads? – MAK Apr 01 '11 at 18:51

3 Answers3

1

Are you sure that you are measuring the time correctly? There could be many threads that are running inside the jvm that are invisible to you as a user. If you get the system time then you are ignoring the existence of those threads. Also, if you are running any other threads you might be ignoring the time that they add in.

mrK
  • 2,208
  • 4
  • 32
  • 46
1

Benchmarking multi-threaded programs can be challenging due to dynamic compilation, garbage collection, and adaptive optimization. I suggest reading chapter 12 of Brian Goetz's "Java Concurrency in Practice".

Steve Emmerson
  • 7,702
  • 5
  • 33
  • 59
  • Excellent book on concurrency in Java! – J T Apr 01 '11 at 21:08
  • Yes, if he is running on a HotSpot VM, I would say it is something caused by the compiler. I answered a somewhat similar question some time ago: http://stackoverflow.com/questions/3703644/where-is-variablilty-in-stack-consumption-coming-from/3704904#3704904 – gpeche Apr 01 '11 at 22:41
0

Assuming the thread you are timing is just one of many threads, simply getting a diff of the start and end times of the computation in the thread is really not measuring the actual CPU time taken by the thread. It competes with other threads and would have to suspend/wait as other threads run, but you would be counting the time it is waiting as well.

Since the way threads are scheduled may vary, and we have to consider garbage collection as well, the total time taken from start to finish for the thread can vary a lot. But the actual amount of CPU time needed will not vary.

Edit:

I think what you need to measure is the amount of time the thread spent in user mode. This should get rid of time spent waiting for the OS/JVM and only measure the time spent running the in the thread. So, try using getCurrentThreadUserTime.

I found an earlier SO thread about it: Difference between thread user time and thread cpu time in Java

Community
  • 1
  • 1
MAK
  • 26,140
  • 11
  • 55
  • 86