The origin of “Premature optimization is the root of all evil”

1. Bottom-line finding

The maxim enters the verifiable historical record under Donald E. Knuth’s name in 1974. Knuth spoke a version on 11 November at the ACM Annual Conference and published two versions in December: one in his Turing Award lecture, “Computer Programming as an Art,” and the fuller, now-canonical version in “Structured Programming with go to Statements.”¹² No verifiable earlier occurrence was found in the searches undertaken for this report.

That result answers “who first put it on the record?” more securely than “who first assembled those words?” The 1974 paper gives no attribution at the maxim. Fifteen years later, however, Knuth called it “Hoare’s dictum.”⁸ C. A. R. Hoare had been an important intellectual influence and one of the paper’s many manuscript reviewers. When asked in 2004, Hoare did not claim authorship; he said he had no recollection, might have attributed it to Edsger Dijkstra, and regarded “common culture or folklore” as a fair assumption.⁹

2. The documented occurrences

11 November 1974: spoken at the Turing Award lecture

The earliest occurrence with a day-specific date is Knuth’s ACM Turing Award lecture, delivered on 11 November 1974 at the ACM Annual Conference in San Diego. The published lecture records:

“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.”

Donald E. Knuth, “Computer Programming as an Art,” p. 671.²

The qualifying joke—“or at least most of it”—is significant. Knuth was deliberately hyperbolic, not proposing a literal law. The next sentences say that efficiency has a time and place and refer the audience to the structured-programming paper “in the current issue of Computing Surveys.”

December 1974: the canonical printed formulation

The fuller passage occurs on p. 268 of “Structured Programming with go to Statements,” ACM Computing Surveys 6(4):

“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.”

Donald E. Knuth, “Structured Programming with go to Statements,” p. 268.¹

The familiar eight-word quotation is therefore a truncation from the middle of a two-sided argument. The preceding sentence narrows the subject to small efficiencies in noncritical code; the following paragraph positively commands attention to critical code.

1989: Knuth calls it Hoare’s

In “The Errors of TeX,” Knuth recounts a bug in get_next, TeX’s hottest routine. He had avoided assigning zero to a variable when he thought its value would usually be irrelevant. A later code path violated that assumption. In retrospect he wrote: “But I also knew, and forgot, Hoare’s dictum that premature optimization is the root of all evil in programming.”⁸ This is the only primary-source evidence uncovered that assigns the maxim to Hoare—and it comes from Knuth, not Hoare, fifteen years after Knuth’s unattributed uses.

3. Chronology of the ideas, people, and events

1. 1959–1960

   Heinz Zemanek expresses doubts about go to; D. V. Schorre begins systematically writing programs without labels or go to, using indented outlines. Knuth later identifies these as early steps in the control-structure movement.¹

2. 1963–1964

   Peter Naur publishes “Go To Statements and Good Algol Style.” Knuth meets Schorre in 1963, remains skeptical, and in 1964 challenges him to solve eight queens without go to; Schorre does so with recursion and Boolean variables.¹

3. 1965–1966

   Dijkstra reports experiments in go to-free ALGOL variants and finds the programs shorter and clearer. Peter Landin describes removing explicit sequencing as a way to make programs more transparent. Hoare, Landin, Strachey, and others influence Dijkstra’s thinking.¹

4. March 1968

   Communications of the ACM publishes Dijkstra’s letter “Go To Statement Considered Harmful.” Dijkstra submitted “A Case Against the Goto Statement”; editor Niklaus Wirth supplied the more memorable title and changed it to a letter to accelerate publication.⁵

5. 1969

   Teaching introductory programming at Stanford, Knuth struggles to express some programs in the new style and repeatedly seeks Robert W. Floyd’s help. This work produces their 1971 paper “Notes on Avoiding ‘go to’ Statements.”¹⁶

6. Summer 1970

   Knuth, about a dozen students, and software-industry representatives conduct a three-month empirical study of FORTRAN programs. Its principal conclusion is the importance of execution-frequency profiles; the report appears in 1970 and the journal article in 1971.³⁴

7. 1971–1972

   Knuth and Floyd publish their go to analysis, and Dan Ingalls publishes “The Execution Time Profile as a Programming Tool.” In 1972, Ole-Johan Dahl, Edsger W. Dijkstra, and C. A. R. Hoare publish Structured Programming; together with Dijkstra’s Turing lecture “The Humble Programmer,” the book makes the new methodology central to the field.¹¹⁵

8. 1 June 1973

   Knuth issues the twenty-five-page Stanford report A Review of “Structured Programming.” He describes the recent Dahl–Dijkstra–Hoare book as promising significant impact on computer science. His 1974 paper later cites both the book and this review, making them a documented intellectual prelude to his continued treatment of the subject.¹⁶¹

9. 1972–1973

   The debate becomes institutional and public: an ACM conference session and a December 1973 Datamation cluster address structured programming and eliminating go to. Knuth worries that purity enforced without regard to compiler overhead may provoke a counterreaction.¹

10. Fall 1973

    Knuth encounters Hoare’s suggestion that an optimizing compiler should be able to describe its optimizations in the source language. Knuth says this lifts his “mental block” about optimization and leads him toward interactive, documented source-to-source transformations.¹⁷

11. 1973–1974

    Knuth spends roughly a year thinking about structured programming. Dijkstra sends several personal communications. Knuth prepares a first draft and receives an extraordinary volume of feedback from roughly forty people, including Hoare, Dijkstra, Floyd, Wirth, John Cocke, Peter Naur, and Dan Satterthwaite.¹

12. February 1974

    Knuth lectures at UCLA using the paper’s intentionally balanced presentation. He reports that listeners on opposing sides each felt he largely supported them. The source does not preserve the lecture text or say whether the maxim was already present.¹

13. 2 April 1974

    The latest precisely dated personal communication cited in the paper is from W. Wesley Peterson. This shows revision continued after the UCLA lecture.¹

14. 11 November 1974

    Knuth delivers “Computer Programming as an Art” in San Diego and publicly uses the “root of all evil” sentence, adding “or at least most of it.”²

15. December 1974

    The Turing lecture appears in Communications of the ACM 17(12), pp. 667–673, and “Structured Programming with go to Statements” appears in ACM Computing Surveys 6(4), pp. 261–301. The latter contains the 97%/3% version.¹²

16. July 1989

    Knuth publishes “The Errors of TeX” and calls the saying “Hoare’s dictum,” with no citation or explanation.⁸

17. January 2004

    Hoare replies to Hans Gerwitz: no recollection of the origin; he might have attributed it to Dijkstra; folklore is a fair assumption. Gerwitz posts the email in August.⁹¹⁰

18. May 2008

    Shreevatsa R. publishes an influential online source comparison arguing that the phrase is Knuth’s. The post usefully corrects casual Hoare/Dijkstra attributions but overstates how completely private coinage can be settled.¹¹

19. 2012

    A note reports Knuth acknowledging that he “did say things like” the maxim. This confirms use, not independent coinage; the 1974 publications already made the former indisputable.¹²

4. What precipitated the maxim?

The broad circumstance: a methodological revolution

Knuth opens “Structured Programming” by describing a revolution in how programs were written and taught. The late-1960s “software crisis” had intensified concern with correctness, comprehensibility, and maintenance. Dijkstra and others argued that unrestricted jumps made a program’s evolving state hard to reason about. Some reformers proceeded from criticism of go to to suspicion of global variables, pointer variables, floating-point arithmetic, semaphores, and even assignment.¹

Knuth accepted the revolution’s core—abstraction, local reasoning, and program structure—but resisted moralistic, one-rule purity. He feared that cleanly structured programs compiled inefficiently would run much slower than older hand-tuned code and produce a backlash against structure itself. His paper asks how to obtain reliability, clarity, and efficiency without treating any one syntactic feature as a magic solution.

The direct literary prelude: Structured Programming and Knuth’s review

Dahl, Dijkstra, and Hoare’s 1972 book Structured Programming is relevant to the maxim’s surrounding history even though it is not a located source of the wording. The volume assembled three substantial treatments of program construction and data structure and became a defining statement of the movement. Knuth engaged it formally in A Review of “Structured Programming”, a twenty-five-page Stanford technical report dated 1 June 1973. The review says the book promises significant impact on computer science; the 1974 paper’s bibliography cites both the book and Knuth’s review.¹⁵¹⁶¹

The careful conclusion is therefore twofold. The book belongs in the causal and intellectual background: it helped define the methodological claims to which Knuth was responding, and Knuth’s review documents sustained engagement before the 1974 article. But no occurrence of the maxim was located in the book, and Knuth does not cite it as the source of the phrase. Hoare’s coauthorship is suggestive only in light of Knuth’s much later “Hoare’s dictum” attribution; it supplies no independent evidence that the wording originated in the volume.

The immediate circumstance: a table-search program

The maxim does not arise from a failed commercial project, a management dispute, or an identifiable conversation. In the published record it arises while Knuth works through three versions of a small table-search routine:

1. Example 1: linear search exits with go to when it finds the target.
2. Example 1a: a go to-free rewrite repeats a comparison and is, in Knuth’s view, slightly less readable and slower.
3. Example 2: a sentinel is placed after the array’s current end, removing an inner-loop bounds test. This is both more structured and substantially faster—about 33% under hand-coded assumptions and 21% with a typical compiler.
4. Example 2a: the loop is doubled/unrolled, duplicating tests so the index increment occurs half as often. Knuth estimates another roughly 12% improvement when the search is important and heavily repeated.¹

The rhetorical pivot is exact: Knuth first rejects the “conventional wisdom” that efficiency in the small can always be ignored. An easily obtained 12% improvement in established engineering, he says, would not be dismissed. He then rejects the opposite vice—spending enormous time on noncritical regions. The maxim names that second error; the “critical 3%” names the exception.

The empirical circumstance: profiles defeat intuition

The number 3% is not a mystical prescription or a disguised Pareto rule. Immediately before the maxim, Knuth says experience reported in Dan Ingalls’s profiling work and his own FORTRAN study showed that most running time in non-I/O-bound programs was concentrated in about 3% of the source. A short inner loop can govern overall speed, so removing one of ten instructions from that loop can nearly improve the entire computation by 10%.¹

The empirical antecedent is unusually concrete. During summer 1970, Knuth worked for three months with about a dozen students and software-industry representatives. Roughly twenty-five programs were dynamically analyzed; the execution-frequency table was compiled from twenty-four FORDAP runs, and seventeen programs were selected for close examination of their inner loops. Knuth reported that profiles were typically jagged, with a few sharp peaks, and that less than 4% of a program generally accounted for more than half its running time. When the group profiled FORDAP itself, two simplifiable loops consumed about half its time; changing them doubled the program’s speed in less than an hour.³⁴

The numerical chain therefore has an empirical base but not the precision sometimes attributed to it. Knuth called the 1971 model a “very rough approximation,” emphasized variation among programs, said his sample might not be representative, and restricted the later 3% statement to non-I/O-bound programs. Moreover, the units change: the empirical statement concerns a fraction of source text, whereas “97% of the time” describes occasions on which small efficiencies should be ignored. The complement is rhetorically fitted to the hotspot observation; it is not a direct statistical estimate that 97% of optimization attempts are harmful.³⁴

Knuth had used measurement tools for seven years by 1974 and reports a “universal experience”: programmers’ intuitive guesses about which code is critical fail. His policy proposal was remarkably strong—compilers should automatically report which source regions cost the most unless the user turns that feedback off. The maxim is therefore inseparable from profiling.

The design circumstance: optimization as an explicit transformation

Hoare’s 1973 influence matters here. Knuth says Hoare’s remark—that a compiler ought to express its optimization in the source language—helped him see optimization not as a hidden machine-code activity but as a documented transformation from program P to program Q. P should be understandable, well documented, and readily proved correct; Q may be less readable but efficient. The transformations from P to Q should be reliable, mechanical, and retained alongside P so later maintainers can understand the system.¹

Thus the maxim crystallized at the intersection of three pressures: structured-programming demands for clarity, engineering demands for speed, and empirical evidence that only measured hotspots deserve clarity-reducing transformations.

5. What Knuth was trying to convey

1. “Premature” means before evidence identifies the target

The most immediate criterion is explicit: look carefully at critical code “only after that code has been identified.” Identification comes from measurement, knowledge of workloads, or a comparably strong reason—not from a priori intuition. The maxim is not tied to a product milestone such as “feature complete.” An inner loop can be identified as critical early; a noncritical routine remains a bad optimization target even late.

2. The object of criticism is small efficiency work in noncritical code

Knuth’s nouns matter. He speaks of “small efficiencies,” “the speed of noncritical parts,” and attempts that damage debugging and maintenance. The famous fragment is not a general warning against selecting a sound asymptotic algorithm, designing to a known capacity requirement, or avoiding an obviously catastrophic data representation. Indeed, Example 2 improves the data structure before the micro-optimization in Example 2a.

3. Optimization remains part of good engineering

Knuth positively argues that an easily achieved 12% improvement can be worthwhile in quality software and that programmers should seize opportunities in the critical 3%. His Turing lecture says efficiency is an aspect of program quality and that it has “a time and place.”² His target is misallocated effort, not performance awareness.

4. Clarity has instrumental value

Unnecessary optimization is harmful not merely because engineering time is scarce. It makes programs harder to debug, understand, change, and maintain, which can reduce “net efficiency.” A simple source program supplies an intelligible object for reasoning about correctness. If optimization requires a less readable result, the derivation should remain documented rather than forcing maintainers to reverse-engineer it.

5. A good lifecycle separates structuring from integration

The paper’s conclusion says to keep efficiency considerations in the background while formulating programs, while remaining subconsciously aware of the available tools. It compares engineering to first understanding separate components and only later integrating functions. Its preferred lifecycle, borrowed from Gerald Weinberg, is “analysis/coding/debugging/improving,” not a permanent refusal to optimize.¹

6. The percentages are illustrative, not normative

“Say about 97%” signals an order-of-magnitude heuristic based on then-current profile observations. It is not a claim that exactly one line in thirty-three should be optimized, that exactly 3% of every program dominates execution, or that 97% of optimization proposals are harmful. The empirical antecedent measures source text; the maxim restates the contrast as “of the time.” That rhetorical change of unit is one reason the numbers should not be read as a reproducible probability. The phenomenon is workload-, language-, and system-dependent.

6. Who originated the wording?

The case for Knuth

• The first located occurrences are two texts authored by Knuth, with a day-dated public delivery by Knuth.
• Neither 1974 occurrence attributes the words to anyone else, although Knuth was normally generous with citations and the structured-programming paper contains more than one hundred references.
• The full 97%/3% rhetoric is tightly fitted to Knuth’s own empirical profiling work and to the precise search example he is analyzing.
• The Turing lecture presents the line in Knuth’s own explanatory voice, not as a quotation.
• No pre-1974 Hoare or Dijkstra occurrence was located, and Hoare did not claim it when asked.

Why sole coinage remains uncertain

• Knuth’s 1989 phrase “Hoare’s dictum” is direct evidence that Knuth then remembered or understood the underlying saying as Hoare’s. It may be a simple memory error, but dismissing it is an inference.
• Hoare directly influenced Knuth’s optimization thinking in fall 1973 and supplied comments on the first draft. Knuth says he incorporated reviewers’ suggestions without always acknowledging them. The surviving published paper does not tell us whether the maxim was already in the first draft or appeared during revision.
• Hoare’s 2004 response is not “I never said it.” It is “I’m sorry I have no recollection how this quotation came about,” followed by speculation about Dijkstra and folklore. That weakens a confident Hoare attribution but does not logically disprove an oral Hoare origin.
• The rhetorical mold “X is the root of all evil” was already common, most famously from the King James wording of 1 Timothy 6:10.¹³ Independent or conversational formation would have been easy.

The Dijkstra hypothesis

The evidence for Dijkstra is weaker. Hoare said only that he might have attributed the quotation to Dijkstra. A later attribution by Bruce Eckel appears to derive from the same folklore, not a primary Dijkstra text. Dijkstra contributed comments to Knuth’s paper and was central to the dispute, but no Dijkstra document containing the phrase was found. It is therefore improper to state that Dijkstra originated it.

Assessment

On balance, Knuth is the probable composer of the published formulation and indisputably its first documented exponent. The evidence is insufficient to assign private oral coinage “to Knuth alone” beyond reasonable doubt. A historian should distinguish documented authorship from ultimate conversational origin.

7. Conflicting stories, errors, exaggerations, and distortions

8. Limits of the surviving record

This inquiry located published articles, the dated Turing lecture, bibliographic records, Knuth’s retrospective statement, and a reproduced private Hoare email. It did not locate Knuth’s first draft, reviewer marginalia, the 144 pages of comments, a transcript of the February 1974 UCLA lecture, or correspondence specifically discussing the phrase. Those materials—if preserved in Stanford, Oxford, ACM, or personal archives—could materially improve the answer.

The statement “no earlier occurrence was found” is bounded by searchable digitized sources. Exact-phrase and variant searches covered “premature optimization/optimisation,” early compiler literature, Dijkstra attribution, Hoare attribution, bibliographic indexes, and digitized book references. Negative search evidence cannot exclude an unindexed conference remark, internal memorandum, editorial comment, or ordinary conversation.

A further archival project would prioritize: (1) the Donald E. Knuth papers and drafts for P69 / “Structured Programming”; (2) correspondence with Hoare and Dijkstra from 1973–1974; (3) UCLA Computer Science colloquium records for February 1974; (4) ACM editorial production files for both December 1974 articles; and (5) Hoare’s retained correspondence or manuscript files. Until such evidence appears, the qualified conclusion above is the maximum warranted by the accessible record.

9. Sources and citation notes

1. Knuth, Donald E. “Structured Programming with go to Statements.” ACM Computing Surveys 6, no. 4 (December 1974): 261–301. DOI: 10.1145/356635.356640. Accessible page-image scan. Key pages: 262–268 (purpose, history, search example, maxim); 282–284 (program transformation and Hoare influence); 294–296 (conclusion and acknowledgments).
2. Knuth, Donald E. “Computer Programming as an Art.” 1974 ACM Turing Award Lecture, delivered 11 November 1974; Communications of the ACM 17, no. 12 (December 1974): 667–673. DOI: 10.1145/361604.361612. Accessible PDF. The maxim is on p. 671; the lecture PDF’s heading supplies the delivery date and venue.
3. Knuth, Donald E. An Empirical Study of Fortran Programs. Stanford Artificial Intelligence Project memo AIM-137 / Computer Science report CS-186, 1970. Internet Archive record and scan; searchable full text. Especially relevant are pp. 11–12 (jagged profiles and the less-than-4% observation), p. 16 (selection of seventeen inner-loop programs), and pp. 33–34 (conclusions and limits).
4. Knuth, Donald E. “An Empirical Study of FORTRAN Programs.” Software—Practice & Experience 1, no. 2 (April–June 1971): 105–133. DOI: 10.1002/spe.4380010203. Accessible PDF.
5. Dijkstra, Edsger W. “Letters to the Editor: Go To Statement Considered Harmful.” Communications of the ACM 11, no. 3 (March 1968): 147–148. ACM republication. On the original title and Wirth’s intervention, see Dijkstra’s retrospective account reproduced in Scott Rosenberg, “Dijkstra’s ‘Go To Statement Considered Harmful’” (2006).
6. Knuth, Donald E., and Robert W. Floyd. “Notes on Avoiding ‘go to’ Statements.” Information Processing Letters 1, no. 1 (1971): 23–31. DOI: 10.1016/0020-0190(71)90018-4.
7. Hoare, C. A. R. Hints on Programming Language Design. STAN-CS-73-403 / AIM-224, Stanford University, December 1973, 29 pp. Confirmed in Stanford’s bibliography of computer-science reports. (Knuth’s 1974 bibliography prints January 1974 and STAN-CS-74-403; Stanford’s report bibliography gives December 1973 and STAN-CS-73-403.)
8. Knuth, Donald E. “The Errors of TeX.” Software—Practice & Experience 19, no. 7 (July 1989): 607–685, esp. 633. DOI: 10.1002/spe.4380190702. Accessible PDF.
9. Gerwitz, Hans. “Premature optimization is the root of all evil.” 12 August 2004. Reproduces Hoare’s January 2004 email. Current page.
10. Gerwitz, Hans. Archived 31 August 2004 version of the same page. Internet Archive capture. This near-contemporaneous capture secures the wording and publication history of the reproduced email.
11. Shreevatsa R. “Premature optimization is the root of all evil.” The Lumber Room, 16 May 2008, later updated. Post. Valuable secondary collation of the attribution dispute.
12. Harrison, Mark. “A note from Donald Knuth about TAOCP.” 2012 (original Codehaus/Blogspot page no longer reliably retrievable). The reported wording and citation are preserved in Brian Christian, The Alignment Problem, and reproduced in this digitized source aggregation. Because the original page was unavailable, this report gives the item limited evidentiary weight.
13. 1 Timothy 6:10, King James Version. “For the love of money is the root of all evil…” Public-domain text. The report treats the maxim’s echo as a plausible rhetorical allusion, not documented authorial testimony.
14. Wiktionary contributors. “premature optimization.” Current entry. Cited only as an example of a live bibliographic error: it combines a “1974 monograph” claim with a 1973 TAOCP citation, while the authentic source is the 1974 periodical literature.
15. Dahl, Ole-Johan; Edsger W. Dijkstra; and C. A. R. Hoare. Structured Programming. London and New York: Academic Press, 1972. viii + 220 pp. ACM bibliographic record; digitized copy record. The book is evidence for the movement’s intellectual setting, not a located occurrence of the maxim.
16. Knuth, Donald E. A Review of “Structured Programming.” Stanford University Computer Science Department report STAN-CS-73-371, 1 June 1973, 25 pp. Stanford record; report PDF. Knuth’s 1974 bibliography cites the report as June 1973.

Quotation policy. The two longer quotations are taken from Knuth’s 1974 primary sources because exact wording is the object of the historical inquiry. Other source language is paraphrased except where a short phrase is necessary to distinguish testimony from interpretation.