Premature optimization is the root of all evil

There is a famous saying that “Premature optimization is the root of all evil”. Sometimes it quoted in a longer form: “We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.”

Both are usually attributed to Donald Knuth, but there also seems to be an idea floating around, that the quote was originally due to C. A. R. Hoare, and Knuth only popularised it. This is false; this post is an attempt to settle the matter of its authorship: the evidence unambiguously indicates that the quote is Knuth’s alone.

The quote, in its full form, is from Knuth’s paper Structured Programming with go to Statements, ACM Computing Surveys, Vol 6, No. 4, Dec. 1974 (see p.268), in which he says

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.

So there it is, with no reference to Hoare. Knuth is not quoting Hoare at this point. (He is also making an important point, one that all programmers would do well to take to heart — both aspects of it.)

There is also Computer Programming as an Art, Knuth’s Turing Award lecture (1974), printed in Communications of the ACM, Volume 17, Issue 12, Dec. 1974 (see p.671), in which he says

The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.

(This is weaker than the other form; quite likely this lecture was given before the article above was published, and the quote got better in the article, as quotes are wont to do.)

However, from 15 years later, there is Knuth’s paper The Errors of Tex, in Software—Practice & Experience, Volume 19, Issue 7 (July 1989), pp. 607–685, reprinted in his book Literate Programming (see p. 276), in which he writes

But I also knew, and forgot, Hoare’s dictum that premature optimization is the root of all evil in programming.

This seems to be the source of the popular attribution to Hoare — a short-circuit of Knuth’s original (uncited) attribution. Knuth calls it Hoare’s dictum, but appears to have forgotten not only the dictum but the fact that he was the one who said it. I (and others) have not been able to track down any citation for the actual quote being due to Hoare, and Knuth does not provide one.

Finally, this is the clincher: “Hoare, in an 2004 e-mail to Hans Genwitz of phobia.com, said he didn’t remember the origin of the saying but that he might have attributed it to Dijkstra.” (says Practical Common Lisp, last chapter, footnote 4). The Wayback Machine has preserved the actual email:

Dear Hans,

I’m sorry I have no recollection how this quotation came about.� I might have attributed it to Edsger Dijkstra.

I think it would be fair for you assume it is common culture or folklore.

Tony.

[It's Hans Gerwitz, and the post is still up.]
Translation: “No, I didn’t say it, and Dijkstra is the guy who usually says such things.” (In this case, we know it was Knuth, not Dijkstra.)

I hope this settles the matter: the phrase is Knuth’s.

---

Edit: I had considered asking Knuth directly and decided against it because it would be too hard, but someone else has done it, and it’s decisive: Thanks to Mark Harrison, (who wrote to Knuth asking if he said something else), look here: Knuth says “I did say things like ‘Premature optimization is the root of all evil in programming’…“.

So there!

About these ads