Data Structures & Algorithms Lecture Notes

3 November 2010 • 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

References

• Performance, Chapter 7, in The Practice of Programming by Brian Kernighan and Rob Pike, Addison-Wesley, 1999.
• Code-Tuning Strategies and Code-Tuning Techniques (Chapters 25 and 26) in Code Complete, 2nd edition, by Steve McConnell, Microsoft Press, 2004.

---

This page last modified on 12 October 2009.