Lecture Notes for Advanced Programming II

1 March 2001 - Making Code Efficient

1. there are two kinds of efficiency - conceptual and execution

   1. write conceptually efficient code

   2. then, if necessary, change the code for execution efficiency

2. c++ makes it easy and hard to write efficient code

   1. easy - access to low-level features

   2. hard - complexity, surprising but defined behavior, access to low-level features

   3. c is easier, java is harder

3. the compiler is smarter than you are

   1. you write conceptually simple code, let the compiler write code that executes efficiently

   2. don't help the compiler - register, inline

4. you don't know how your program is executing

   1. a program's detailed dynamic behavior cannot be predicted

   2. you must measure performance to know where to work

   3. writing efficient code is like debugging - find the inefficiencies and fix

   4. you cannot make efficient inherently inefficient algorithms

5. you must write your programs so they can be easily tuned

   1. efficient code is not simple

   2. making code efficient can be complicated

   3. simpler code is easier to make more efficient

6. understand the code's static behavior

   1. you must understand what the code's supposed to do

   2. the code must be well structured and simple

   3. you can't outrun inefficient algorithms

7. run experiments to determine the code's dynamic behavior

   1. you don't know why the code's inefficient

   2. use performance tools to measure the code - statement counts, execution time, memory use

8. change the code from inside out

   1. make the scope of the change as small as possible - 80-20 rule

   2. innermost loops, then procedures, then move out, . . .

   3. don't patch, #ifdef, special case - rewrite

   4. understand the performance of the code you're adding

9. check your results

   1. is the code still correct?

   2. does the code perform better? significantly better?

      1. if so - stop

      2. if not, go back and try again

      3. if you can't get significant improvements, back out

This page last modified on 27 February 2001.