Four Kinds of Optimisation

Summary

Premature optimisation might be the root of all evil, but overdue optimisation is the root of all frustration. No matter how fast hardware becomes, we find it easy to write programs which run too slow. Often this is not immediately apparent. Users can go for years without considering a program’s performance to be an issue before it suddenly becomes so — often in the space of a single working day. I have devoted more of my life to optimisation than I care to think about, and that experience has led me to make two observations: Human optimism leads us to believe that we can easily know where a program spends most of its time. Human optimism leads us to believe that we can easily know how to make the slow parts of a program run faster. You will not be surprised to learn that I think both forms of optimism misplaced. Partly this is because, as hardware and software have become more sophisticated, it has become harder to understand their effects on performance. But, perhaps more fundamentally, we tend to overestimate how much we know about the software we’re working on. We overemphasise the parts of the system we’ve personally worked on, particularly those we’ve most recently worked on. We downplay other parts of the system, including the impact of dependencies (e.g. libraries). The solution to the first of these observations is fairly widely known — one should rigorously profile a program before assuming one knows where it is spending the majority of its time. I deliberately say “rigorously profile” because people often confuse “I have profiled a program once” with “I have built up a good model of a program’s performance in a variety of situations”. Sometimes, a quick profiling job is adequate, but it can also mislead. Often it is necessary to profile a program with different inputs, sometimes on different machines or network configurations, and to use a variety of sampling and non-sampling approaches. However, the multiple solutions, and their inevitable trade-offs, to...