Data Structures & Algorithms Lecture Notes

29 October 2009 • Performance Measurement in Practice

---

Outline

• Program measurements.

• Statistics

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.

Summary

• Use statistics to quantify and qualify your measurements.

  • And demand the same from others.