When you are first learning to program in a language your emphasis is usually on correctness, that is, getting your programs to run and return accurate and error-free results – and rightly so. There is little point in trying to speed up a program that returns incorrect answers! You develop your programs, prototyping with simple inputs so that you can see at a glance how things are progressing. At some point in the development process you start to increase the size or complexity of the inputs to your program and, if all goes well, the program scales well. But commonly, there are bottlenecks at various stages of the computation that slow things down. Some of these may be unavoidable, but often you can find optimizations that improve the efficiency and running time of your programs. This chapter introduces some of the optimization principles to think about both during the development process and after they are complete and you are satisfied that they produce the desired output.

There are two measures we will focus on – timing and memory footprint. Sometimes one plays a more prominent role than the other. But ultimately, squeezing another tenth of a second out of a computation that is only going to be run once or twice does not make a lot of sense.