The 'premature optimization is evil' myth (2010)
joeduffyblog.com
joeduffyblog.com
In the inevitable meme transfer in the telephone game[1] and shortening of memes to smaller soundbites, the "small efficiencies" part is left out.
To me, "small efficiencies" was trying to "optimize" your old C code from...
x = x + 1;
x++;
++x;
Knuth isn't talking about being ignorant or careless with choosing bubble sort O(n^2) vs quicksort O(log(n)). Or not placing an index on a lookup key of a 1 terabyte table (that's a 1-hour full table scan vs millisecond b-tree lookup). Those are not "small efficiencies".
If one leaves out the "small efficiencies" as a conditional, regurgitating the "premature optimization" is a cop out for not thinking.
Commonly phrased in startup world as "It's OK, we're just building an MVP."
Quicksort is O(n log n) average case and O(n^2) worst-case.
Hopefully, it didn't detract from the point that Knuth was talking about premature micro-optimizations and not design/architecture/algorithm optimization. Some inexperienced people are repeating "premature optimization" to try and win internet arguments instead of using it as nuanced advice to avoid wasting time.
is pretty much the antithesis of
>to avoid wasting time.
-> I've found this super useful in projects. This doesn't mean you don't spend time on design or architecture, but it means many engineers have a strong tendency to jump on optimization opportunities too quickly (the more junior the stronger the tendency), AND this causes bad architecture choices that come to bite you hard later on. Keeping it simple and un-optimized is often better than early optimizing, not just because you save time and it's not worth it (hardware is cheap), but also because you keep your architecture elegant and the real bottlenecks will be different from what you thought they were and will come up later.
It's absolutely valid, and wisdom that's often hard earned.
To me that makes the "myth" part of the title more than a little click-baity, which is unfortunate.
Knuth is right: premature optimization is a bad idea, full stop. That doesn't mean that there aren't performance related activities you should be undertaking at various stages of implementation, that either aren't optimization, or aren't premature, or both.
Saying "this bad thing is bad" is a bit of a tautology, but there is some meaning to be gleaned from the statement.
Design activities allow you to think about how a system may and should behave. Optimization activities involve analysis of how a system actually behaves, and making changes typically involving performance trade offs, then analyzing those changes.
These activities can (typically should) be iterative in nature over a complicated projects development, and they do feed into each other somewhat.
What is true as a counterpoint to Knuth's maxim, is that if you do not think about the implications of your design early enough, you can easily end up painting yourself into a performance corner it may be difficult or impossible to optimize your way out of. If you've picked a fundamentally inappropriate data structure or algorithm, you may be in trouble well before you realize it. This is also why software developers would often benefit from more targeted design prototypes, earlier on.
And yes, for some of this there is no easy replacement for experience.
Another thing to think about: Optimization almost always costs you something, at the very least time, but often code maintainability, portability, generality etc. It is usually a trade-off (but not always).
Often good design work will improve your system in many respects at once.
There is of course some scale dependence to the use of these terms; the 'design' is of a larger system than the individual algorithms that compose it and can be abstracted and optimized.
In cases where the scale is the same, i.e. variations of the design itself will have substantial impact on its performance characteristics, then optimization and design can't be readily distinguished and Knuth's aphorism is less clearly relevant.
brilliant--a few words that belongs somewhere more conspicuous.
'make it work' then 'make it fast' makes sense of course, but who wants to optimize code in quadratic time that could have been originally written w/ linear time complexity.
> Knuth is right: premature optimization is a bad idea, full stop.
You should do X always, unless it does not make sense.
How do you know the difference ? With enough experience or enough ignorance. Knowing when you are in one category or another for a specific topic is the tricky bit.
Once you have the right algorithms, data structures, and system architecture in place and working, it's going to be fast enough and you can choose to spend time optimizing only where absolutely necessary. Even then, you should default to getting order of magnitude better performance via a better design rather than tweaking inefficiencies.
"Mostly this quip is used defend sloppy decision-making, or to justify the indefinite deferral of decision-making."
I have never heard it used in this context. Sometimes I've heard it used as a gentle way to suggest to someone that they are going off in the weeds and need to refocus on what they should be focused on, but usually I've just heard it used as it was originally intended by Knuth.
Optimization often involves making code less clear, more brittle, or with a more pasta-like organization. Frequently optimization requires writing code that if looked at out of context, doesn't make sense or might even look wrong.
When these sorts of optimizations need to be made, they should be made only as needed (and documented). It shouldn't be done without knowing whether or not a particular code path is even a bottleneck in the first place, and it shouldn't be done if speeding up that particular bottleneck wouldn't make the software better in any tangible way. That's all the phrase means.
It's not that all issues are preventable. It's that you can prevent a lot of them with just a little extra work up front.
It's a misuse of Knuth's original point, which has much more to do with how brittle and incomprehensible "optimized" code can become.
The programming language affects a lot the criterion. Some are known to be "correct" (like Haskell), others "fast" (like C) ...
Given an infinite amount of time, I suppose the three can be reached in any language.
Most of the time, the answer is "Too much, not worth it". Some of the time the answer is "Let's do it". Knowing which situation you are in is key.
Ideally, I should write code for readability and maintainability and let the compiler and runtime worry about optimizations.
The only good reason I can think of is that you're somehow stuck with 300ms+ delay anyway, so you provide an animation so that the users don't think "WTF? I just clicked on it and why is nothing happening?" But if you can shave off 0.2 seconds then you can probably get rid of the animation altogether!
I think they're terrible.
You'd also be surprised by how many people will completely misunderstand your UI and get confused by things popping around magically, if the transitions are too fast or inexistent. You have to build a UI/UX that your typical user will enjoy and be able to use, not a UI/UX that your nerdy friends are going to love. (unless they're your target users)
From an overall social welfare pesrpective, there is something to be said for going above and beyond the customer's minimum standard. Indeed, most of the work that goes on at big companies is of this type (it's no coincidence that the original author works on the compiler team at Microsoft). Just understand the context in which you work - if the company is going to go under with its current customer base, it's irresponsible to focus on things that are not going to get more customers - and that it can be hard to measure the effectiveness of work that doesn't directly lead to new sales.
So do you want to say that MSFT should invest less energy in speeding up the code they produce, because it won't get them more customers or more money?
As a user, of course I want Microsoft to invest more in speeding up their products. I also want them to be easier to use, and have all the features that I want, and cost less, and release more frequently.
As an engineer, yes, I do want them to invest more in speeding up products. Performance tuning is fun, it's an extra skill that can go on my resume, and it helps me take pride in my work.
As a shareholder, hell no are you going to indulge those prima donna engineers and their perfectionist tendencies. I invested in this company to get a return on my investment, and that means more revenue. It's clear that shaving CPU cycles isn't going to get more customers; Windows has been dog-slow compared to competitors ever since the Amiga came out, and it hasn't hurt us so far. That effort would be better invested in getting into new lines of business and building more solutions to capture the enterprise market.
As an executive - it's a complicated question. I want our products to be faster, but it's also clear that our customers want them to be easier to use, and have a lot more features, and cost less, and release more frequently. All of those are in conflict with writing performant code with a fixed number of highly-trained engineers. And if I hire more engineers, the code often gets slower, as global optimization opportunities get lost in the communication gaps between workers. OTOH, performance often has intangible benefits in brand loyalty, in increased usage, in word-of-mouth, and in PR. I'd love to be able to quantify these benefits and trade them off against each other, but the point of intangibles is that they are intangible. I'm responsible to shareholders, however, and my gut feeling is that increased performance will not be the deciding factor for most customers.
(As just plain old me, the question is completely academic: I am neither a user, employee, executive, or shareholder of Microsoft, so I don't really care what they do.)
And tangentially, I still wonder why MSFT thinks that forcing Windows 10 down the throat of the existing users can be considered something that will "get them more customers" if that should be the ultimate goal of the company.
If you want performance, you have to design for performance, not just build the first thing that comes to mind and try to optimize it later.
IMHO, this is exactly the kind of thing Donald Knuth was approving of.
Given how cheap CPU cycles are, how expensive developers are and that faster code often means more 'unsafe' code, 97% of the time it's more economic to just have the resource-greedy software.
Plus, I've seen more than my fair share of premature optimizations that ended up actually causing performance problems and stupid bugs.
I agree. I run sloccount in my build system. It gives a cost for manpower. For example:
Total Physical (SLOC) = 6,944
Development (Person-Months) = 18.36
Schedule Estimate (Months) = 7.55
Estimated Average Number of Developers = 2.43
Estimated Cost to Develop = $ 206,696
http://vmorgulys.github.io/stackcity/sloccount.html
We should count the energy spent by inefficient programs (multiply the number of devices). It could balance that equation as the Moore's Law is ending.
I guess Debian (or another distro) if more energy-efficient than Windows (or Android).
Edit: beautified sloccount output
Unfortunately looking further than the end of the next sprint is disallowed in a lot of people's minds. It's pretty sad that a lot of software "engineers" actively avoid any kind of engineering.
Premature architecture is a code smell. Putting in scaffolding for later is a code smell.
However, I admire your ability to write code without any forethought now that can be used perfectly in whatever form it will be needed later.
I dispute that that is true. They may have a vague idea of a goal, but that's not applicable at the code level in general.
> Based on that knowledge you can make reasonable decisions and trade-offs now.
We aren't talking about making decisions, we're talking about stubbing out code for future needs, an entirely different thing. Nothing wrong with making reasonable decisions, but there is something wrong with stubbing out code you don't need because you think you'll need it later; if you need it later, add it later. It'll cost the same as adding it now. If you think it's going to cost more later, then revisit your architecture because it shouldn't. The implicit argument for adding it now is that's it's cheaper to add now than later, I'm saying that's nearly always a bunk argument.
> However, I admire your ability to write code without any forethought now that can be used perfectly in whatever form it will be needed later.
That's not what I said; the cost of change should be the same later as now. That doesn't mean you won't have to make a change, it just means it shouldn't be harder to add later than to add now.
I was talking about decisions and not writing code and was pretty clear about that.
> That could mean a simple API wrapper that can later on be optimized
That's code. That's what I'm responding to, you insulted those who believe in not writing code before it's necessary, called them sad, and now you want to deny the very thing being replied to? Really? Forget it, you don't know how to discuss something.
That's patently false in any code I've seen; and saying "well make it so, can't be so hard" is just proof by handwaving.
It's new code, so you can absolutely write it without extra scaffolding for "shit you might need later". If you don't need it now, you don't need it yet.
That's the problem.
> Optimization often involves making code less clear, more
> brittle, or with a more pasta-like organization.
> Frequently optimization requires writing code that if
> looked at out of context, doesn't make sense or might
> even look wrong.
This does mean you can't skimp on good design, making your project a collection of modular, replaceable components.
But that doesn't mean it's a good way to write software. Accept that most of what devs do is fairly mundane, and focus your mental effort where it's actually needed and you'll be a better developer than anyone who obsesses over the performance/elegance/extensibility of every line they write. Obviously it's a spectrum, and it takes balance, but I know which side I'm currently on!
> I have wasted countless hours on needlessly efficient
> implementations of the wrong interface, or, on the other
> end of the spectrum, coming up with the perfect interface
> for code that will never be used again.
I know I've certainly done enough optimizations that left the code clearer and shorter (despite often being more verbose with naming), while being more performant due to shedding whatever messy, tortured approach was in use before. Enough small gains like this have come out of code where I was the original author that it isn't a case of conceit.
Clear and simple code can frequently beat clever code, regardless of which metric you choose to apply from the "performance or understandability" bag.
Here's a comment where someone says that performance doesn't matter at all if you only have a certain number of users and then they backtrack and qualify their statements: https://news.ycombinator.com/item?id=11245700
I have the opposite impression - that many devs are lazy and don't think about optimisation at all. They write slow code by default and hide behind a misquoted Knuth.
Your definition is off by the way, writing fast code and doing optimisation doesn't necessarily mean that the code will be less understandable or become brittle. e.g: using range va xrange in Python 2.x when iterating over large ranges - that's a difference of literally one letter. There are of course other examples.
OP said
Optimization often involves making code less clear, more brittle
Seems you're arguing against a straw man here.
* OP is arguing that optimisation is usually problematic from multiple perspectives. Here's the full quote:
Optimization often involves making code less clear, more brittle, or with a more pasta-like organization. Frequently optimization requires writing code that if looked at out of context, doesn't make sense or might even look wrong.
* I am arguing that these assumptions cannot be made so easily.
Yes, they qualified the statements with "often" and "frequently", but the tone is clearly negative. It shouldn't be, and we shouldn't shun writing fast code out of the belief that it's at odds with readability or robustness.
Which literally makes no noticeable difference 97% of the time.
I wouldn't necessarily complain if you did that to my code as part of a broader refactor but if the range is small you're not doing anybody any favors.
The problem is that when people hear that quote, without knowing it's original intended usage, they are able to use it as a "just get it done" excuse. This often happens when people are too shielded from what's going on in the database via an ORM layer like ActiveRecord for example.
You don't need premature optimization...but you do need competent optimization. If you can see a blatant red flag that you're going to avoid by taking a little more time to do something a different way...do that.
Something is off about that.
These guys were militant "all logic in the objects" types so when they had to create a dashboard page, instead of just doing a scope with a couple of joins and the proper criteria; they went off of the base object, got the first set of associations, checked to see if it met the criteria by looping through the results and calling the object methods (which made associated calls to evaluate their comparisons under the hood) before finally converting the entire result set of about 20,000 objects into an array so that it could be sorted and the trimmed to exact number of records that were supposed to be displayed on that particular page.
It was brutal. You would have thought it would require real, serious, effort to pull off that level of scary.
I don't have the code to offer, but I can cite a couple of blog posts that I wrote about it a while back. It was so bad that I not only start blogging more because of it but I also taught a class to try to teach people both Rails AND PostgreSQL so they couldn't get into a situation of learning one without the other.
Here's the posts...
The Drawback to Web Frameworks (2013) - http://www.brightball.com/ruby/the-drawback-to-web-framework...
"In order to look up what the status was on a particular object related to a user, they used some beautiful looking Rails code to find, filter, and combine results (and THEN paginate). The problem is that after Rails goes one level deep from a single record it starts performing single queries for each record in each relationship. That meant, for example, that in order to retrieve the most recent objects for a user who had over 18,000 in his account history that upwards of 50,000 queries were executed. The results of those 50,000 queries were then loaded into the web server's RAM (and SWAP), processed/sorted/filtered, and THEN paginated just to show the first 100 results. It was appalling and that is only one example."
And here's the class that I taught to try to stop it from happening ever again. :-)
http://www.brightball.com/classes/ruby-on-rails-and-postgres...
I don't agree with that. It may be true for very low level micro-optimizations, but isn't usually the case for higher level optimizations that give the best performance improvements.
A lot of times code can be sped up significantly just by using a different data structure or caching a value that's already computed somewhere else. For example, I've seen production C++ where the code was using a std::vector to keep a list of items in sorted order and remove duplicates. It was trivially converted to a std::set and saved several seconds of run time.
I tend to think of it more as not painting myself into a corner than necessarily getting it perfect the first time. It's amazing what some thought, maybe a day in the profiler per couple of months of dev work to catch out the big mistakes (and as near as I can see, nobody ever gets quite good enough to be able to never make such mistakes), and some basic double-checking (like "are any of my queries are doing table scans?") can do for performance, long before you pull out the "big guns".
Sorry, I did not mean to delegitimize those points. I understand where they are coming from.
"are any of my queries are doing table scans?"
It makes me grind my teeth when developers apply brute force thinking like this. There are many times when full tables scans are fine - e.g. used on a small table, or when a query returns more than a few percent of the rows in a table.
imo, blindly hunting out full table scans is a textbook case of premature optimization.
Besides, this may "grind your teeth" but I see the opposite at least a full order of magnitude more often, if not two. I'm far more likely to get someone asking me "What's EXPLAIN?" (when working with MySQL) than to see someone going nuts making sure they have 0 table scans.
Yeah, that's exactly right. I was reading the article with that lens, and found some of its examples less than compelling. It may not matter if Linq is doing a bunch of allocations; you could always replace it with the in-place loop later. Starting with Linq doesn't cost any potential energy.
I had a couple more nuanced reactions to the OP.
a) While this is an argument that needs to be made more often, and one that I've made before, characterizing careless optimization as just lack of thoughtfulness is underestimating the problem. The real problem when I end up writing carelessly slow code is that I had no conception of the internal details of some library or service. The best programmers know they have to gradually break down every abstraction in their mind, and gain the ability to think about its internals when the need arises. It took me a long time to realize that my mindset when using a library should be to gradually understand how it works. Heck, I stared at the sql statements emitted in Rails logs for years before I realized they were telling me something useful. It's not about not being thoughtful, it's about being on a path of learning long before you need it. And we need to be spreading this word far and wide.
b) The standard of "all great software programmers I know are proactive in writing clear, clean, and smart code. They pour love into the code they write." is incredibly rare. That isn't going to change. So as long as we place the onus on considering alternatives up front, we're always going to be disappointed. Particularly when new programmers come in late in a project's life cycle and weren't around since it started, they may not actually be aware of all the different situations it's invoked in, and how bad worst-case might be. They'll also be less intrinsically motivated because they have less of a sense of ownership for the codebase. Things get even worse in projects that started out as prototypes, because of course there it makes sense to just go with the first idea that pops into your head.
I think we should make it easy for people to contribute by making it easier to perform radical rewrites of parts of codebases. That way there's less pressure on perfectly checking all possible alternatives up front.
The difficulty of a rewrite has less to do with the raw effort of the rewrite and more with the prospect of causing regressions, and the stress emanating from that prospect. I've been exploring making codebases more rewrite-friendly, using more comprehensive white-box tests: https://news.ycombinator.com/item?id=11052322.
I think the title is a bit misleading because it's a good heuristic and you agree with that too.
1. novice - follows rules because he is told to
2. master - follows rules because he understands them
3. guru - transcends the rules because he understands that rules are over-simplifications of reality
In case you're interested in a graphical representation [1] of some common latency costs, someone at UC Berkeley put together an interactive chart with the original Numbers Every Programmer Should Know from Jeff Dean's (Google) large scale systems presentation.
[1] http://www.eecs.berkeley.edu/~rcs/research/interactive_laten...
For instance, you often figure out you don't need a piece of code only after you've written and tested it, or after your thought process about the design has evolved. When you delete that code, it doesn't help anyone that a couple of hours ago you've invested five minutes in picking the "right" data structure for the implementation. The right data structure for unstable code is the one which lets you work with it and takes up the least of your time. As your code becomes more stable, it could then make sense to invest time in picking and coding a better data structure; it's less efficient to do so prematurely.
And that is: amount of time that will ever be spent in it across all deployments and execution instances, versus how long it takes to develop, taking into the cost of that CPU time and development time.
You could spend, say, $100 of development time such that the total CPU time saved over the entire installed base of the code over its lifetime is worth $5.
Secondly, even if the saving is greater than $100, that means nothing if it's not recouped! That is to say, suppose you spend $100 to optimize something, and the entire user base saves $200 worth of CPU time over the next 25 years, when the last installation of the program is shelved. Only, oops, the users never paid a single penny more for the improvement. Moreover, suppose the improvement was only marginal and in some relatively obscure function, so that it didn't help to sell more of the program to more users. So in the end, you're just out $100.
> Mostly this quip is used defend sloppy decision-making, or to justify the indefinite deferral of decision-making.
Here is the thing. An program optimized for performance is "bad" because it's hard to change its organization later (for instance when it needs to be optimized). It's harder to debug, too.
We consciously avoid optimizing code in order to have the code in a state that is easier to work with.
But we must ensure that we actually achieve this. In effect, we should be actively optimizing for good program organization, rather than just focusing on a negative: not optimizing for performance.
Or optimizing something other than performance, and good program organization.
A really bad approach is, for example, "optimizing for the minimum amount of time I ever have to spend learning effective use of my programming language, libraries, and existing frameworks in my project".
You get code that isn't performance optimized, avoiding the "root of all evil", but it's garbage in other ways.
He starts the article by judging laziness - after spending a lot of time on stuff that ends up being irrelevant in retrospective I wish I was more lazy about this stuff.
Isn't that exactly what the phrase means? Understanding where it is important and where it isn't? At least that is what I always thought.
Knowing the difference is key, and this is why senior engineers should be in charge of making architectural and design choices up front, and on an ongoing basis. Of course, most businesses can't attract such people, as scalability is not common knowledge outside major internet cities :(
Clever architecture will always beat clever coding.
In the early stages premature optimization can engage too much clever coding and architecture.
There's no shortage of time spent building and optimizing a stack that largely introduces overhead to quickly iterate and solve a problem. I guess this perspective also keeps in mind you should likely throw away the first version of whatever you build because it uncovers how the architecture should be, and where, if anywhere the clever coding and optimization should be.
It's not to say optimization isn't worth thinking about. It's not just worth obsessing about at a scale perspective, and experienced developers develop clever architecture approaches and habits that buy their designs breathing room as they may grow.
The fundamental issue here is every piece of software is meant to break at a certain capacity, just like hardware. As the author very eloquently mentioned, understanding what you may come back to revisit and develop often may be one thing, and other areas you may not end up touching again, and may be worth a different type of design thought.
The mentors I have worked with have balanced the thought of being kind to your future developer self in the present, and that can mean not under, or over-engineering a solution.
Quite often the architectural design needs to be proven and verified before building a lot around it. Spending more time on the schema and architecture to ensure this is where I've found massive gains in baking in optimization to the bread with little development overhead other than planning and thinking a bit more.
Quite often if I want to dive in to build a throw away prototype, I'll stop myself and think of a plan. When I'm hesitant to build without a plan, I often let myself prototype lightly to aid development of a plan.
Developing for the simplest common denominator in the early stages to allow as many people to participate in the learning and direction of the solution is extremely critical as well. When problems reach the 10-100 million row level there will be a lot more to figure out than just optimizing it.
Quite often technologies get caught up in optimizing technical design and code, and not users, problems or solving them. Maybe users need to be the focus for Technical developers, and technical understanding is something to focus on for non-technical developers who trivialize technical matters.
Personally I think "talking down" advice is harmful and goes very much against the pro-learning pro-self-education mindset of our industry. People either ignore it, in which case it accomplishes nothing, or they obey it and it stops people from learning or trying new things. It's also subject to a lot of misinterpretation. The "premature optimization" quote is often misinterpreted in practice to mean "never optimize or think about performance at all."
A better version of the premature optimization quote is:
"Don't sacrifice correctness, capability, good design, versatility, or maintainability to optimization until you already have something that works and you know what you need to optimize."
Another nuance on optimization is: "optimize through better algorithms before you micro-optimize." Micro-optimization means tweaking out a for() loop or implementing something with SSE, while picking a better algorithm means picking something with O(N) over something with O(N^2). Picking a better algorithm is often something you do "prematurely" during the design phase, while micro-optimization is best left until the end.
A better version of the crypto quote is:
"Don't attempt to implement any kind of production crypto code until you know enough about crypto to know how to break crypto at the level you are implementing, and label any crypto experiments as experimental and don't try to pass them off as production or as trustworthy. Also make sure you are up on the state of the art and can name e.g. the last few major attacks against a major crypto implementation and can describe how they work."
If you can't meet those criteria then no, you should not be implementing production crypto (though you are free to play around). But that advice also tells you what paths you need to go down if you want to learn enough to attempt crypto and how to recognize when you might know enough to attempt crypto. Can you explain exactly how BEAST, CRIME, POODLE, and DROWN work? Can you tell me why crypto must be authenticated and why you should encrypt-then-MAC instead of MAC-then-encrypt? If so, then maybe you're ready to swim in that pool. Otherwise, learn.
"Don't optimize" would be the talking-down version.
"Don't optimize prematurely" is naturally tautological. "It is wrong to do X prematurely" is true regardless of X; if it isn't wrong to do X at this point in time, then doing X now isn't premature. It's closer to the pop-culture version of the advice, and like any tautological advice can always be wielded against someone. It's worse than "talking down," which can reduce the mental load on a novice, it's actually not-useful at any stage, as it provides no advice on when optimization is premature and when it isn't.
The pithy version of Knuth's quote might be "Don't microoptimize until you can tell the difference between the 97% of code that doesn't need it and the 3% of code that does" which is in line with pretty much the entirety of your comment.
> I am personally used to writing code where 100 CPU cycles matters.
Essentially, if you are running into electricity / resource constraints on, say, an e-commerce website, then unless your design choices were absolutely hideous, then you are having a Very Good Problem.
Many programmers can spend their entire careers on building and maintaining such apps. The infrastructure costs are outclassed by their salary by several orders of magnitude. A decent website costs millions to develop in total and hundreds monthly to host. It can bring in several million in revenue every year.
All this and it's still a sideshow to the main business. A site I maintain does $3 million in business every year, whereas our retail partners do 7.
And renting servers from AWS can end up being more expensive than paying another dev and using dedicated systems.