Tracing “premature optimization is the root of all evil”

Method note. Entries are ordered by discovery during this investigation, not by the date of the historical event. “No earlier occurrence found” records the result of the searches performed; it is not proof that no private or unindexed antecedent existed.

Discovery sequence

1. Located the canonical printed passage. Donald E. Knuth’s “Structured Programming with go to Statements,” ACM Computing Surveys 6(4), December 1974, p. 268, contains the familiar 97%/3% formulation. The paragraph explicitly contrasts wasted work on noncritical code with attention to identified critical code. Publisher record; searchable scan. primary
2. Found the concrete example immediately before the maxim. Knuth first changes a table-search data structure to remove an inner-loop operation, then considers loop doubling/unrolling. He calculates a roughly 12% improvement and rejects the view that such a measured gain is necessarily marginal. This made it clear that the slogan was not an argument against small optimizations as a class. Paper, pp. 267–268. primary
3. Found Knuth’s operational definition of “premature.” The sentences after the slogan say the critical 3% should be examined, but “only after that code has been identified”; programmers’ a priori guesses about hotspots usually fail, so measurement feedback should be automatic. Paper, p. 268. primary
4. Traced the numerical “3%” to profiling work. The paper cites Dan Ingalls’s 1972 chapter “The Execution Time Profile as a Programming Tool” and Knuth’s own empirical FORTRAN study. Knuth’s 1970 study (journal version 1971) identifies program profiles as its principal conclusion; the underlying project involved about a dozen students and industry representatives during summer 1970. 1970 report record; 1971 article. primary metadata
5. Established that the source paper was about the structured-programming controversy, not principally optimization. Its abstract announces two concerns: improved control syntax and a transformation method that begins with readable/correct but possibly inefficient code. The optimization maxim occurs inside a worked linear-search example in the section on eliminating go to. Full paper. primary
6. Found Knuth’s account of the controversy’s prehistory. The paper names D. V. Schorre, Peter Naur, Edsger Dijkstra, Peter Landin, Christopher Strachey, C. A. R. Hoare, Niklaus Wirth, Robert Floyd, and others. It records Knuth’s own 1969 difficulty teaching the new style and the resulting Knuth–Floyd article “Notes on Avoiding ‘go to’ Statements” (1971). Knuth–Floyd record. primary
7. Verified Dijkstra’s catalytic 1968 letter. “Go To Statement Considered Harmful” was published 1 March 1968. The famous title was supplied by editor Niklaus Wirth; Dijkstra had submitted “A Case Against the Goto Statement.” This helped separate the structured-programming dispute from later folklore about the optimization maxim. CACM text. primary
8. Found that “rebuttal to Dijkstra” is too strong. Knuth says his provocative title was chosen to attract both camps, says he does not believe he is sharply disagreeing with Dijkstra, and describes the paper as a balanced survey. He ultimately favors abolishing high-level go to when suitable substitutes exist. Paper, pp. 262–263. primary
9. Located a pre-publication public occasion. Knuth says he tested the paper’s deliberately “vacillating” presentation in a UCLA lecture in February 1974. The paper does not say whether the optimization maxim itself appeared in that lecture, so the event narrows the gestation period but does not establish a first utterance. Paper, p. 264. primary
10. Found a specific Hoare influence during the paper’s gestation. Knuth says that in fall 1973 a remark by Hoare lifted his “mental block” about optimization: a compiler should be able to describe optimizations in the source language. This directly fed Knuth’s envisioned interactive program-transformation system, although it is not evidence that Hoare supplied the maxim’s wording. Paper, pp. 282–283. primary
11. Found unusually broad manuscript review. Knuth reports 144 pages of single-spaced comments, six hours of conversation, and four listings from roughly forty named contributors. Both Hoare and Dijkstra are listed. Suggestions were sometimes incorporated without individual acknowledgment, leaving open—though not proving—the possibility of unattributed wording. Acknowledgments, p. 296. primary
12. Located a second 1974 occurrence with a firm oral date. Knuth’s Turing Award lecture, delivered at the ACM Annual Conference in San Diego on 11 November 1974, says programmers worry about efficiency “in the wrong places and at the wrong times” and gives the maxim with the qualifier “or at least most of it.” It points listeners to the structured-programming paper in the “current issue” of Computing Surveys. Lecture PDF; publisher record. primary
13. Recognized a publication-order ambiguity. Both the Turing lecture and “Structured Programming” appeared in December 1974 ACM periodicals. The lecture was unquestionably spoken on 11 November, but the surviving publication data do not establish which December issue physically circulated first. chronology
14. Found the 1989 source of the Hoare attribution. In “The Errors of TeX,” Knuth describes a bug caused by trying to avoid a very frequent assignment and parenthetically says he had forgotten “Hoare’s dictum that premature optimization is the root of all evil in programming.” No citation accompanies that attribution. Publisher record; scan, p. 633. primary
15. Located Hoare’s 2004 response. Asked by Hans Gerwitz, Hoare wrote that he had “no recollection” how the quotation arose, might himself have attributed it to Dijkstra, and thought “common culture or folklore” a fair assumption. This is non-claim of authorship, not a categorical denial. Gerwitz’s post; 2004 archive capture. private email reproduced
16. Found the influential 2008 authorship argument. Shreevatsa R. assembled the two 1974 texts, the 1989 “Hoare’s dictum” passage, and Hoare’s email, concluding that the phrase was Knuth’s. The evidence collection is valuable; its categorical conclusion is stronger than the record warrants because Hoare reviewed Knuth’s draft and Knuth’s 1989 attribution remains unexplained. The Lumber Room. secondary
17. Checked the reported 2012 Knuth confirmation. A now-hard-to-retrieve note quotes Knuth acknowledging, “I did say things like ‘Premature optimization is the root of all evil in programming.’” This confirms use, already established by the 1974 texts; it does not by itself state that he independently coined the wording. A later book reproduces the citation and cautiously concludes that the phrase was “in all likelihood” Knuth’s. citation trail. secondary trail
18. Identified a false 1973 citation in a current dictionary entry. Wiktionary calls a nonexistent “1974 monograph The Art of Computer Programming” the source, while its quotation line labels the source “1973.” The authentic page number 671 belongs to the December 1974 Communications of the ACM lecture, not a 1973 TAOCP volume. Entry. error
19. Checked the rhetorical template. “The root of all evil” closely echoes the King James rendering of 1 Timothy 6:10, “For the love of money is the root of all evil.” The allusion is highly plausible as phrasing, but no source found records Knuth or Hoare explicitly identifying it. KJV text. inference
20. Searched for pre-1974 occurrences and Dijkstra usage. Searches of exact-phrase variants, British spelling, early compiler literature, Dijkstra materials, bibliographic databases, and digitized books produced no verifiable occurrence before Knuth’s 1974 texts. This negative result increases confidence in “earliest documented under Knuth’s name,” but cannot resolve private conversation, manuscript comments, or unindexed print.
21. Separated the slogan from Knuth’s final prescription. The conclusion calls premature emphasis on efficiency a source of complexity and grief, but also says efficiency should remain in a programmer’s “background” awareness. When it matters, start with a structured program and apply well-understood, documented transformations; the recommended lifecycle is analysis/coding/debugging/improving. Paper, pp. 294–295. primary
22. Returned to the 97%/3% question and located the underlying quantitative observations. The full text of Knuth’s 1970 Stanford report says that roughly twenty-five programs received dynamic analysis (the reported table used twenty-four runs) and seventeen programs were examined closely for their inner loops. Their profiles were typically jagged, with a few sharp peaks; Knuth reported that less than 4% of a program generally accounted for more than half its running time. Profiling FORDAP itself exposed two loops consuming about half its time; simplifying them doubled its speed in under an hour. Full report text; 1971 journal article. primary
23. Clarified how the numerical observation became the maxim. Knuth’s 1974 paper first states that most execution time in non-I/O-bound programs is concentrated in about 3% of the source text, then shortly afterward says to forget small efficiencies “say about 97% of the time.” The complement is rhetorically fitted to the profiling result, but the units shift from source text to occasions for optimization. Knuth’s earlier report calls its model a “very rough approximation” and warns that its FORTRAN sample may not be representative; the 97/3 split is therefore a heuristic, not a universal measured law. 1974 paper, pp. 267–268; 1970 report. source-critical inference
24. Established the relevance of Dahl, Dijkstra, and Hoare’s Structured Programming. The book appeared in 1972 and consolidated major statements of the methodology that frames Knuth’s later paper. It is not a located source of the maxim, but Knuth engaged it directly: he issued a twenty-five-page Stanford report, A Review of “Structured Programming”, dated 1 June 1973, and his 1974 paper cites both the book and that review. This makes the book and review a documented intellectual prelude, not evidence that the wording appeared in the book. Book record; Stanford review record; review PDF. primary bibliography