The Lumber Room

"Consign them to dust and damp by way of preserving them"

Premature optimization is the root of all evil

with 12 comments

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

Written by S

Fri, 2008-05-16 at 00:27:06 +05:30

Posted in Uncategorized

Tagged with

12 Responses

Subscribe to comments with RSS.

  1. [...] I have known of this quote but never knew its origin, until tonight. Ewemoa, from DonationCoder.com, shared the quote with mouser who recommended it be shown to me. Thanks to both of them, I can now effectively quote its origin as well. Long story short, I wanted to include this quote, and the page that was referenced to me, on my website. Here is the link: http://shreevatsa.wordpress.com/2008/05/16/premature-optimization-is-the-root-of-all-evil/ [...]

  2. [...] performance issues… damn!  I started to panic a little.  I went on a tangent and started optimizing without understanding the problem I was facing first.  I was using gruff to generate graphs (you’re probably way ahead of me at this point… [...]

  3. [...] don’t want to optimize this code prematurely. And “while you’re still writing it” is probably premature. On the other hand, [...]

  4. [...] In context from Knuth’s paper Structured Programming with go to Statements, ACM Computing Surveys, Vol 6, No. 4, Dec. 1974 p.268 (source): [...]

  5. Hello,

    Thanks for info, I linked to you.

    Do you also know where he did say:

    If you find that you’re spending almost all your time on theory, start turning some attention to practical things; it will improve your theories. If you find that you’re spending almost all your time on practice, start turning some attention to theoretical things; it will improve your practice.

    Thanks.

    askfamousquote

    Fri, 2009-11-13 at 21:17:39 +05:30

    • Your site (“Who said that quote and what’s its context?”) seems like a nice idea, but why you do not actually have context for any of your quotes? :P

      Anyway, this quote (nice one) seems to be from a keynote address he gave at the 11th World Computer Congress in 1989, titled Theory and Practice. A PDF is available on the arXiv here (and the TeX file tap.tex is P138 on Knuth’s webpage). Cheers,

      Shreevatsa

      Fri, 2009-11-13 at 23:06:56 +05:30

  6. Who said that (I was sure it was Knuth, but cannot find a ref anywhere): “An advice on optimization, for rookies – do not optimize, for gurus – do not optimize just yet”?

    Alexms2001

    Mon, 2012-02-13 at 23:06:25 +05:30

    • I’m pretty sure it was not Knuth, but yes, something like that has been part of the programming folklore.

      S

      Tue, 2012-02-14 at 16:04:35 +05:30

  7. [...] premature optimization is the root of all … not good things. Therefore, the default return value for the select operation has now been changed to a list of [...]

  8. [...] well-known since the seventies that premature optimization is root of all evil. This saying is so old that it was part of my CS education in the early 2000′s. (The best [...]

  9. […] for each. Don’t over-think it – let the system just do its thing. Another example of premature optimization being the root of all evil, I suppose. There wasn’t a significant performance issue there at all, in any case. Just […]

  10. […] There is some interesting background information on the origin of Knuth’s quote at Shreevatsa R’s blog here. […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 67 other followers