Stop Misquoting Donald Knuth!

DISCLAIMER: The following are my own personal opinions and are not shared, sanctioned or endorsed by anybody in particular, especially my employer. Any criticisms expressed herein are of a general nature and are neither inspired by nor directed at any person, entity, or product in particular.  Links to other online materials are used only for the purposes of illustration and are not meant to disparage or hurt the feelings of anybody in particular.

The Free Lunch ended a long time ago, and there are indications that the multi-core free lunch won’t last much longer.  Special purpose accelerators will become much more common, but by definition they are special purpose and cannot solve every problem.  We need to start paying as much attention to the performance, efficiency, and scalability of our code as we do to all the other factors. Will this waste resources is as important a question as will this break encapsulation or will this be maintainable.  I am not the only person to have these ideas. Lots of other people have discussed it relatively recently.  The fact that not all of them are graphics people suggests that we may be seeing the beginnings of a move in the right direction.

Things People Say

The are few pieces of conventional wisdom that we often hear about code optimization:

  • Optimize code only when necessary
  • Only optimize the bottlenecks, and only after they are identified
  • Micro-optimization is a waste of time
  • Constant factors don’t matter
  • Engineering time costs more than CPU time
  • The machine’s so fast it won’t matter
  • Nobody will notice an occasional delay
  • We can just buy more servers

It’s easy to see where this attitude comes from.

For most of the development cycle, most teams spend most of their time writing code, testing code, reviewing code, debugging code, refactoring code, and ensuring that their functional requirements have been met (all the while reacting to inevitable design changes). Putting it all together takes time, a lot of time, and there are a lot of things competing for our attention, and as a result, running time is usually far from people’s minds, because so much effort is required just to get things running at all.

Performance tuning is neither necessary nor desirable once the performance is within the required limits. Considerable time and thus money can be wasted chasing small inefficiencies, and in many cases the effort is rightly deemed futuile if the running time is already less than the time it takes a human being to notice that the job is done. Adequate is often good enough, and better still if it can be pulled off more quickly and with less effort.

Modern computers are fast, ridiculously fast. Our machines are so absurdly fast that the threshold of adequacy is easily reached. Typical applications can and do waste an incredible amount of their capacity and get away with it.

Donald Knuth once wrote these unfortunate words:

” We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.”

This statement is often quoted in an attempt to de-emphasize code performance in favor of other factors which are considered more important:

  • Ease of use
  • Rapid development
  • Clarity and readability
  • Reusability
  • Risk of accidental bugs
  • Extensibility
  • Elegance
  • Object-Oriented Purity

There is a whole class of developer out there who rejects any optimization beyond occasional attention to asymptotic complexity.  They believe that their responsibility ends once they’ve picked the theoretical best algorithm, and that at this point things are as good as they’re likely to get.  Sometimes, they don’t even go that far, settling for n log n because somebody already wrote Quicksort for them.  They either won’t bother to do better, or they don’t think they can.  Note that the one can cause the other.

The Slippery Slope

The problem with this attitude is that it leads to complacency.  It allows the cycle eaters to multiply out of control.  We gloss over the small things, forgetting that the sum of a large number of small numbers is itself a large number. Waste creeps in, little by little, because we let it.

Bounds checks here, and exceptions there.

Integer overflow checks.

Passing smart pointers by value for no particular reason.

Using the wrong integer type.

Extra indirections just to speed up our compiles.

Extra temporary allocations for stylistic reasons.

Ignoring data locality.

All that stuff Mike Acton wrote about.

I’ve listed lots of relatively low-level things up there, but that’s just because it’s the level I work at. The same sorts of mismanagement can and do occur at every level of the stack, and in every language. An extra string copy here, a spurious string->int conversion there. A missing database index, a poor schema design, webpages loading copious amounts of JavaScript. The same mentality on a different scale. We just don’t take small efficiencies seriously, and there are consequences.

The worst sorts of slippery slopes are so close to flat that we don’t realize we’re on them.  Sometimes, our users’ machines are so ridiculously fast that the waste goes unnoticed, but other times, our user experiences annoying and unnecessary delay. And still other times, we utterly fail to function under load.

If you tell yourself, it’s only a malloc, it’s nothing, and you do this often enough, you will end up with 25000 temporary allocs for a single keystroke.  They may only take 50ns each, but I type 529 characters per minute.

When these sorts of things are pointed out, people aught to respond by fixing the problem, so that they can deliver a better product.  Instead, they typically start arguing with you about why it’s not that big a deal.

Knuth and Small Efficiencies

The irony about Knuth’s quote is that the people who most often quote it would be horrified by its original context. Knuth made this statement in an article in which he argued in favor of the careful use of go-to statements for micro-optimization in performance-intensive loops. He would probably flunk a modern code review.  You can find the quote in the linked PDF, page 8, second column.

Even more ironic is something else that Knuth wrote in the same article. This gem of a paragraph, published in 1974, still rings true 40 years later:

The improvement in speed from Example 2 to Example 2a is only about 12%, and many people would pronounce that insignificant. The conventional wisdom shared by many of today’s software engineers calls for ignoring efficiency in the small; but I believe this is simply an overreaction to the abuses they see being practiced by penny-wise- and-pound-foolish programmers, who can’t debug or maintain their “optimized” programs. In established engineering disciplines a 12% improvement, easily obtained, is never considered marginal; and I believe the same viewpoint should prevail in software engineering. Of course I wouldn’t bother making such optimizations on a one-shot job, but when it’s a question of preparing quality programs, I don’t want to restrict myself to tools that deny me such efficiencies.

Considering performance in the small is not “premature optimization”, it is simply good engineering, and good craftsmanship. As software engineers, we have largely forgotten about our obligation to create quality programs where efficiency is concerned. We have built for ourselves a culture in which constant factors are the compiler’s problem and the hardware’s problem, in which our productivity, comfort, and profit are more important than the effective utilization of the user’s resources, and the quality of their experience under load.

As a user, I am tired of this.

I am tired of slow load times. The ratio of bytes loaded to load time should be very close to the I/O throughput of the machine. If it is not, somebody is wasting my time.  I am tired of programs not stopping immediately, the instant I click the little X, because somebody is traversing a large reference graph and doing lots of itty-bitty deletes. I am tired of seeing progress bars and splash screens.

As a developer, I am tired of my IDE slowing to a crawl when I try to compile multiple projects at a time. I am tired of being unable to trust the default behavior of the standard containers. I am tired of my debug builds being unusably slow by default.

As a citizen of planet Earth, I am tired of all the electricity that gets wasted by organizations who throw hardware at software problems, when a more efficient implementation might allow them to consume much, much less, and spend less money powering it all.

We need to stop wasting our customers’ resources.  We need to build a developer culture in which efficiency loss is not tolerated unless it is done consciously, to satisfy a functional requirement, or achieve some tangible benefit beyond mere expediency.    This is not merely a matter of taste or opinion, it is a matter of professional ethics.



    • Rob K

      It sure seems to me that most of the stuff you’re complaining about here really isn’t about optimization. It’s more about crappy design by people who don’t really understand what problem they’re trying to solve.

      If you actually understand what you’re trying to do, you code doesn’t do a bunch of stuff it doesn’t need to do, and you don’t have to spend a bunch of time optimizing. Good design that focuses on locality of reference, cohesion, and decoupling tends to be fast and consume the least memory without any special optimization effort..

      Code that’s easy to understand is code that’s easy to optimize. Code that provides the wrong answer, no matter how quickly it does so, is infinitely slow.

  1. Alex Vanden Abeele

    I think that you, together with some people in the comments, blame the programmers too much. I think that most programmers want to get the most out of their code who feel it’s part of the fun of writing code that it is optimal – memory wise, performance wise, algorithm wise.
    But the programmer is not asked to do that, he just needs to finish agile feature x in sprint y, after which he must continue on the next feature. I think there are many programmers who wish they could spent some more time on their code, but it’s just not possible.

    You mention Data Oriented Design (data locality) as a forgotten optimization. I disagree that this is an optimization, by its name it is a design. Design has to happen at the start of the software development. You cannot optimize a program by making it data oriented all of a sudden, you have to redesign it. Rethink it, Go back to square one.

  2. gnz

    It could have been so easy… To stop people misquoting Knuth, you just had to copy the *complete* quote and say “hey, don’t you forget that last sentence!”.

    “Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.”

    Knuth’s words are not “unfortunate” at all, he is exactly right about premature optimization. The problem is that people forgot that critical 3%. Your problem, on the other hand, seems to be that you still don’t really get what Knuth meant.

  3. Vladimir

    Programmer never must code for a sake of code. We live in a real world and if the product generates revenue X before and the same revenue X after optimisation – we’ve just wasted a lot of money for nothing while we might have come up with features that could have increased the said revenue (the revenue which pays salaries, you know). On the other hand there’s a whole lot of applications that literally bring the more money the faster and more reliable they are. It’s a sole matter of requirements which stem from the market your selling to.

  4. I have been coding and managing software teams for 30 years. I have very frequently seen developers who quickly focus on one aspect of code, like performance, or security without understanding the whole picture of the code they are writing. I could name scores of developers, widely regarded as excellent who fail to grasp the problem they are solving in its entirety. An incredibly secure, or performant or elegant module amongst a sea of mush is nearly pointless. A module that takes months to perfect has no value if its need is in days.

    A question I looked at on Stack Overflow yesterday asked why a well optimized XML parsing library performed more slowly that the simple version that is “known to be slow”. The question had profiler results pointing to a 10% slower result in the library call. But it was all wrapped in Ruby 1.8.7 within Rails 2.3 (both verging on a decade old) on unspecified hardware or fixtures. I want to say something unkind while shaking my fist, as it was plain that there were easily hundreds of probable issues of which this misguided attempt at “throwing optimization at it” simply failed to see. This is my counterpoint to yours.

    Code first, optimize later … or premature optimization are just ways of encapsulating ideas of how to approach the complete software engineering problem better, or at least that’s how I see them. My current favorite is “Make it work, make it beautiful, make it fast”. All fail if they are misunderstood. I see these as equivalent to guidelines for writing prose, where an outline, then drafts, precede the finished product.

    I think we would agree that pushing an outline or draft to production is a bad practice. And also: this is very often how people (mis)understand Agile and MVP strategies. It is absolutely stunning to me how quickly and blithely so-called engineers are willing to put complete crap out on the flawed premise that they’ll fix it later. Even more frightening is the code they don’t even know is crap. I am guessing we agree on these points.

    So in teaching people to deliver high quality software, I often ask them to step away from the “details” like performance and security and such and make sure they can answer questions such as “why are you writing this?” and “what should it do?”. Often I find people, very smart, talented, experienced (on paper) who don’t know these answers, and instead have lazily jumped to the fun part, the “solving the puzzle” part. Of all the code I have seen, by far the most secure, the fastest, and the most maintainable is the code not needed. Thinking about how to solve a problem is hard; just jumping in is easy … And lazy. Not finishing is just unprofessional.

    So this is simply to say that there are valid reasons why these simplistic phrases have stuck. And yes, they can indeed seem misguided. But it has sadly been my experience that very few engineers are brilliant, or even competent at the larger engineering problem of delivering a whole thing. Sometimes to get quality software, we need to teach engineers on the job. If we cannot get past “make it work” or “make it beautiful” then we should not deploy … But these steps can provide a worthy template for thinking about how to deliver great software.


  5. The quality way to address this is to define the speed requirements necessary as part of the spec and meet them. Simple. Straight-forward.And limits the optimisations necessary.

    Without speed being in the spec you are just as likely to buy more expensive hardware than necessary or waste time on unnecessary optimisations, as you are to not deliver a fast enough solution.

    Unbounded optimisation is also a root of some evil! (And leaves practitioners with a false sense of superiority).

  6. Cookiecat

    The factors you juxtapose with performance (Rapid development, Clarity and readability, Reusability, Risk of regression, Extensibility, Elegance, Object-Oriented Purity), aka “internal quality” are arguably all in service of maintaining low cost of adding/changing functionality. Given infinite resources, everyone would pick a system that has these qualities AND performance.

    Let’s consider: is there a tradeoff between performance and maintainability/readability? If the answer is “no, it just takes more time/resources/expertise to get both”, then there is an implicit tradeoff with development time/cost. If the answer is “yes, there is a tradeoff between maintainability and performance”, then which system would we rather have:

    A) more optimized but less maintainable


    B) less optimized but more maintainable

    With B, there is a choice: do we optimize the perf or do we keep adding more features? With A, adding more features has an unavoidable, and less predictable cost.

    Optimization patterns like object pooling, flyweights, and custom memory management macros have a profound impact on maintainability and can mutate the codebase into a state where adding more developers is no longer an option.

    • Cookiecat

      Forgot to include one other comment:

      re: “We need to stop wasting our customers’ resources.”

      By resources, you mean cycles, machines, bandwidth, electricity. But here are a few other limited resources customers have: time spent waiting for delivery of the product and money spent funding it.

      It is for us software craftsmen to help the customer discover what their priorities are and deliver the best possible product within those constraints.

      • > But here are a few other limited resources customers have: time spent waiting for delivery of the product and money spent funding it.

        These are only initial costs that, as time goes, constitute smaller and smaller portion of TCO, contrary to variable costs that accrue over time. Maintenance, fixing bugs, waiting longer for an unresponsive, non optimized application to perform a required action, are costs as well. They are divided into smaller chunks and perhaps are harder to notice or to care about when all attention is directed at initial resources spent on first delivery, but costs nonetheless.

  7. alex

    “I type 529 characters per minute”

    This seemed like a massive number, until I realized that typing is usually measured in words per minute not char per minute.

    • If you do the math, the 20ns times 530 makes 0.02ms.

      That’s 0.002% of a second. He proposes it should be optimized, so the computer could spend 0.02ms doing something else, more useful.

      • I probably shouldn’t respond to what might just be nerd-sniping, but… He quoted 50ns per alloc, times 529 keystrokes per minute, *times 25000 allocs per keystroke*. My arithmetic makes that about 0.66 seconds (per minute of typing).

  8. Jean-Victor Côté

    It is the same as with writing. Why follow orthographic and syntaxical rules when writing, the meaning is conveyed anyway, one would say? But sloppy writing leads to sloppy thinking and conveyed meaning acquires a life of its own.

  9. Jayson Vantuyl

    I’m pretty middle-of-the-road on this one. The thing that Knuth meant (and was dead-on about) was that premature optimization is bad because you’re make design decisions (and expending time) based on something you have no information about.

    When a sloppy programmer abuses the GC, for example, there’s no question that it’s a huge, app-wide performance hit. Being sparing with objects is not “premature optimization”, it’s reasonably frugal programming. There’s no premature optimization here, there’s just “making a clear and well-reasoned solution.”

    Here’s where things fall down, though. As a senior developer, you must make that argument. Have that conversation. Make it happen. I think it’s fair to say that we generally don’t work hard enough to have rigorous visibility into performance. This is a shame, because there are really good tools to do precisely that.

    These days, many people test and many even run code coverage, but very few people profile–especially as part of a CI build. In having the above conversation, having these tools in place provides critical backup for your point. (This is one of the things I love about Go, by the way. They’ve unified testing and benchmarking.)

    That said, I think the semi-obscured point above is that these people aren’t just choosing to give up performance–it’s that it’s given up without thought. For my part, I routinely file stories in our icebox when we decide that we’re going to take a hit on performance. That said, I also continually argue to take the performance hit; because quality, speed, and limited developer resources compete. The key here is to make it a conscious decision.

    I actually welcome the “premature optimization is the root of all evil” retort, because it’s secretly an opportunity draw the line between what qualifies as optimization and what qualifies as “just good programming.” There is no better opportunity to improve your team’s standards than that question–but you have to work to control the narrative at this point!

    Development is increasingly a collaborative venture. The trick (and its entirely a rhetorical exercise) is to prevent that from ending the discussion. Here, the failure is not so often technical but rather is a failure of communication.

    Managers often initially despise me because I’m all over the “we don’t *really* know this” angle. I suck false-certainty out of meetings like a six-year-old with a chocolate shake. A manager’s job being “to reduce and mitigate risk” is at direct odds with a development team’s job to make informed decisions. This creates this weird culture where all decision points are True or False; because NULL scares the bejesus out of mediocre (i.e. most common) management.

    So, as much as “these duct-tape programmers are sloppy” is a clear and present danger; “this perfectionist can’t communicate” is *worse* and equally endemic. When you hear this Knuthy retort, work to change the process. Identify and highlight uncertainty. Force people to accept it and make them defend what they’re buying with it.

    As it happens, you’ll find that being a lone craftsman is wildly different than be a group of artisans. When you can’t take your own risks and reap your own rewards, you have to change the group culture to embrace the same thing. If you can’t make this change where you are, you might want to ask yourself if you shouldn’t work somewhere else–because it’s a shame to let bad management waste the effort of a good craftsman.

  10. Apo

    Actually I think this is a misunderstanding of the (mis)-quote. Knuth’s not making any rules, and the key word “premature” implies don’t optimize before it’s appropriate. Much of Knuth’s work is indeed about optimization, and he is just noting that one should think about when to spend time on it. Also note the use of hyperbole as a device to both dramatize the point and make it slightly tongue in cheek.

  11. steve

    I agree with your premise here, but I also think mindsets like yours and mine are a dying breed. I’ve read elsewhere on HN about the impending death of the software craftsman/artisan, and I think that sentiment is accurate.

    I’ve always held the opinion that people who complain about premature optimization are for the most part sloppy programmers who write sloppy code. “Why would you cast a variable when the compiler does it for you?” “A foreach loop is easier to write than a for loop” “0 evaluates to false, so I’ll just use that in my comparison statements”. Just sloppy.

    I think as we continue to deal in larger abstractions, shifting further away from the bits and bytes that are the atoms and molecules of our work, we tend to care less about slippage and spillage. We treat the GC like the cleaning lady picking up after a frathouse party. We pay little thought to it, and even less respect to it.

    We are approaching a point where we will no longer be software architects and programmers, but instead software configurers. This is already abundant in the “enterprise”, where we essentially write glue code for prepackaged libraries. Granted, this only makes sense in an environment where costs must be low and cycles short, so I am not denying the practicality of it…it’s just that more and more people think that’s what programming actually is.

    • Rob K

      My experience has been the exact opposite. The crappiest programmers I’ve worked with were the ones who were always talking about “optimizing” (“we’ve gotta make it fast!”) and wouldn’t know who Knuth was if he bit them. They write sloppy, unmaintainable crap which is full of micro-optimizations but uniformly slow and incomprehensible. In my couple of decades of experience, craftsmen constitute maybe 20% of coders. Most of the rest have been techie code grinders.

      To my mind, correctness must be stressed above all else. An incorrect answer, no matter how quickly arrived at, is still wrong.

  12. Robin

    I second your sentiments. My perspective is that performance ALWAYS MATTERS, even at small scale.

    When someone plats the tiresome old “development time matters more” card in this argument, I shudder. Slow performance is a problem on multiple leverls, because software performance equals investment efficiency, equals energy efficiency, equals environment etc. Throwing more hardware at slow software is a brute force measure, a solution akin to treating the symptom rather than the cause.

    It’s a sad and baffling reality that there just doesn’t seem to be any way to get into people’s heads that it’s an economically and environmentally wiser choice to have fast software from some extra development time, than to throw faster and faster servers at it to make it perform nominally.

  13. Instructions for how to optimize:

    * Write a benchmark or profile your code
    * Find the largest inefficiency in your code
    * Improve the code based on what you found

    Repeat until you’re satisfied or when there’s only small inefficiencies, gaining you maybe 10% in total.

    If something is missing from the above steps in the recipe, you’re not optimizing the code. Also keep in mind it’s about the total. Say you manage to improve the performance 5% in sequence 5 times, it totals 25% improvement.

    Now consider how effiencies compose: Say you’ve got hundred independent tasks. Each task completes in 10 seconds, but could complete in 9. You would save 1m 15 seconds seconds to optimize. Total the tasks would then take only 15 minutes to complete.

    So when Knuth said: ” We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.”

    …I think what he said was correct, even if detached from the context. It’s technically correct statement.

    Now misinterpretations of that quote are an entirely another thing. But the quote’s good.

    • Sebastian Sylvan

      The problem is that in real apps you often see most of the time being spent in thousnands of tiny inefficiencies. Who wants to go fix 1000 tiny performance issues after-the-fact? Nobody, and that’s why your word processor takes several seconds to start.

      Meanwhile, if you just used common sense and good practices *up front* you could avoid creating those tiny inefficiencies in the first place, without really costing you any extra effort.

      • If the 1000 performance issues stack. That means they affect the same point in the program. The performance increase becomes: a * b * c * d * e

        If they are independent, they are in separate parts of the program. The performance increase averages: sum(L) / count(L)

        In modern computing, there’s also the cache to be accounted too. Some things that appear to be independent may be dependent after all.

        The important thing Knuth, and about everybody else points out. It’s necessary to measure performance benefits. You won’t exactly know your program’s performance up-front.

        Also, this doesn’t only apply to optimizing. You should observe the whole, see the purpose of your code and work towards the purpose getting filled. Everything works in a context and if you’re missing that context, it possibly won’t work.

  14. lmm

    Programmer time is a constrained resource, and one that has genuine value. Look at how much companies are paying to hire programmers – or, more viscerally, look at all the ways our lives are better than ten years ago thanks to programming. Professional ethics demands that we conserve that resource just as much as the ones that you mention – and spending an expensive resource to conserve a cheap one is bad economics and bad charity. It’s like knitting a sweater for a penguin: it makes you feel good, but if you really wanted to save birds you’d send money instead.

    • Sebastian Sylvan

      Firstly, most of these pointless inefficiencies do not actually save a lot of programmer time, they’re just dumb choices made for dumb reasons.

      Secondly, software often runs more than once. The savings you get from marginal effort is multiplied over all the users of the app. If you can make your customers 1% more happy by spending 5% more time on the code, then that’s often a big win overall because there are a lot more customers than programmers in many cases.

      Thirdly, programmers use the app too. If you can improve the performance of the app then you’ve improved the iteration time during development, which *saves* programmer time.

    • Erik

      That sort of mentality is why it takes me 40 seconds to load our economy solution to log my hours, and 10 seconds to load up each project on which I’ve worked that day, with a final 20 seconds to save the data…

      But hey, the company who develops it has about 50 employees, afaik, and we only have about 2100 using it every day, so I guess it is better they save on their valuable time than optimising their code properly…

      On to the topic of the blog, for me it hits the problem right on the head!
      “we can optimise the hot spots later”, “but why optimise that, theres a larger bottleneck elsewhere ” until we end up at “why is this do slow?”…
      Even people who care about performance are too often blinded by the idea of optimising later, since premature optimisation is the root of all evil. But when you get to the point where speed really matters there is no obvious area to attack as the software now suffers from the death of a thousand paper cuts..

      Case in point, I worked at a company doing 3D visualisations, writing their own renderer and using it for making videos/interactive solutions for difrerent industries. All modelling was done in 3DS Max, exported with a custom exporter, and then optimised and tweaked with custom scripts.

      The people who had worked on the exporter had only added in features as needed, taking little to no care in optimising neither speed nor size of outputfiles. It got so bad they had to spend days in another dept. to get the files down to a size they could work with.
      There were no obvious hot spots, so nobody wanted spend their precious time optimising it.

      To cut a long story short, after optimising and rewriting most of it, the file sizes dropped from several gigbaytes into a few hundred mbs and reducing the post processing time by about 3-4 days(!!) per scene… But these optimisations/changes were not considered worthwhile when writing it for the first time..


    characters per minute? i dont know anyone that uses that metric. either you are impossibly snooty or you’re british or something.

    – dumb american

Comments are closed.