Computer Algorithms II Lecture Notes

25 September 2007 • Program Measurement

Outline

• Why measure?

• Measurement types.

• Measuring tools.

• What to measure.

• What to do with measurements.

Measurement Types

• Two possible measurement strategies are

  1. make a few accurate measurements, or

  2. make many inaccurate measurements.

Accurate Measurements

• Accurate measurements are, in some sense, definitive.

• However, accurate measurements are

  • Difficult and expensive to make.

  • Influenced by context.

Inaccurate Measurements

• Without question, inaccurate measurements are less useful than accurate measurements.

• But, inaccurate measurements are easier and cheaper to make than accurate measurements.

Statistical Measures

• Inaccurate measurements can be improved and made useful using statistics.

• There's lots of applicable statistics, but the two simplest and usful are average and standard deviation.

  • There's also lots of rules covering apropriate statistical use.

  • Dangerously, these will be left implicit and assumed to hold.

Average Measures

• There are lots of averages: mean, median, mode, and so on.

  • For our purposes, the mean is the most useful.

• There are lots of means: arithmetic, geometric, and so on.

  • For our purposes, the arithmetic mean is the most useful.

Arithmetic Mean

• Given a set of n > 0 measurements, the (unweighted) arithmetic mean is

  (the sum of the measurements)/n

Error Measurements

• Useful inaccurate mesaurements should include a measure of inaccuracy (or error).

• There are many, many measures of error.

• We are interested in the spread of the measurements.

  • The more spread out the measurements are, the more inaccurate they are.

  • “Spread” is measured as

    spread = (maximum measurement) - (minimum measurement)

• The arithmetic mean does not measure spread; in fact, it hides it.

Standard Deviation

• The standard deviation of a set of measures provides an indication of measure spread.

• The standard deviation is the (arithmetic) mean of the distance between measures and their (arithmetic) mean.

  double stddev(int a, unsigned n)
  
    assert n > 1
  
    const double mean = mean(a, n)
    double stddev = 0.0
  
    for i = 1 to n
      d = a[i] - mean
      stddev += d*d
  
    return sqrt(stddev/(n - 1))
  

Interpreting Standard Deviation

• As a measure of spread, the smaller (relative to the mean) the standard deviation, the better.

• Examples:

  • Mean 100, standard deviation 5: good.

  • Mean 100, standard deviation 10: ok.

  • Mean 100, standard deviation 50: bad.

• Chebyshev's Inequality: 75% of the measurements are within two standard deviations of the mean.

Troubleshooting

• High standard deviations indicate poor quality measurements.

  • There's too much variability to have meaningful data.

• Two obvious problem sources:

  1. Measuring the wrong characteristic.

     • In particulary, measuring a characteristic that's independent of problem size.

  2. Measuring too many influences.

     • Measuring not only your program, but other programs too.

• Of the two, the second is the more likely problem.

  • And the more difficult to get rid of.

  • Finding a quiesent system is tough.

  • But: don't watch videos while taking measurements.

Summary

• Take a bunch of fast, cheap, but inaccurate measurements.

• Summarize the measurements using the arithmetic mean.

• Characterize the error using standard deviation.

• Measure on isolated systems to improve the results.

Measuring Tools

• Most operating systems provide calls for the basic units of interest.

  • In Unix, it's gettimeofday for time, debugging malloc routines for space.

  • These kinds of system calls tend to be system specific.

• The operating system or third parties may provide higher-level tools.

  • The Unix time command.

    $ time anagram star
    arts
    rats
    star
    tars
    tsar
    
    real    0m0.334s
    user    0m0.232s
    sys     0m0.008s
    
    $
    

Stopwatch

class stopwatch

  unsigned elapsed()
  void start()
  void stop()

• See the code.

• Example use.

  stopwatch sw
  
  sw.start()
  for i = 1 to n
    f()
  sw.stop()
  
  printf("%g\n", sw.elapsed()/((double) n));
  

Episode Timer

class episode_timer

  episode_timer(unsigned size = 1024)

  void start(void)
  void stop(void)
  void clear()

  double stddev()
  double average()

  unsigned total()
  unsigned count()

• See the code.

• Example use.

  episode_time et
  
  for i = 1 to n
    et.start()
    f()
    et.stop()
  
  printf("%g (%g)\n", et.average(), et.stddev());