Donald Knuth is a fairly amazing guy. I consider him one of the most influential contributors to computer science of all time. Unfortunately, most of the time I hear his name, I cringe. This is because it’s typically somebody quoting a small portion of one of his famous statements on optimization: “premature optimization is the root of all evil.”
I mention that this is only a portion of the entire quote, and, as such, I feel that Knuth is being quoted out of context. Optimization is important. It is a critical part of every software development effort, and should never be ignored. A developer who ignores optimization is not a professional. Every developer should understand optimization – know what to optimize, when to optimize it, and how to think about code in a way that is intelligent and productive from day one.
I want to start by discussing my own, personal motivation here. I recently wrote about a performance issue I ran across, and was slammed by multiple comments and emails that effectively boiled down to: “You’re an idiot. Premature optimization is the root of all evil. This doesn’t matter.” It didn’t matter that I discovered this while measuring in a profiler, and that it was a portion of my code base that can take “many hours to complete.” Even so, multiple people instantly jump to “it’s premature – it doesn’t matter.”
This is a common thread I see. For example, StackOverflow has many pages of posts with answers that boil down to (mis)quoting Knuth. In fact, just about any question relating to a performance related issue gets this quote thrown at it immediately – whether it deserves it or not.
That being said, I did receive some positive comments and emails as well. Many people want to understand how to optimize their code, approaches to take, tools and techniques they can use, and any other advice they can discover.
First, lets get back to Knuth – I mentioned before that Knuth is being quoted out of context. Lets start by looking at the entire quote from his 1974 paper Structured Programming with go to Statements:
“We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified.”
Ironically, if you read Knuth’s original paper, this statement was made in the middle of a discussion of how Knuth himself had changed how he approaches optimization. It was never a statement saying “don’t optimize”, but rather, “optimizing intelligently provides huge advantages.” His approach had three benefits: “a) it doesn’t take long” … “b) the payoff is real”, c) you can “be less efficient in the other parts of my programs, which therefore are more readable and more easily written and debugged.”
Looking at Knuth’s premise here, and reading that section of his paper, really leads to a few observations:
Optimization is important “he will be wise to look carefully at the critical code”
Normally, 3% of your code – three lines out of every 100 you write, are “critical code” and will require some optimization: “we should not pass up our opportunities in that critical 3%”
Optimization, if done well, should not be time consuming: “it doesn’t take long”
Optimization, if done correctly, provides real benefits: “the payoff is real”
None of this is new information. People who care about optimization have been discussing this for years – for example, Rico Mariani’s Designing For Performance (a fantastic article) discusses many of the same issues very intelligently.
That being said, many developers seem unable or unwilling to consider optimization. Many others don’t seem to know where to start. As such, I’m going to spend some time writing about optimization – what is it, how should we think about it, and what can we do to improve our own code.
