Revisiting Knuth's "Premature Optimization" Paper
34 comments
·June 26, 2025godelski
Swizec
Amdahl’s Law is the single best thing I learned in 4 years of university. It sounds obvious when spelled out but it blew my mind.
No amount of parallelization will make your program faster than the slowest non-parallelizable path. You can be as clever as you want and it won’t matter squat unless you fix the bottleneck.
This extends to all types of optimization and even teamwork. Just make the slowest part faster. Really.
hinkley
> faster than the slowest non-parallelizable path
Rather, than the slowest non-parallelized path. Ultimately you may reach maximum speed on that path but the assumptions that we are close to it often turn out to be poorly considered, or considered before 8 other engineers added bug fixes and features to that code.
From a performance standpoint you need to challenge all of those assumptions. Re-ask all of those questions. Why is this part single threaded? Does the whole thing need to be single threaded? What about in the middle here? Can we rearrange this work? Maybe by adding an intermediate state?
godelski
> It sounds obvious when spelled out but it blew my mind.
A cliche is a phrase that's so obvious everyone innately knows or understands it; yet, it is so obvious no one internalizes it, forcing the phrase to be used ad nauseam
Like Amdahl's Law, I think many of these take a surprising amount of work to prove despite the result sounding so obvious. The big question is if it was obvious a priori or only post hoc. We often confuse the two, getting us into trouble. I don't think the genius of the statement hits unless you really dig down into proving it and trying to make your measurements in a nontrivially complex parallel program. I think that's true about a lot of things we take for granted
chinchilla2020
another commonly misinterpreted one is the `shouting fire in a crowded theatre` quote.
In it's original context it means the opposite of how people use it today.
ilc
Interestingly, you didn't learn the full lesson:
When optimizing, always consider the cost of doing the optimization vs. it's impact.
In a project where you are looking a 45/30/25 type split. The 45 may actually be well optimized, so the real gains may be in the 30 or 25.
The key is to understand the impact you CAN have, and what the business value of that impact is. :)
The other rule I've learned is: There is always a slowest path.
godelski
I didn't get that impression from their response. I mean I could be wrong, but in context of "use a profiler" I don't think anything you said runs counter. I think it adds additional information, and it's worth stating explicitly, but given my read yours comes off as unnecessarily hostile. I think we're all on the same page, so let's make sure we're on the same side because we have the same common enemy: those who use Knuth's quote to justify the slowest piece of Lovecraftian spaghetti and duct tape imaginable
Swizec
> The key is to understand the impact you CAN have, and what the business value of that impact is. :)
Like I tell everyone in system design interviews: AWS will rent you a machine with 32TB of RAM. Are you still sure about all this extra complexity?
chinchilla2020
There is more to it than that.
1. Decide if optimization is even necessary.
2. Then optimize the slowest path
nurettin
There is also the "death by a thousand cuts" kind of slowness that accrues over time and it doesn't really matter where you start peeling the onion and the part you started is rarely the best.
hinkley
It is exactly this "lulled into complacency" that I rail against when most people cite that line. Far too many people are trying to shut down down dialog on improving code (not just performance) and they're not above Appeal to Authority in order to deflect.
"Curiosity killed the cat, but satisfaction brought it back." Is practically on the same level.
If you're careful to exclude creeping featurism and architectural astronautics from the definition of 'optimization', then very few people I've seen be warned off of digging into that sort of work actually needed to be reined in. YAGNI covers a lot of those situations, and generally with fewer false positives. Still false positives though. In large part because people disagree on what "The last responsible moment" in part because our estimates are always off by 2x, so by the time we agree to work on things we've waited about twice as long as we should have and now it's all half assed. Irresponsible.
godelski
I'm with you, and been on a bit of a rampage about it lately. Honestly, just too much broken shit, though I'm not sure what the last straw was.
A big thing I rail against is the meaning of an engineer and that our job is about making the best product, not making the most profitable product (most times I bring this up someone will act like there's no difference between these. That itself is concerning). The contention between us engineers and the business people is what creates balance, but I'm afraid we've turned into yesmen instead. Woz needs Jobs, but Jobs also needs Woz (probably more than the other way around). The "magic" happens at the intersection of different expertise.
There's just a lot of weird but subtle ways these things express themselves. Like how a question like "but what about x problem" is interpreted as "no" instead of "yes, but". Or like how people quote Knuth and use it as a thought terminating cliche. In ML we see it with "scale is all you need."
In effect, by choosing to do things the easy way we are choosing to do things the hard way. Which this really confuses me, because for so long in CS the internalization was to "be lazy." Not in the way that you put off doing the dishes now but in the way that you recognize that doing the dishes now is easier than doing them tomorrow when you 1) have more dishes 2) the dishes you left out are harder to clean as the food hardens on the plate. What happened to that "efficient lazy" mindset and how did we turn into "typical lazy"?[0]
[0] (I'm pretty sure I need to add this) https://en.wikipedia.org/wiki/Rhetorical_question
dan-robertson
I like this article. It’s easy to forget what these classic CS papers were about, and I think that leads to poorly applying them today. Premature optimisation of the kind of code discussed by the paper (counting instructions for some small loop) does indeed seem like a bad place to put optimisation efforts without a good reason, but I often see this premature optimisation quote used to:
- argue against thinking about any kind of design choice for performance reasons, eg the data structure decisions suggested in this article
- argue for a ‘fix it later’ approach to systems design. I think for lots of systems you have some ideas for how you would like them to perform, and you could, if you thought about it, often tell that some designs would never meet them, but instead you go ahead with some simple idea that handles the semantics without the performance only to discover that it is very hard to ‘optimise’ later.
naniwaduni
> It’s easy to forget what these classic CS papers were about, and I think that leads to poorly applying them today.
Notably, pretty much the entire body of discourse around structured programming is totally lost on modern programmers failing to even imagine the contrasts.
godelski
> a ‘fix it later’ approach
But what I think people don't realize is that this is exactly what tech debt is. You're moving fast but doing so makes you slow once we are no longer working in a very short timeline. That's because these issues compound. Not only do we repeat that same mistake, but we're building on top of shaky ground. So to go back and fix things ends up requiring far more effort than it would have taken to fix it early. Which by fixing early your efforts similarly compound, but this time benefiting you.
I think a good example of this is when you see people rewrite a codebase. You'll see headlines like "by switching to rust we got a 500% improvement!" Most of that isn't rust, most of that is better algorithms and design.
Of course, you can't always write your best code. There's practical constraints and no code can be perfect. But I think Knuth's advice still fits today, despite a very different audience. He was talking to people who were too obsessed with optimization while today were overly obsessed with quickly getting to some checkpoint. But the advice is the same "use a fucking profiler". That's how you find the balance and know what actually can be put off till later. It's the only way you can do this in an informed way. Yet, when was the last time you saw someone pull out a profiler? I'm betting the vast majority of HN users can't remember and I'd wager a good number never have
mjd
This is my all-time favorite paper. It's so easy to read, and there's so much to think about, so much that still applies to everyday programming and language dedign.
Also there's Knuth admitting he avoids GO TO because he is afraid of being scolded by Edsger Dijkstra.
apricot
Reading Knuth is always a pleasure.
From the paper:
"It is clearly better to write programs in a language that reveals the control structure, even if we are intimately conscious of the hardware at each step; and therefore I will be discussing a structured assembly language called PL/MIX in the fifth volume of The art of computer programming"
Looking forward to that!
bluGill
If you have benchmarked something then optimizations are not premature. People often used to 'optimize' code that was rarely run, often making the code harder to read for no gain.
beware too of premature pessimization. Don't write bubble sort just because you haven't benchmarked your code to show it is a bottleneck - which is what some will do and then incorrectly cite premature optimization when you tell them they should do better. Note that any compitenet languare has sort in the standard library that is better than bubble sort.
monkeyelite
- Knuth puts sentinels at the end of an array to avoid having to bounds check in the search. - Knuth uses the register keyword. - Knuth custom writes each data structure for each application.
hinkley
When I was young someone pointed out to me how each hype cycle we cherry-pick a couple interesting bits out of the AI space, name them something else respectable, and then dump the rest of AI on the side of the road.
When I got a bit older I realized people were doing this with performance as well. We just call this part architecture, and that part Best Practices.
ethan_smith
The famous "premature optimization" quote isn't from a dedicated paper on optimization, but from Knuth's 1974 "Structured Programming with go to Statements" paper where he was discussing broader programming methodology.
osigurdson
The real root of all evil is reasoning by unexamined phrases.
hinkley
"A clever saying proves nothing." - Voltaire
layer8
> Usually people say “premature optimization is the root of all evil” to say “small optimizations are not worth it” but […] Instead what matters is whether you benchmarked your code and whether you determined that this optimization actually makes a difference to the runtime of the program.
In my experience the latter is actually often expressed. What else would “premature” mean, other than you don’t know yet whether the optimization is worth it?
The disagreement is usually more about small inefficiencies that may compound in the large but whose combined effects are difficult to assess, compiler/platform/environment-dependent optimizations that may be pessimizations elsewhere, reasoning about asymptotic runtime (which shouldn’t require benchmarking — but with cache locality effects sometimes it does), the validity of microbenchmarks, and so on.
parpfish
The way I often hear it expressed has nothing to do with small efficiency changes or benchmarking and it’s more of a yagni/anticipating hyper scale issue. For example, adding some complexity to your code so it can efficiently handle a million users when you’re just fine writing the simple to read and write version for hat isn’t optimal but will work just fine for the twenty users you actually have.
osigurdson
It is generally better just to focus on algorithmic complexity - O(xN^k). The first version of the code should bring code to the lowest possible k (unless N is very small then who cares). Worry about x later. Don't even think about parallelizing until k is minimized. Vectorize before parallelizing.
For parallel code, you basically have to know in advance that it is needed. You can't normally just take a big stateful / mutable codebase and throw some cores at it.
subharmonicon
Love this paper and read it several times, most recently around 10 years ago when thinking about whether there were looping constructs missing from popular programming languages.
I have made the same point several times online and in person that the famous quote is misunderstood and often suggest people take the time to go back to the source and read it since it’s a wonderful read.
userbinator
I understood it to mean that optimising for speed at the expense of size is a bad idea unless there are extremely obvious performance improvements in doing so. By default you should always optimise for size.
yubblegum
Ironically, all pdfs of the famous paper have atrocious typesetting and are a pain to read.
svat
The word “typesetting” does not refer to all aspects of visual appearance, but merely to the crucial decision of where each character goes: what glyph (from the fonts available) is placed at what position on the page. This paper was first published in the ACM Computing Surveys journal, and the typesetting is fine (as you'll find if you pick up a physical copy of the journal) — I think what you're complaining about is that all PDF versions that have been put up online so far (including the official one available via https://doi.org/10.1145/356635.356640) are from the same poor scan of the journal: it's not the typesetting that is atrocious, but the scanning quality (converting the printed page into digital images).
You may also want to look at the version published in Knuth's collection called Literate Programming (with corresponding errata: https://cs.stanford.edu/~knuth/lp.html#:~:text=Errata,correc... ), and I've just uploaded a scan here: https://shreevatsa.net/tmp/2025-06/DEK-P67-Structured.progra...
yubblegum
My eyes thank you!
I think the problem with the quote is that everyone forgets the line that comes after it.
This makes it clear, in context, that Knuth defines "Premature Optimization" as "optimizing before you profile your code"@OP, I think you should lead with this. I think it gets lost by the time you actually reference it. If I can suggest, place the second paragraph after
The optimization part gets lost in the middle and this, I think, could help provide a better hook to those who aren't going to read the whole thing. Which I think how you wrote works good for that but the point (IMO) will be missed by more inattentive readers. The post is good also, so this is just a minor critique because I want to see it do better.https://dl.acm.org/doi/10.1145/356635.356640 (alt) https://sci-hub.se/10.1145/356635.356640