There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. 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. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail. After working with such tools for seven years, I’ve become convinced that all compilers written from now on should be designed to provide all programmers with feedback indicating what parts of their programs are costing the most; indeed, this feedback should be supplied automatically unless it has been specifically turned off.
Donald Knuth
More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason – including blind stupidity.
William A. Wulf
Interestingly, despite the fact that neither of these quotes says anything specifically about goto, and that the sentiments can be applied to programming as a whole, they both come from papers talking about the use of gotos. Knuth’s quote is from Structured Programming with go to Statements, (Computing Surveys, Vol 6, No 4, December 1974, p268). Wulf’s quote is from A Case Against the GOTO (Proceedings of the ACM National Conference, ACM, Boston, August 1972, p796)
Knuth’s quote is usually abbreviated to “premature optimization is the root of all evil”, sometimes “97% of the time” is mentioned. I wanted to put the quote in context – the surrounding text adds a layer of nuance that isn’t present in the sound bite.
There is some interesting background information on the origin of Knuth’s quote at Shreevatsa R’s blog here.
The idea that “premature optimization is the root of all evil” is itself the root of all slow software that implodes when faced with production-size data volumes. Just the other day we sped up a program over 1000x (from running for many days to running only a few minutes) by changing only a dozen or so lines of code.
Knuth isn’t saying don’t optimize… he’s saying that on-the-fly optimizing whilst writing random pieces of code is a bad idea “since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail”.
It sounds to me like the program you worked on either
a) never went through an optimization phase (which is what Knuth is suggesting is better)
or b) was never designed with optimization in mind
Again, Knuth’s advice applies to ad-hoc, unsubstantiated optimization. E.g., a developer thinking “I’ll just unroll this loop while I’m here because I totally bet it will be slow”, or the other favourite I see “I’ll just add a level of caching here in case the function I’m calling slows down for some reason”. In both cases, the developer should *prove* using tools and analysis that the optimization should happen, as these changes increase the complexity of the code, therefore increasing the maintenance costs of the codebase.
I understood MV’s comment in a different manner. Getting a speed up of 1000x by changing 12 lines of code sounds like identifying the “critical 3%” and fixing it. The fact that an enormous speed up was obtained by changing 12 lines of code means the program design was excellent – the critical code wasn’t spread out over thousands of lines and hundreds of functions.
Finally, the fact that MV is able to quote a 1000x speed up means that somebody actually did some performance measurements. The number of times I hear people talking about performance is vastly greater than the number of times they actually have any data.
This depends heavily on the meaning of “Optimization”.
Knuth talks about “small efficiencies” and not about “Algorithm Selection”. So if you need to select an algorithm you’d do well to use a “good one” (the definition of “good” depends heavily on the use case). So if you use an algorithm with a complexity of O(n^n) where you expect to have lots of elements, then you’re in for bad time.
What Knuth is talking about is stuff like: eliminating variables, manually assigning registers for speed, introducing special cases in the code for performance reasons alone, ….
Stuff like this will usually make the code less readable and more complicated.
All code that is “optimized” this way should be double and tripple checked by multiple programmers because it’s very simple to introduce errors.
Introducing that kind of complexity should only be done in places where it’s REALLY required. And not everywhere!
In short: nobody expects you to use a “BubbleSort” when you need to sort a list (using quicksort is always a good idea. Even more so since quicksort is part of almost every code library anyway). However you should just use the regular library quicksort and not introduce a specially designed quicksort that is optimized for a specific problem (that step should only be done if you see that the implementation of the quicksort is the bottleneck of your preformance… Which is hardly ever the cause…)
I’m pleased to see you included the context for Donath Knuth’s “premature optimisation” quote. It annoys me no end when people use a very small part of what Mr Knuth said as justification for avoiding optimisation entirely.
In context, Mr Knuth states quite clearly that you should identify the critical parts, then target those. That nuance seems to be lost on most people.
Just after I posted this I found a link (via Hacker News) to the transcript of a talk on optimization that Andrei Alexandrescu gave at Facebook:
Three Optimization Tips for C++
One of the first things he mentions is “Quoting Knuth more or less out of context”.