9 ms·

Revisiting Knuth's “Premature Optimization” Paper

194 points by signa11 1y ago

mjd 1y ago
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. https://pic.plover.com/knuth-GOTO.pdf https://pic.plover.com/knuth-GOTO.pdf
- apricot 1y ago
  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!
- nick__m 1y ago
  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! Like Brooks said: No Silver Bullets
- Joker_vD 1y ago
  Yeah, it's one of my favourites as well. And it weirds me out that the "premature optimization" bit is the most quoted piece of that paper — arguably, that's the least interesting part of it, compared to the musings on the language design and (semi)automatic transformation of algorithms! I personally find that "break/continue" with (optionally labelled) loops cover about 95% of GOTO's use cases today (including "one-and-a-half" loops), although e.g. Rust and Zig, with their expression-oriented design (and support for sum types) offer an option to experiment with Zahn's event mechanism... but usually factoring an inner loop body into a separate function is a more clear-to-read approach (as for efficiency? Hopefully you have a decent inliner idk). The only thing I truly miss, occasionally, is a way to concisely write an one-and-a-half range/FOR loop. Something like this: for key, value in enumerate(obj): emit(f'{key}={value}') between: emit(',') When you have a generic "while True:" loop, conditional "break" works fine enough, but here? Ugh.
  - int_19h 1y ago
    I might be missing something, but how would `goto` improve matters on that for-loop? It seems to me that the fundamental problem here is rather than there's no easy way to check whether this is the last iteration or not, but that is orthogonal to goto vs break.
    - Joker_vD 1y ago
      Well, what you actually need is to make the first iteration special — generally, you can detect whether the iteration was last only after you've already finished it, but special-casing the very first iteration can be done. You put the "between" block at the beginning of the loop body, but start the loop by jumping over it into the middle. It works even better with "for" loops, they desugar into: i = START; if (i > END) goto _after_loop; goto _loop_body; while (1) { BETWEEN; _loop_body: BODY; _loop_test: // "continue" would desugar into "goto _loop_test". i++; if (i > END) break; } _after_loop: ... which, if you throw away the "BETWEEN" part, is a standard way to compile for-loops, with pre-test and loop inversion. But writing this by hand is just... no. I'd rather add either a boolean flag, or throw in "if i > 0: ..." or "if i != END: ..." guard. Sometimes those even get optimized away, see e.g. [0] — both of loops there desugar into pretty much this; but it's brittle, changing "if (i > START)" into "if (i != START)" in the second function duplicates the loop body, and if you make it sufficient larger than a single function call, the elided conditional branch rematerializes again. But yes, the goto doesn't help much with it = iter(...) try: loop_var = next(it) except StopIteration: return body(loop_var) while True: try: loop_var = next(it) except StopIteration: break between(loop_var) body(loop_var) loop where you must crank the iterator before every iteration; there you have to either duplicate some code, or count your iterations and check the current number. [0] https://godbolt.org/z/Y4hv4oYdP https://godbolt.org/z/Y4hv4oYdP
      - int_19h 1y ago
        Sather had a very interesting approach to extensible looping constructs that allows for this kind of flexibility: https://www.gnu.org/software/sather/docs-1.2/tutorial/iterators.html https://www.gnu.org/software/sather/docs-1.2/tutorial/iterat... With this machinery, you could declare an iterator like so: first!(): BOOL is yield true; loop yield false; end; end; And then the case that you describe would be something like: a: ARRAY{INT} := |1,2,3|; loop if not first! then emit(','); end; x := a.aelt!; emit(x); end; Which in practice amounts to the same thing as an explicit boolean flag - it's just hidden inside the internal state of first! that the loop has to maintain - but it sure is a lot clearer. In Python and the likes, I suppose you could do the same with zip() if you aren't already using enumerate(): def first_or_not(): yield True while True: yield False: for value, is_first in zip(obj, first_or_not()): if not is_first: emit(',') emit(f'{key}={value}') But this gets unnecessary verbose compared to Sather's implicit zip. Regarding the ability to optimize away the version with an index check or equivalent, I was curious if C++ compilers these days are up to snuff if you choose to do something similar to Python. Turns out that Clang can indeed turn this: void emit_array(span<char*> xs) { for (auto [x, i] : views::zip(xs, views::iota(0))) { if (i) { emit(","); } emit(x); } } into optimized assembly that doesn't perform the check inside the loop. But it does it by duplicating emit(x) so that it always runs once before the first iteration, and then checking for >1 item and only looping then. Ditto for this Rust code: fn emit_array(xs: &[String]) { for (i, x) in xs.into_iter().enumerate() { if i != 0 { emit(","); } emit(&x); } } Unfortunately both g++ and MSVC struggle to optimize this equally well; both end up using a flag that is repeatedly checked in loop body. (https://godbolt.org/z/bb79jW87Y https://godbolt.org/z/bb79jW87Y)
subharmonicon 1y ago
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.
wewewedxfgdf 1y ago
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.
- hinkley 1y ago
  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.
godelski 1y ago
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. ^^^^^^^^^^ 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 > 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. 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 https://dl.acm.org/doi/10.1145/356635.356640 (alt) https://sci-hub.se/10.1145/356635.356640 https://sci-hub.se/10.1145/356635.356640
- Swizec 1y ago
  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. https://en.wikipedia.org/wiki/Amdahl%27s_law https://en.wikipedia.org/wiki/Amdahl%27s_law
  - godelski 1y ago
    > It sounds obvious when spelled out but it blew my mind. I think there's a weird thing that happens with stuff like this. Cliches are a good example, and I'll propose an alternative definition to them. 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 At least, it works for a subset of cliches. Like "road to hell," "read between the lines," Goodheart's Law, and I think even Amdahl's Law fits (though certainly not others. e.g. some are bastardized, like Premature Optimization or "blood is thicker than water"). Essentially they are "easier said than done," so require system 2 thinking to resolve but we act like system 1 will catch them. 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
bluGill 1y ago
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.
- sgarland 1y ago
  Most of the time, the arguments aren’t even that cogent, they’re more along the lines of “I’m not going to specify the columns I need from this SELECT query, because that’s premature optimization.”
yubblegum 1y ago
Ironically, all pdfs of the famous paper have atrocious typesetting and are a pain to read.
- svat 1y ago
  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 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,corrections%20to%20errors 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.programming.with.go.to.statements-LP.pdf https://shreevatsa.net/tmp/2025-06/DEK-P67-Structured.progra...
  - yubblegum 1y ago
    My eyes thank you!
- aitchnyu 1y ago
  The typesetting expert's papers are hard on the eyes. The algorithm expert's programs are not executed.
layer8 1y ago
> 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 1y ago
  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.
userbinator 1y ago
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.
dan-robertson 1y ago
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.
- godelski 1y ago
  > a ‘fix it later’ approach Oh man, I hate how often this is used. Everyone knows there's nothing more permanent than a temporary fix lol. 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
osigurdson 1y ago
The real root of all evil is reasoning by unexamined phrases.
- hinkley 1y ago
  "A clever saying proves nothing." - Voltaire
osigurdson 1y ago
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.
- IshKebab 1y ago
  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.
  - osigurdson 1y ago
    Hmmm. I wasn't thinking about making performance decisions that early in a project - more like an optimization approach for a given feature / work. In terms of deciding on what programming language to use for a project, that is a complicated one. Usually it is some combination of the team and the problem I suppose.
- jltsiren 1y ago
  Choose an algorithm that's reasonably efficient and easy to implement. Then parallelize if it wasn't fast enough. Then try to find a better algorithm. And only then vectorize. Pick the low-hanging fruit first, and only resort to options that require more work and make the code less maintainable if that wasn't enough. Software engineers and computer scientists are often reluctant to parallelize their code, because they have learned that it's difficult and full of hidden pitfalls. But then they lose the performance gains from multithreaded loops and other simple approaches, which are often essentially free. Multithreaded code is not particularly difficult or dangerous, as long as you are not trying to be clever.
  - osigurdson 1y ago
monkeyelite 1y ago
- 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 1y ago
  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.
  - sitkack 1y ago
    I like to call anything I don't like "anti-patterns".
- bluGill 1y ago
  When Knuth wrote his paper compilers/optimizer were not nearly as good as today, and CPUs were much more deterministic (only disk access shows the issues we now see with cache misses). Most of his optimizations are things that the compiler will do better than you can (most is not all!) and so not even worth thinking about. Meanwhile the compiler will almost never turn a O(n^2) into O(n*ln(n)) despite that resulting in a much faster speedup than anything the compiler can do.
  - monkeyelite 1y ago
    Knuth does this today. And a compiler will never make sentinels for you. Most of these tricks still work and have a measurable difference.
ethan_smith 1y ago
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.
- tyrust 1y ago
  That's literally the first sentence of the article.
kragen 1y ago
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.
alexey-salmin 1y ago
> 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%.
- aw1621107 1y ago
  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-improvements-in-net-8/#peanut-butter https://devblogs.microsoft.com/dotnet/performance-improvemen...
  - BanterTrouble 1y ago
    They are describing "marginal gains theory". Lots of small improvements to something add up to a larger more tangible improvement.
  - sfn42 1y ago
    This is a bit different because C# is designed and implemented by industry experts - far above the average code monkey in terms of skill, understanding and experience, with added help from community experts, and the software in question is used by millions of systems all over the world. Practically every part of C# is a hot path because it runs on probably billions of devices every minute of every day. This code is worth micro-optimizing. A 1% improvement in a popular C# library probably saves megawatts of electricity (not to mention the time saves) on a global scale. Most code is not like that at all. Most code is not worth putting this kind of effort into. Most code is fine being 10% or even 500% slower than it technically could be because computers are lightning fast and can crunch numbers at an incredible speed. Even if the computer is doing 5 times as much work as it needs to it'll still be instant for most use cases. The problem for these kinds of applications arises when it's not doing 5 times as much work as it needs to but 5000 times or 5 million times. Or when the data is just really large and even the optimal solution would take a noticeable amount of time.
globular-toast 1y ago
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.
- bluGill 1y ago
  It is sad how often people cite premature optimization in the real world even when it isn't premature. Using a good algorithm is never premature optimization, particularly when the good algorithm is likely built into your language as well. Likewise if you have run the profiler it is not premature optimization, and running the profiler to find those places is not premature optimization.
another_twist 1y ago
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.
p0w3n3d 1y ago
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.
- osigurdson 1y ago
  Suggest not over indexing on this approach. The profiler will not always identify an easily fixable hotspot. Performance should not entirely be post hoc. Some upfront investment pays off. Sure, not every algorithm matters but with some basic upfront investment (like don't do O(N^2) when O(N) is possible, or don't hit the DB for every item in a loop) will pay off. The alternative can be weeks / months of profiling and debugging. The fixed code often introduces other bugs as code built upon it makes various assumptions. I'm speaking from experience in a large code base where people liked to use the "root of all evil" argument quite a bit at one time.
  - p0w3n3d 1y ago
    You're right, we should keep our development skills in shape and hold on to sanity when writing code. Especially n+1 queries and other types of calls to another system would cause problems invisible for profiler (some kind of profilers?). That's why when converting data from one list to another I used to always initialize the latter with the known size (now I use Java streams mostly) On the other hand there is me doing JMH microbenchmarking in code that was eventually parsing configuration files (only once at startup) which was the moment I learnt the said quote from Donald Knuth from the colleagues reviewing my code
meindnoch 1y ago
After 20 years of programming, I've came to the following realization: On a long enough timeline, the probability that someone will call your code in a for-loop approaches 1.
- hidroto 1y ago
  and that is how we end up with this 'accidentally quadratic' software https://news.ycombinator.com/item?id=9217048 https://news.ycombinator.com/item?id=9217048
svara 1y ago
In practice repetition of this quote more often than not leads to a lazy attitude of "don't think about performance, it's too complicated, measure first and then let's talk". In my experience all great programmers think about performance from the moment they start thinking about a problem. Like, you're writing an O(n^2) nested loop over an array that's not going to be tiny? Get out of here! That just shouldn't happen and talking about "premature optimization" points in exactly the wrong direction.
bob1029 1y ago
I think the best way to go about optimization is to maintain a constant baseline level of mechanical sympathy with the computer's architecture. If you burn into your soul the table of NUMA latencies and really accept the inevitable conclusions regarding practical computation, a lot of the optimization discussion simply boils down to keeping the closest cache as hot as possible as often as possible. Put differently, if you can get the working set to ~fit in L1, then you have nothing to worry about. The CPU is faster than most people can reason about now. You can talk to L1 1000x before you can talk to the GPU 1x. This stuff makes a ridiculous difference when applied correctly. Context switching and communication between threads is where most developers begin to lose the rabbit. Very often a problem can be solved on one physical core much faster than if you force it to be solved across many physical cores.
SleepyMyroslav 1y ago
(meta) I am probably wasting my time commenting on linked article here. Nobody does that /s. I don't think the measurements support conclusion that well. What I want to have when I see those measurements: I want language abstract machine and compiler to not get in the way I want code on certain platforms to perform. This is currently not what I get at all. The language is actively working against me. For example, I can not read cache line from an address because my object may not span long enough. The compiler has its own direction at best. This means there is no way to specify things, and all I can do is test compiler output after each minor update. In a multi-year project such updates can happen dozens of times! The ergonomics of trying to specify things actually getting worse. The example with assembly is similar to my other experiences: the compiler ignores even intrinsics now. If it wants to optimize, it does. I can't run to someone else for magic library solutions every time I need to write code. I need to be able to get things done in a reasonable amount of time. It is my organization development process that should decide if the solution I used should be part of some library or not. It usually means that efforts that cover only some platforms and only some libraries are not that universally applicable to my platforms and my libraries as folks at language conferences think /s. Disclaimer. I work in gamedev.
skeezyboy 1y ago
the reason were still arguing over this is because knuth cant say things concisely; he didnt communicate this idea succintly enough
- skeezyboy 1y ago
  howd i get downvoted for that
lo0dot0 1y ago
It's also good practice to chose an appropriate language for the problem. It's not premature optimisation to use a compiled language instead of Python when you already know the code will run thousands of times in a loop because of the application and use a lot of electrical energy in the process.

194 points by signa11 1y ago

mjd 1y ago

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. https://pic.plover.com/knuth-GOTO.pdf https://pic.plover.com/knuth-GOTO.pdf

apricot 1y ago
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!
nick__m 1y ago
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! Like Brooks said: No Silver Bullets
Joker_vD 1y ago
Yeah, it's one of my favourites as well. And it weirds me out that the "premature optimization" bit is the most quoted piece of that paper — arguably, that's the least interesting part of it, compared to the musings on the language design and (semi)automatic transformation of algorithms! I personally find that "break/continue" with (optionally labelled) loops cover about 95% of GOTO's use cases today (including "one-and-a-half" loops), although e.g. Rust and Zig, with their expression-oriented design (and support for sum types) offer an option to experiment with Zahn's event mechanism... but usually factoring an inner loop body into a separate function is a more clear-to-read approach (as for efficiency? Hopefully you have a decent inliner idk). The only thing I truly miss, occasionally, is a way to concisely write an one-and-a-half range/FOR loop. Something like this: for key, value in enumerate(obj): emit(f'{key}={value}') between: emit(',') When you have a generic "while True:" loop, conditional "break" works fine enough, but here? Ugh.
- int_19h 1y ago
  I might be missing something, but how would `goto` improve matters on that for-loop? It seems to me that the fundamental problem here is rather than there's no easy way to check whether this is the last iteration or not, but that is orthogonal to goto vs break.
  - Joker_vD 1y ago
    Well, what you actually need is to make the first iteration special — generally, you can detect whether the iteration was last only after you've already finished it, but special-casing the very first iteration can be done. You put the "between" block at the beginning of the loop body, but start the loop by jumping over it into the middle. It works even better with "for" loops, they desugar into: i = START; if (i > END) goto _after_loop; goto _loop_body; while (1) { BETWEEN; _loop_body: BODY; _loop_test: // "continue" would desugar into "goto _loop_test". i++; if (i > END) break; } _after_loop: ... which, if you throw away the "BETWEEN" part, is a standard way to compile for-loops, with pre-test and loop inversion. But writing this by hand is just... no. I'd rather add either a boolean flag, or throw in "if i > 0: ..." or "if i != END: ..." guard. Sometimes those even get optimized away, see e.g. [0] — both of loops there desugar into pretty much this; but it's brittle, changing "if (i > START)" into "if (i != START)" in the second function duplicates the loop body, and if you make it sufficient larger than a single function call, the elided conditional branch rematerializes again. But yes, the goto doesn't help much with it = iter(...) try: loop_var = next(it) except StopIteration: return body(loop_var) while True: try: loop_var = next(it) except StopIteration: break between(loop_var) body(loop_var) loop where you must crank the iterator before every iteration; there you have to either duplicate some code, or count your iterations and check the current number. [0] https://godbolt.org/z/Y4hv4oYdP https://godbolt.org/z/Y4hv4oYdP
    - int_19h 1y ago
      Sather had a very interesting approach to extensible looping constructs that allows for this kind of flexibility: https://www.gnu.org/software/sather/docs-1.2/tutorial/iterators.html https://www.gnu.org/software/sather/docs-1.2/tutorial/iterat... With this machinery, you could declare an iterator like so: first!(): BOOL is yield true; loop yield false; end; end; And then the case that you describe would be something like: a: ARRAY{INT} := |1,2,3|; loop if not first! then emit(','); end; x := a.aelt!; emit(x); end; Which in practice amounts to the same thing as an explicit boolean flag - it's just hidden inside the internal state of first! that the loop has to maintain - but it sure is a lot clearer. In Python and the likes, I suppose you could do the same with zip() if you aren't already using enumerate(): def first_or_not(): yield True while True: yield False: for value, is_first in zip(obj, first_or_not()): if not is_first: emit(',') emit(f'{key}={value}') But this gets unnecessary verbose compared to Sather's implicit zip. Regarding the ability to optimize away the version with an index check or equivalent, I was curious if C++ compilers these days are up to snuff if you choose to do something similar to Python. Turns out that Clang can indeed turn this: void emit_array(span<char*> xs) { for (auto [x, i] : views::zip(xs, views::iota(0))) { if (i) { emit(","); } emit(x); } } into optimized assembly that doesn't perform the check inside the loop. But it does it by duplicating emit(x) so that it always runs once before the first iteration, and then checking for >1 item and only looping then. Ditto for this Rust code: fn emit_array(xs: &[String]) { for (i, x) in xs.into_iter().enumerate() { if i != 0 { emit(","); } emit(&x); } } Unfortunately both g++ and MSVC struggle to optimize this equally well; both end up using a flag that is repeatedly checked in loop body. (https://godbolt.org/z/bb79jW87Y https://godbolt.org/z/bb79jW87Y)

subharmonicon 1y ago

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.

wewewedxfgdf 1y ago

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.

hinkley 1y ago
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.

godelski 1y ago

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. ^^^^^^^^^^ 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 > 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. 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 https://dl.acm.org/doi/10.1145/356635.356640 (alt) https://sci-hub.se/10.1145/356635.356640 https://sci-hub.se/10.1145/356635.356640

Swizec 1y ago
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. https://en.wikipedia.org/wiki/Amdahl%27s_law https://en.wikipedia.org/wiki/Amdahl%27s_law
- godelski 1y ago
  > It sounds obvious when spelled out but it blew my mind. I think there's a weird thing that happens with stuff like this. Cliches are a good example, and I'll propose an alternative definition to them. 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 At least, it works for a subset of cliches. Like "road to hell," "read between the lines," Goodheart's Law, and I think even Amdahl's Law fits (though certainly not others. e.g. some are bastardized, like Premature Optimization or "blood is thicker than water"). Essentially they are "easier said than done," so require system 2 thinking to resolve but we act like system 1 will catch them. 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

bluGill 1y ago

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.

sgarland 1y ago
Most of the time, the arguments aren’t even that cogent, they’re more along the lines of “I’m not going to specify the columns I need from this SELECT query, because that’s premature optimization.”

yubblegum 1y ago

Ironically, all pdfs of the famous paper have atrocious typesetting and are a pain to read.

svat 1y ago
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 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,corrections%20to%20errors 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.programming.with.go.to.statements-LP.pdf https://shreevatsa.net/tmp/2025-06/DEK-P67-Structured.progra...
- yubblegum 1y ago
  My eyes thank you!
aitchnyu 1y ago
The typesetting expert's papers are hard on the eyes. The algorithm expert's programs are not executed.

layer8 1y ago

> 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 1y ago
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.

userbinator 1y ago

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.

dan-robertson 1y ago

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.

godelski 1y ago
> a ‘fix it later’ approach Oh man, I hate how often this is used. Everyone knows there's nothing more permanent than a temporary fix lol. 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

osigurdson 1y ago

The real root of all evil is reasoning by unexamined phrases.

hinkley 1y ago
"A clever saying proves nothing." - Voltaire

osigurdson 1y ago

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.

IshKebab 1y ago
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.
- osigurdson 1y ago
  Hmmm. I wasn't thinking about making performance decisions that early in a project - more like an optimization approach for a given feature / work. In terms of deciding on what programming language to use for a project, that is a complicated one. Usually it is some combination of the team and the problem I suppose.
jltsiren 1y ago
Choose an algorithm that's reasonably efficient and easy to implement. Then parallelize if it wasn't fast enough. Then try to find a better algorithm. And only then vectorize. Pick the low-hanging fruit first, and only resort to options that require more work and make the code less maintainable if that wasn't enough. Software engineers and computer scientists are often reluctant to parallelize their code, because they have learned that it's difficult and full of hidden pitfalls. But then they lose the performance gains from multithreaded loops and other simple approaches, which are often essentially free. Multithreaded code is not particularly difficult or dangerous, as long as you are not trying to be clever.
- osigurdson 1y ago

monkeyelite 1y ago

- 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 1y ago
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.
- sitkack 1y ago
  I like to call anything I don't like "anti-patterns".
bluGill 1y ago
When Knuth wrote his paper compilers/optimizer were not nearly as good as today, and CPUs were much more deterministic (only disk access shows the issues we now see with cache misses). Most of his optimizations are things that the compiler will do better than you can (most is not all!) and so not even worth thinking about. Meanwhile the compiler will almost never turn a O(n^2) into O(n*ln(n)) despite that resulting in a much faster speedup than anything the compiler can do.
- monkeyelite 1y ago
  Knuth does this today. And a compiler will never make sentinels for you. Most of these tricks still work and have a measurable difference.

ethan_smith 1y ago

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.

tyrust 1y ago
That's literally the first sentence of the article.

kragen 1y ago

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.

alexey-salmin 1y ago

> 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%.

aw1621107 1y ago
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-improvements-in-net-8/#peanut-butter https://devblogs.microsoft.com/dotnet/performance-improvemen...
- BanterTrouble 1y ago
  They are describing "marginal gains theory". Lots of small improvements to something add up to a larger more tangible improvement.
- sfn42 1y ago
  This is a bit different because C# is designed and implemented by industry experts - far above the average code monkey in terms of skill, understanding and experience, with added help from community experts, and the software in question is used by millions of systems all over the world. Practically every part of C# is a hot path because it runs on probably billions of devices every minute of every day. This code is worth micro-optimizing. A 1% improvement in a popular C# library probably saves megawatts of electricity (not to mention the time saves) on a global scale. Most code is not like that at all. Most code is not worth putting this kind of effort into. Most code is fine being 10% or even 500% slower than it technically could be because computers are lightning fast and can crunch numbers at an incredible speed. Even if the computer is doing 5 times as much work as it needs to it'll still be instant for most use cases. The problem for these kinds of applications arises when it's not doing 5 times as much work as it needs to but 5000 times or 5 million times. Or when the data is just really large and even the optimal solution would take a noticeable amount of time.

globular-toast 1y ago

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.

bluGill 1y ago
It is sad how often people cite premature optimization in the real world even when it isn't premature. Using a good algorithm is never premature optimization, particularly when the good algorithm is likely built into your language as well. Likewise if you have run the profiler it is not premature optimization, and running the profiler to find those places is not premature optimization.

another_twist 1y ago

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.

p0w3n3d 1y ago

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.

osigurdson 1y ago
Suggest not over indexing on this approach. The profiler will not always identify an easily fixable hotspot. Performance should not entirely be post hoc. Some upfront investment pays off. Sure, not every algorithm matters but with some basic upfront investment (like don't do O(N^2) when O(N) is possible, or don't hit the DB for every item in a loop) will pay off. The alternative can be weeks / months of profiling and debugging. The fixed code often introduces other bugs as code built upon it makes various assumptions. I'm speaking from experience in a large code base where people liked to use the "root of all evil" argument quite a bit at one time.
- p0w3n3d 1y ago
  You're right, we should keep our development skills in shape and hold on to sanity when writing code. Especially n+1 queries and other types of calls to another system would cause problems invisible for profiler (some kind of profilers?). That's why when converting data from one list to another I used to always initialize the latter with the known size (now I use Java streams mostly) On the other hand there is me doing JMH microbenchmarking in code that was eventually parsing configuration files (only once at startup) which was the moment I learnt the said quote from Donald Knuth from the colleagues reviewing my code

meindnoch 1y ago

After 20 years of programming, I've came to the following realization: On a long enough timeline, the probability that someone will call your code in a for-loop approaches 1.

hidroto 1y ago
and that is how we end up with this 'accidentally quadratic' software https://news.ycombinator.com/item?id=9217048 https://news.ycombinator.com/item?id=9217048

svara 1y ago

In practice repetition of this quote more often than not leads to a lazy attitude of "don't think about performance, it's too complicated, measure first and then let's talk". In my experience all great programmers think about performance from the moment they start thinking about a problem. Like, you're writing an O(n^2) nested loop over an array that's not going to be tiny? Get out of here! That just shouldn't happen and talking about "premature optimization" points in exactly the wrong direction.

bob1029 1y ago

I think the best way to go about optimization is to maintain a constant baseline level of mechanical sympathy with the computer's architecture. If you burn into your soul the table of NUMA latencies and really accept the inevitable conclusions regarding practical computation, a lot of the optimization discussion simply boils down to keeping the closest cache as hot as possible as often as possible. Put differently, if you can get the working set to ~fit in L1, then you have nothing to worry about. The CPU is faster than most people can reason about now. You can talk to L1 1000x before you can talk to the GPU 1x. This stuff makes a ridiculous difference when applied correctly. Context switching and communication between threads is where most developers begin to lose the rabbit. Very often a problem can be solved on one physical core much faster than if you force it to be solved across many physical cores.

SleepyMyroslav 1y ago

(meta) I am probably wasting my time commenting on linked article here. Nobody does that /s. I don't think the measurements support conclusion that well. What I want to have when I see those measurements: I want language abstract machine and compiler to not get in the way I want code on certain platforms to perform. This is currently not what I get at all. The language is actively working against me. For example, I can not read cache line from an address because my object may not span long enough. The compiler has its own direction at best. This means there is no way to specify things, and all I can do is test compiler output after each minor update. In a multi-year project such updates can happen dozens of times! The ergonomics of trying to specify things actually getting worse. The example with assembly is similar to my other experiences: the compiler ignores even intrinsics now. If it wants to optimize, it does. I can't run to someone else for magic library solutions every time I need to write code. I need to be able to get things done in a reasonable amount of time. It is my organization development process that should decide if the solution I used should be part of some library or not. It usually means that efforts that cover only some platforms and only some libraries are not that universally applicable to my platforms and my libraries as folks at language conferences think /s. Disclaimer. I work in gamedev.

skeezyboy 1y ago

the reason were still arguing over this is because knuth cant say things concisely; he didnt communicate this idea succintly enough

skeezyboy 1y ago
howd i get downvoted for that

lo0dot0 1y ago

It's also good practice to chose an appropriate language for the problem. It's not premature optimisation to use a compiled language instead of Python when you already know the code will run thousands of times in a loop because of the application and use a lot of electrical energy in the process.