Data Structures & Algorithms Lecture Notes

27 October 2009 • Performance Measurement

---

Outline

An Old Friend

• Algorithm 1.

  StringBuilder read
  
  while str = input.readline()
    read.append(str)
  
  for i = 0 to read.length()
    if read.charAt(i) == '<'
      // process tag
  

Another Old Friend

• Algorithm 2.

  StringBuilder read
  
  while str = input.readline()
    read.append(str)
    for i = 0 to read.length()
      if read.charAt(i) == '<'
        // process tag
        read.setCharAt(i) = ' '
  

• Which algorithm is better?

Measuring Algorithm Performance

• Implement the algorithm and measure the code.

• It’s a definitive judgement.

• But algorithms don’t execute; they’re not code.

  • It requires implementing the algorithm.

• There are other problems too.

Using Performance Measurement

• Compare competing programs.

• Obtain detailed information about a program.

  • Find and help fix non-performance program errors.

• Understand the interaction between hardware and software.

• Characterize support hardware and software properties.

Problems

• Measurements are context dependent.

  • Determining context accurately is difficult.

• Comparing results is hard.

  • Contexts must match to be meaningful.

• Taking meaningful measurements is hard.

Summary