The Lumber Room

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 popularised it.

This post is an attempt to settle the matter of its authorship; to show, as best as I can, that the quote is Knuth’s.

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; probably, this lecture 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.
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.

Further, and 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.

[However, if Knuth calls it "Hoare's dictum", there might be some reason for it: perhaps Hoare had similar opinions? So if someone can point me to references of Hoare having said words to that effect, it would be greatly appreciated. I could send Knuth a letter asking him for the source of the quote (after all, tracking down quotations is a particularly Knuthian activity if I may say so; see §22 of Mathematical Writing), but...]