The Lumber Room

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

Premature optimization is the root of all evil

with 17 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!

Advertisements

Written by S

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

Posted in Uncategorized

Tagged with

17 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: https://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

    • 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

  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

    • 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

  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. […]

  11. […] actually make building the software any faster or more efficient. It’s the career equivalent of premature optimization: there may be a few problems where knowing the properties of a low-level technology manifests at a […]

  12. […] the rest of us — those who understand what it means to say We should forget about small efficiencies, say about 97% of the time, I’ll keep heartily recommending ”.join, so we all can sleep in all tranquility and […]

  13. […] Premature optimization is the root of all evil […]

  14. […] Особенно если учесть рост проекта и компании. О преждевременной оптимизации не забываем, но если есть процесс, который хорошо […]

  15. […] 我们中的一些Python提交者,我相信大多数Rigo和Hettinger,都是为了优化某些特殊情况下的s += something 枯萎病这个太常见的s += something 枯萎病事实证明,初学者永远不会确信''.join是正确的选择,+=的可怕缓慢可能会给Python带来一个坏名声。我们其他人并不那么热,因为他们不可能把每一次事件(甚至只是大多数事件)都优化成体面的表现。但是我们对这个问题感到不够热情,试图积极阻止。 我相信这个线程证明我们应该更严厉地反对他们。就像现在一样,他们在某些难以预测的案例子集中对+=进行了优化,使得对于特殊的愚蠢的案例比正确的方法(IS仍然是''.join)要快20%完美的方式,通过使用错误的成语,让初学者陷入追求20%的不相关的收益……不惜一次又一次地从他们的POV中突然冒出200%的性能损失(或更多,因为非线性行为仍然潜伏在Hettinger和Rigo打扮并放入花朵的角落之外 – 一个重要的东西,一个会使他们悲惨的东西。这与Python的“理想情况下只有一个显而易见的方式”是一致的,对我来说,就像我们总体上对初学者有一个陷阱 – 最好的一样……那些不仅仅接受他们被“更好的”所告知,但好奇地去质疑和探索。 啊,我放弃了。 OP,@mshsayem,继续前进,在任何地方使用+ =,享受你无关紧要的20%加速,微不足道的情况下,你最好享受他们的剑柄 – 因为有一天,当你看不到它在一个重要的,大的操作中,你会被200%减速的迎面而来的拖车卡车撞击(除非你运气不好,这是一个2000%的;)。只要记住:如果你觉得“Python非常慢”,请记住,它更可能是你心爱的+=循环之一转身,咬着喂它的手。 对于我们其他人来说,那些明白We should forget about small efficiencies, say about 97% of the time意味着什么的人,我会一直坚持推荐''.join,所以我们都可以睡得很安宁,知道我们不会遇到超线性的放缓。我们最不期待,至少可以负担得起你。但是对你来说,Armin Rigo和Raymond Hettinger(后两位亲爱的私人朋友,不止是共同委托人;-) – 可能你的+=顺利,你的大O永远不会比N更坏! – ) 所以,对于我们其他人来说,这里有一个更有意义和有趣的测量: […]


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