I think the problem with the quote is that everyone forgets the line that comes after it.
We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.
vvvvvvvvvv
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.
^^^^^^^^^^
@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
> People always use this quote wrong, and to get a feeling for that we just have to look at the original paper, and the context in which it was written.
https://dl.acm.org/doi/10.1145/356635.356640 (alt) https://sci-hub.se/10.1145/356635.356640
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.
While Amdahl’s Law is very important, its practical effects are very frequently overestimated, at least as frequently as Knuth is misquoted.
Simple problems, e.g. solving a system of equations, will usually include some non-negligible sequential part, which, according to Amdahl’s Law will limit the amount of speed-up provided by hardware parallelism.
On the other hand, complex problems, e.g. designing an integrated circuit, can usually be decomposed in a very great number of simpler subproblems that have weaker dependencies between them, than between the parts of a subproblem, so that by distributing the execution of the simple subproblems over parallel hardware that executes sequentially each subproblem you can obtain much greater acceleration factors than when attempting to parallelize the execution of each simple subproblem.
With clever decomposition of a complex problem and with good execution planning for its subtasks, it is much easier to approach the performance of an embarrassingly parallel problem, than when trying to find parallel versions of simple algorithms, whose performance is frequently limited to low values by Amdahl’s Law.
Amdahl’s Law frequently prevents you from reducing the execution time of some task from 1 minute to 1 second, but it normally does not prevent you from reducing the execution time of some task from 1 year to 1 week, because a task so complex to have required weeks, months or years before parallelization normally contains a great enough number of weakly-coupled subproblems.
> 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?
Before optimizing, I always balance the time I'll need to code the optimization and the time I (or the users of my code) will effectively gain once the optimization is there (that is, real-life time, not CPU time).
If I need three weeks to optimize a code that will run for 2 hours per month, it's not worth it.
But by not optimizing, you don't grow your profiling/optimizing skills and you miss out on a reduction in how long optimizing takes you for future work. Therefore many more codes will not meet the threshold and your skills may not grow for a long time.
> 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
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.
Well, sort of. The specific point Justice Oliver Wendell Holmes was making is pretty much the same as how it’s used today: some speech is so obviously harmful that it can’t be protected by freedom of speech. The problem is that Holmes was using it as an example of what even “the most stringent protection of free speech” would leave unprotected, and he went on to interpret the First Amendment rather less stringently, ruling that it didn’t protect anti-draft flyers.
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.
> 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?
... to the tune of about 10 cents a second, yeah. If you can hire a dev team to optimize one of those out, you plausibly come out ahead (well, vs face value).
Hopefully if you’re doing something that actually needs that much RAM you’re also making 6-figures per hour in revenue.
I’ve heard that some companies spend hundreds of millions per year on cloud hosting and it’s still worth it. I can’t even imagine that level of scale.
PS: The context in which I bring this up is a design exercise that would deal with maybe 5gb of data per month. People really over-complicate it :)
How do you come out ahead hiring an entire team to save $6/hour?
That's $6/minute, $360/hour. Granted, if you're using it at a scale approaching FTE costs, you probably want at least some reserved capacity and you're likely not paying face value, but then the comparison was never going to be rigorous anyway.
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
It is hostile because I've seen people mess up optimization too many times.
Sometimes leaving the spaghetti alone IS correct. Sometimes it isn't.
But most awful spaghetti happens because what it was asked to do was awful, IMHO.
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.
There is more to it than that.
1. Decide if optimization is even necessary.
2. Then optimize the slowest path
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.
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
One of the aphorisms I operate by is that when the order of magnitude of a problem changes, the appropriate solution to that problem may also need to change.
Here we are sitting at four to seven orders of magnitude separated from Knuth, depending on whether you mean number of devs or number of machines or size of problems tackled.
Size of machines is pretty amazing. The PDP-10s and 360/67s Knuth was talking about in 01974 were about 1 MIPS (with 32-bit or 36-bit operations) and could scale as high as 16 mebibytes of RAM. Today you can put 6 tebibytes in a 384-core two-socket AMD server that can do in excess of 10 trillion 32-bit operations per second: 6 orders of magnitude more RAM, 7 orders of magnitude more arithmetic.
But that's really understating the case, because those were large shared mainframes. Today's equivalent would be not a 2-socket rackmount server, or even a whole rack, but quite plausibly a whole data center, three more orders of magnitude. 9 orders of magnitude more RAM, 10 orders of magnitude more arithmetic.
Probably also worth mentioning that the absolute number of computers has also increased a lot; every USB-C power brick contains a multi-MIPS computer.
I agree that the number of devs has increased by only about four or five orders of magnitude. In 01974 I'd guess there might have been 50,000 programmers; my grandparents took programming classes around that time involving batch submission of punched cards, and that was a reasonably common thing at US universities. Today, Roblox has 380 million monthly active users; what percentage of them write their own games in it? And the popular programming environments Microsoft Excel and Google Sheets have over a billion users each.
> 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.
Your comment reads like a strawman argument. No one is arguing against "improving code". What are you talking about? It reads like you are misrepresenting any comment that goes against your ideas, no matter how misguided they are, by framing your ideas as obvious improvements that can only be conceivably criticized by anyone who is against good code and in favor of bad code.
It's a rehash of the old tired software developer cliche of "I cannot do wrong vs everyone around me cannot do right".
Ironically, you are the type of people Knuth's quote defends software from: those who fail to understand that using claims of "optimization" as a cheat code to push through unjustifiable changes are not improving software, and are actually making it worse.
> "Curiosity killed the cat, but satisfaction brought it back." Is practically on the same level.
This is the same strawman. It's perfectly fine to be curious. No one wants to take the magic out of you. But your sense of wonder is not a cheat code that grants you the right to push nonsense into production code. Engineers propose changes based on sound reasoning. If the engineers in your team reject a change it's unlikely you're surrounded by incompetent fools who are muffling your brilliant sense of wonder.
> If you're careful to exclude creeping featurism and architectural astronautics from the definition of 'optimization', (...)
Your comment has a strong theme of accusing anything not aligned with your personal taste as extremely bad and everything aligned with your personal taste as unquestionably good that can only possibly be opposed if there's an almost conspiratorial persecution. The changes you like are "improving code" whereas the ones proposed by third parties you don't like suddenly receive blanket accusations such as "creeping featurism and architectural astronautics".
Perhaps the problems you experience, and create, have nothing to do with optimization? Food for thought.
> This makes it clear, in context, that Knuth defines "Premature Optimization" as "optimizing before you profile your code"
As with that Google testing talk ("We said all your tests are bad, but that's not entirely true because most of you don't have any tests"), the reality is that most people don't have any profiling.
If you don't have any profiling then in fact every optimisation is premature.
A lot of people are still thinking of Knuth's comment as being about just finding the slow path or function and making it faster. What Knuth has talked about, however, and why any senior engineer who cares about performance has either been taught or discovered, is that most real optimization is in the semantics of the system and - frankly - not optimizing things but finding ways not to do them at all.
Tuning the JSON parser is not nearly as effective as replacing it with something less stupid, which is, in turn, not nearly as effective as finding ways to not do the RPC at all.
Most really performant systems of a certain age are also full of layer violations for this reason. If you care about performance (as in you are paid for it), you learn these realities pretty quickly. You also focus on retaining optionality for future optimizations by not designing the semantics of your system in a way that locks you permanently into low performance, which is unfortunately very common.
I understand the Knuth's _Premature Optimization_ saying as: (1) find the most hot code (best way to have full heat chart), (2) optimize there. That's all of it, and it really works. E.g. If you have some code that prepares data for a loop that is n^2, and you work hard on this data preparation, profile it etc., this will not give you any visible improvement, because this is one-time code. What's inside the n^2 loop is more important and optimize there, even work together and prepare the data better to allow the loop work more efficient.
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.
> 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
I 100% agree. I could have written the same comment.
The biggest way I see this is picking an architecture or programming language (cough Python) that is inherently slow. "We'll worry about performance later" they say, or frequently "it's not performance critical".
Cut to two years later, you have 200k lines of Python that spends 20 minutes loading a 10GB JSON file.
> 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.
It is interesting that there's so much discourse about the effort people have had to put into data structure and algorithm stuff for interviews, but then people refuse to take advantage of the knowledge studying that gives you towards trivial effort optimizations (aka your code can look pretty similar, just using a different data structure under the hood for example).
> Yet we should not pass up our opportunities in that critical 3 %
The funny thing is, we forgot how to write programs that spend most of their time in 3% of the code.
Profile a modern application and you see 50 level deep stacks and tiny slices of 0.3% of CPU time spent here and there. And yet these slices amount to 100%.
I think the C# dev team had an interesting way to describe that kind of profile [0]:
> In every .NET release, there are a multitude of welcome PRs that make small improvements. These changes on their own typically don’t “move the needle,” don’t on their own make very measurable end-to-end changes. However, an allocation removed here, an unnecessary bounds check removed there, it all adds up. Constantly working to remove this “peanut butter,” as we often refer to it (a thin smearing of overhead across everything), helps improve the performance of the platform in the aggregate.
[0]: https://devblogs.microsoft.com/dotnet/performance-improvemen...
Most programs inherently don't have a small bit of code they spend most of their time in. There are exceptions like scientific computing, AI, etc. But most programs have their runtime distributed through lots of code so the idea that you can ignore performance except to profile and optimise some hotspots is nonsense.
Most programs - after dealing with bugs & low hanging fruit - don't have hotspots.
I'm not sure about the "most programs" bit. I think you're forgetting whole swathes of programs like system utilities, databases, tools etc.
But, in any case, this is why we build large programs using modular architectures. You don't profile the Linux kernel hoping to find a hotspot in some obscure driver somewhere, you profile the driver directly. Same for filesystems, networking etc. Similarly we build libraries for things like arithmetic and SAT solvers etc. that will be used everywhere and optimise them directly.
Your comment reads like you're disagreeing with your parent, but in fact you are reinforcing the point. We've forgotten how to build programs like this and end up with big balls of mud that can't be profiled properly.
Pick your top 3 and optimize if you really have to. But if the whole chain is 0.3% here and there, theres very little room for large optimization wins without some redesign.
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.
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!
thank you, that's an incredible paper !
This statement in the introduction applies to so many things in CS:
I have the
uncomfortable feeling that others are making
a religion out of it, as if the conceptual
problems of programming could be solved by
a single trick, by a simple form of coding
discipline!
> 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.
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.
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.
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.
Not sure I agree. Yes algorithmic complexity is important and should always be considered. But you shouldn't ignore X. Picking Rust instead of Python only changes X but it can easily reduce X by a factor of 100 or more, and it's not something you can realistically decide later.
The real root of all evil is reasoning by unexamined phrases.
"A clever saying proves nothing." - Voltaire
- 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.
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.
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.
I mean basically what he's saying is check the impact of your optimization. Every time there's an optimization, theres a complexity and brittleness cost. However sometimes unoptimized code is actually more difficult to read than the optimized version. I mean its quite logical tbf.
I happen to have also reread the paper last week. The last time I read it was 30 years ago, closer to when it was written than to the present, and I had forgotten a lot of it. One of the few bits that stuck with me was the Shanley Design Criterion. Another was "n and a half loops".
The bit about sequential search and optimization, the topic of this whole blog post, is kind of a minor detail in the paper, despite being so eloquently phrased that it's the part everyone quotes—sometimes without even knowing what “optimization” is. There's a table of contents on its second page, which is 33 lines long, of which "A Searching Example" and "Efficiency" are lines 4 and 5. They are on pages 266–269, 3 pages of a 41-page paper. (But efficiency is an issue he considers throughout.)
Mostly the paper is about control structures, and in particular how we can structure our (imperative!) programs to permit formal proofs of correctness. C either didn't exist yet or was only known to less than five people, so its break/continue control structures were not yet the default. Knuth talks about a number of other options that didn't end up being popular.
It was a really interesting reminder of how different things looked 51 years ago. Profilers had just been invented (by Dan Ingalls, apparently?) and were still not widely available. Compilers usually didn't do register allocation. Dynamically typed languages and functional programming existed, in the form of Lisp and APL, but were far outside the mainstream because they were so inefficient. You could reliably estimate a program's speed by counting machine instructions. People were sincerely advocating using loops that didn't allow "break", and subroutines without early "return", in the interest of building up their control flow algebraically. Knuth considered a recursive search solution to the N-queens problem to be interesting enough to mention it in CACM; similarly, he explains the tail-recursion optimization as if it's not novel but at least a bit recondite, requiring careful explanation.
He mentions COBOL, BCPL, BLISS, Algol W, Algol 60, Algol 68, other Algols, PL/I (in fact including some example code), Fortran, macro assemblers, "structured assemblers", "Wirth's Pascal language [97]", Lisp, a PDP-10 Algol compiler called SAIL (?), META-II, MIXAL, PL360, and something called XPL, but not Smalltalk, CLU, APL, FORTH, or BASIC.
He points out that it would be great for languages to bundle together the set of subroutines for operating on a particular data type, as Smalltalk and CLU did, but he doesn't mention CLU; it had only been introduced in the previous year. But he's clearly thinking along those lines (p.295):
> (...) it turns out that a given level of abstraction often involves several related routines and data definitions; for example, when we decide to represent a table in a certain way, we also want to specify the routines for storing and fetching data from that table. The next generation of languages will probably take into account such related routines.
Often when I read old papers, or old software documentation like the TENEX EXEC manual, it's obvious why the paths not taken were not taken; what we ended up doing is just obviously better. This paper is not like that. Most of the alternatives mentioned seem like they might have turned out just as well as what we ended up with.
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.
That's literally the first sentence of the article.
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.
Wait... people understood "premature optimisation" to mean "small optimisations are not worth it"? I've always understood it to mean exactly what it's supposed to mean, namely don't optimise something until you've shown that it's actually needed. I honestly don't know how it could be interpreted any other way.
Ironically, all pdfs of the famous paper have atrocious typesetting and are a pain to read.
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...
My eyes thank you!
It's no longer relevant. It was written when people were writing IBM operating systems in assembly language.
Things have changed.
Remember this: "speed is a feature"?
If you need fast softwqare to make it appealing then make it fast.
I will say I have worked on projects where sales and upper management were both saying the same thing: customers don't like that our product is slow(er than a competitors), and the devs just shrug and say we've already done everything we can. In one case the most senior devs even came up charts to prove this was all they were going to get.
Somehow I found 40%. Some of it was clever, a lot of it was paying closer attention to the numbers, but most of it was grunt work.
Besides the mechanical sympathy, the other two main tools were 1) stubbornness, and 2) figuring out how to group changes along functional testing boundaries, so that you can justify making someone test a change that only improves perf by 1.2% because they're testing a raft of related changes that add up to more than 10%.
Most code has orphaned performance improvements in 100 little places that all account for half of the runtime because nobody can ever justify going in and fixing them. And those can also make parallelism seem unpalatable due to Amdahl.