Software and engineering
Premature optimisation
Do not tune code for speed before you have measured where the time goes; most of it is in a few places, and you will guess them wrong.
Donald Knuth, "Structured Programming with go to Statements", ACM Computing Surveys, December 1974. Often credited to Tony Hoare; Knuth himself called it Hoare's dictum in 1989, and Hoare has said he cannot recall where it came from.
The line everyone quotes is half a paragraph. Knuth wrote that programmers waste enormous time worrying about the speed of noncritical parts of their programs, that these attempts hurt debugging and maintenance, and that we should forget about small efficiencies about 97 percent of the time: premature optimisation is the root of all evil. The next sentence is the one that gets dropped: we should not pass up our opportunities in that critical 3 percent. A good programmer looks carefully at the critical code, but only after it has been identified, because the universal experience of people using measurement tools is that their intuitive guesses about what is critical fail. In the same paper Knuth argues that an easily obtained 12 percent is never considered marginal in established engineering and should not be in software.
It holds because running time concentrates. Knuth's figure of speech is the inner loop: speed it up by 10 percent and the whole program speeds up by almost 10 percent, while the rest of the code barely runs. A profiler finds that loop for you; intuition does not, and Knuth wanted compilers to report where the time went automatically. The practice is a loop of its own: write the clear version, measure under realistic load, change the one thing at the top of the profile, measure again, and stop when the gain is inside the noise. Keep the measurement with the code, so the next person can tell the tuned 3 percent from the 97 percent that should stay plain.
The quote is misused as a licence to ignore performance until it hurts. Knuth said the opposite: he objected to micro-tuning before measurement, not to thinking. Choices that are expensive to reverse, such as the data model, an O(n squared) algorithm on a growing input, a chatty network protocol or the number of model calls per request, are not small efficiencies, and no profiler will save you from them later. Those belong to design, where measurement means estimating orders of magnitude before building. The attribution is also folklore: Knuth's 1974 paper has the sentence with no reference to Hoare, Knuth credited Hoare fifteen years later, and Hoare told Hans Gerwitz in 2004 that he had no recollection of it and might have credited Dijkstra.
Example
In the 1974 paper itself Knuth worked through a sequential search loop (his Example 2) and a version with the loop body doubled so the loop test ran half as often (Example 2a). He put the gain at about 12 percent, and argued that in any established engineering discipline an easily obtained 12 percent would never be called marginal. He then checked the number against the actual output of a typical compiler and found the real improvement was less than he had expected, because the go to statements in the faster version stopped the compiler from assuming what was in its registers. The paper's advice follows from the episode: even the author's own estimate was off until he measured.
Where it applies
Profile before you touch anything: a sampling profiler on the service, the performance tab in the browser, timestamps per stage in a model pipeline. Fix the stage at the top, re-measure, and stop when the gain is in the noise. Spend design time instead on the choices you cannot cheaply reverse, such as the storage engine, the data model and the number of round trips per request; Knuth's 3 percent does not exempt those.
Think about it
What code have you optimised this year without a measurement before and after, and what did it cost in readability?
Applied it to something real? Log it.
Test yourselfKnuth's full sentence says to forget small efficiencies about 97 percent of the time. What does the rest of the passage say to do with the other 3 percent?
Look at it carefully and optimise it, but only after measurement tools have identified it, because intuitive guesses about which code is critical fail.
Related models
- Amdahl's lawSpeeding up one part of a job is capped by the share of time that part takes; whatever you leave untouched sets the ceiling.
- YAGNI (you aren't gonna need it)Build a capability when you actually need it, not when you foresee needing it; the forecast is usually wrong and carrying the code is not free.
- Bottlenecks and the theory of constraintsA system's throughput is set by one constraint; improving anything else is wasted effort until that constraint is fixed.
- One-way and two-way doorsMake reversible decisions quickly and save slow, careful deliberation for the ones you cannot undo.