Data Structures & Algorithms Lecture Notes

5 November 2010 • Performance Measurement in Practice (in Java)

---

Outline

• Program measurements.
• Statistics
• Java timing tools.

Program Measurements

• The scope of program measurements can cover
  • the whole program from start to finish.
  • selected parts of the program.

Whole Program Measurement

• Start measuring when the program starts, stop when the program ends.
  • This measures everything that happens during execution.
  • Usually at corse-grained measurement resolution.
• Useful for getting a rough idea of what’s going on.

Whole Measurement Tools

• At the worse, find the time, run the program, find the time.

  $ date ; java main <in >/dev/null ; date
  Thu Oct 29 13:15:14 EDT 2009
  Thu Oct 29 13:15:19 EDT 2009
  $ 

• Sometimes the operating system helps.

  $ time java main /dev/null
  real  0m0.247s
  user  0m0.148s
  sys   0m0.060s
  $
  

Program Part Measurements

• Surround the interesting parts of the program with measurements.
  • The after measurement minus the before measurement gives the elapsed measurement.
• Alternative: write a program consisting only of the parts of interest and do whole-program measurement.
  • System overhead may fuzz up the measerments too much.

Statistics

• Rapidly summarize lots of data.
  • Averages, minimum and maximum.
• Provide more meaningful measurements.
  • Quartile ranges, skew.
• Gage measurement quality.
  • Standard deviation, confidence interval.
• Lots of other useful statistics.
  • Experiment design, hypothesis testing, ...

Data Summary

• Reduce many measurements to one or a few numbers to summarize.
  • Mean, median and mode; arithmetic and geometric mean, and so on.
• The arithmetic mean is usually appropriate.
  • Approximately equal, unrelated measurements.
  • The geometric mean is a better summary of performance improvements.

Summary Example

• Five msec timing measurements: 23, 20, 18, 23, 28.

  Arithmetic mean: (23 + 20 + 18 + 23 + 28)/5 = 22.4 msec

• Three execution speedups: 1.2, 4.6, 0.9.

  Arithmetic mean: (1.2 + 4.6 + 0.9)/3 = 2.23

  Geometric mean: ³√(1.2 × 4.6 × 0.9) = 1.7

• Don’t forget to specify n, the measurement count.

Measurement Quality

• Quality measurements should be tightly bunched.

  

• Standard deviations should be small.
  • 63% of the measurements are within one standard deviation of the mean.
• The differences between the minimum and maximum measurements should be small.

Quality Example

• Five measurements: 23, 20, 18, 23, 28.

  Mean: 22.4, standard deviation: 3.4
  Maximum - minimum = 28 - 18 = 10

• Five more measurements: 13, 20, 18, 23, 38.

  Mean: 22.4, standard deviation: 8.5
  Maximum - minimum = 38 - 13 = 25

• In either case, smaller is better.

Elapsed Timing Pattern

• The general pattern for measuring execution time is

  int start = time()
  // execute code
  int elapsed = time() - start
  

• This pattern is common enough that it's best captured in code.

Java Timers

• Java makes it difficult to work with source code in any form.
  • Unlike C, for example.
• The next best thing is to define timer classes that make it easier to measure time.

    Stopwatch sw
  
    sw.start()
    // execute code
    int elapsed = sw.stop()
  

Stopwatch Class

public void 
Class Stopwatch

  start() { 
    startTime = 
      System.currentTimeMillis()
    }

  public int
  stop() { 
    return (int) 
      (System.currentTimeMillis() - startTime)
    }

  private long startTime

See the code.

Example

Stopwatch sw = new Stopwatch()
int perIteration = 0, n = 10

sw.start()
for (int i = 0; i < n; i++)
  // whatever
perIteration = sw.stop()/n

• More iterations provide smoother data, and a change to measure smaller intervals.

Elapsed Time.

• Alternatively, a class could keep track of a sequence of elapsed time measurements.

  public void 
  start() { 
    times.add(System.currentTimeMillis())
    }
  
  public void 
  stop() { 
    final int n = times.size() - 1
    times.set(n, 
      System.currentTimeMillis() - times.get(n))
    }
  
  private Vector<Long> times

Elapsed Time..

public double average()
  long total = 0
  for (long t: times)
    total += t
  return ((double) total)/times.size()

public double stddev()
  long sum = 0, sumSqr = 0
  for (long t: times)
    sum += t
    sumSqr += t*t

  final int n = times.size()
  return Math.sqrt((
    sumSqr - ((double) (sum*sum)/n))/(n - 1))

See the code.

Example

EpisodeTimer et = new EpisodeTimer()
final int n = 10

for (int i = 0; i < n; i++)
  et.start()
  // whatever
  et.stop()

System.out.println(
  et.average() + ", " + et.stddev())

Summary

• Use statistics to quantify and qualify your measurements.
  • And demand the same from others.

---

This page last modified on 12 October 2009.