Checking Efficiency

Clock/Machine Cycles

Page 1 of 1

4 Replies - 2510 Views - Last Post: 23 March 2010 - 10:18 PM Rate Topic: -----

#1 stauffski  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 210
  • Joined: 03-November 07

Checking Efficiency

Posted 23 March 2010 - 01:03 PM

To those of you who have been programing for even as little as a year, it is fairly safe to say that you have all written a NonrepeatingRandomGenerator. I'm a 5 year programmer and I have decided to come back to the subject. However in this case I have written two completely different classes that accomplish the same non repeating random task. After completion of the two classes I decided to compare their efficiencies. Intially, I started out measuring the elapsed time for each class in equivalent tests. I did this by using the Calendar.getInstance().getTimeInMills() method and referenced the beginning time versus the ending time to calculate the elapsed time. This method works, however, after some thought I realized that this testing method is vulnerable to endogenous error. Background tasks that operate on my computer may inadvertently cause a time to be misrepresented. In a obvious solution to this problem I decided that counting the machine cycles of the thread would be more accurate. However when I attempted to research a way to accomplish this, all I could find was impertinent material... Is anyone familiar with a way to count machine/clock cycles in Java?

Thanks,
Stauffski

Is This A Good Question/Topic? 0
  • +

Replies To: Checking Efficiency

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10807
  • View blog
  • Posts: 40,287
  • Joined: 27-December 08

Re: Checking Efficiency

Posted 23 March 2010 - 01:22 PM

This is a low-level task, for which Java is not designed. Also, the System.currentTimeMillis() and Calendar.getTimeInMillis() methos are updated once every 60 milliseconds (on a Windows machine), so there is a margin of error when using them. You would be better off determining the Big-O of your algorithm, as it is platform independent. You can record ordered pairs based on (input, numSteps) and perform regression tests to determine the best Big-O, or you can take a look at KYA's tutorial on Determing Big-O Notation.
Was This Post Helpful? 1
  • +
  • -

#3 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • Joined: 11-December 07

Re: Checking Efficiency

Posted 23 March 2010 - 07:02 PM

macosnerd101 is absolutely correct but I'd like to suggest an alternative. You can make that 60 ms error margin almost disappear by repeating the runs several times. Use a simple for loop and set it so each algorithm runs for about 10 seconds. If you record the precise time taken and the number of runs, you can easily calculate an accurate time per run.

You can get round the problem of background tasks by repeating the whole experiment. Run each class, then wait for a minute. Run each class again, repeat as necessary -- maybe while you take a shower or eat dinner or take the dog for a walk. Then you can work out some averages and standard deviations or just look and see if there are any suspicious values.

Finally, watch out for the virtual machine's trickery. Typically, it interprets a loop a couple of thousand times and then compiles the bytecode. So, you may want to turn off the JIT compiler (a java command line option) or prime the code by running it a few thousand times, until your test code sees the difference in speed, and then run your test code. It may even be interesting to compare the before JIT and after JIT results.
Was This Post Helpful? 1
  • +
  • -

#4 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8346
  • View blog
  • Posts: 31,910
  • Joined: 06-March 08

Re: Checking Efficiency

Posted 23 March 2010 - 10:15 PM

View Poststauffski, on 23 March 2010 - 02:03 PM, said:

To those of you who have been programing for even as little as a year, it is fairly safe to say that you have all written a NonrepeatingRandomGenerator. I'm a 5 year programmer and I have decided to come back to the subject. However in this case I have written two completely different classes that accomplish the same non repeating random task. After completion of the two classes I decided to compare their efficiencies. Intially, I started out measuring the elapsed time for each class in equivalent tests. I did this by using the Calendar.getInstance().getTimeInMills() method and referenced the beginning time versus the ending time to calculate the elapsed time. This method works, however, after some thought I realized that this testing method is vulnerable to endogenous error. Background tasks that operate on my computer may inadvertently cause a time to be misrepresented. In a obvious solution to this problem I decided that counting the machine cycles of the thread would be more accurate. However when I attempted to research a way to accomplish this, all I could find was impertinent material... Is anyone familiar with a way to count machine/clock cycles in Java?

Thanks,
Stauffski

Hey stauffski long time no see
Your posts were generally really challenging
But I guess macosxnerd101 beat me on that one (probably based on posts I have already done :))
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10807
  • View blog
  • Posts: 40,287
  • Joined: 27-December 08

Re: Checking Efficiency

Posted 23 March 2010 - 10:18 PM

Quote

Then you can work out some averages and standard deviations or just look and see if there are any suspicious values.

Actually, better to use Chi-Square test, as it allows for the ability to look at all values at once, since large Chi-square values means you have a significantly larger value in your results. If you use Chi-Square test, you'll want to compute the ratio between the size of the problem, and the runtime.

You can also run a regression test with (problemSize, runtime) ordered pairs to determine Big-O.

As for turning the JIT compiler off, you are starting to move into platform specific tests, which aren't reliable when determining efficiency, except when comparing algorithms relatively, as very few computers have the exact same configurations and processing speeds. Again, better to use Big-O here, as it provides insights for the true efficiency of code, not platform-specific runtime.

This post has been edited by macosxnerd101: 23 March 2010 - 10:19 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1