The Fallacy of Premature Optimization (2009)
ubiquity.acm.org
ubiquity.acm.org
In my experience most engineers take a situational approach. Sometimes it is worth it to optimize early, sometimes it is not. Some things are worth optimizing, some not. Also some things are worth optimizing to certain level.
These types of articles and claims conjure up a debate because everyone is imagining a different scenario in their heads. It is entirely plausible that each claim could be the best solution in a different scenario.
Do these articles assume that engineers are incapable of thinking flexibly and need to follow some absolute truths that have to be debated? Have I been around too good engineers that I have not noticed this issue?
It's not a problem that's exclusive to coding, you find people talking loudly about absolutes in most fields. People like definitive answers. Makes us feel secure.
Which makes absolutes easy to sell, and especially popular with people who feel out of their depth. It also makes them popular in academics.
You also find flexible, creative thinkers in the same fields. They're just not as loud, or as numerous, in my experience.
When people espouse absolutes, I generally (not absolutely) assume either they're not experts or they think their audience can't handle nuance.
I think this article assumes that there are possibly engineers that don't think flexibly and need to follow some "absolute truths".
> Have I been around too good engineers that I have not noticed this issue?
Probably. I mean, I would love to be between your colleagues.
In some places, submission to ideas rumored to be proven is valued more than flexible thinking, critical thinking at any time, etc. I know that some countries in Asian have a rather high degree of culture like this. It doesn't apply to everyone.
I think this also makes sense. Take a cat. Cats clearly are able to think a lot more complex than they can communicate. They use a set of very basic body cues to communicate, but they are able to process information a lot more complex than these. Why would this not be like this humans too?
I have some very opinionated friends on coding styles, libraries, programming languages, programming "rules", "principles" etc... They're all sort of rubbish. I think it's important to know and study them because they give you different ways to think of engineering. But when it's time to commit code to production does anyone really think about "ah this is not DRY, premature optimization, NIH etc...". I claim no. We always think about the specific situation. Is it good to invent this code. Is it good to optimize this possible future extension. Is it good to repeat this particular code. We all know repeating code is "bad" but we all also know reasonable exceptions.
So yes, all rules are by nature fuzzy. In fact, whenever someone tells me a principle they hold, I immediately start thinking about fuzzy-fying it i.e. thinking of possible niche cases where this principle would reasonably NOT hold.
The code generally had one path but every method was built using dictionaries of possible classes that would implement interfaces so they wouldn’t have any duplicate code.
Sometimes some dev teams go down the wrong path.
Sounds like a horror show built by people who don't understand OOP.
It's not nearly as uncommon as I'd like.
“ The inner-platform effect is the tendency of software architects to create a system so customizable...”
Yup, that was it and I have seen it so many times - architects should think that a flexible system that “can just” handle any possible future requirement. This always ends in a mess of junk that isn’t actually needed by the business.
There are some developers that are like that, they read in a book about some patterns or idea and then in code reviews will jump on you because you did X wrong and not followed his bellowed pattern from the book.
I've also seen the opposite, quite often actually: Cheaping out on hardware that is going to ship maybe 1-10k (very expensive) units, then spending hundreds of thousands on optimizing software to make it not even good, just less painfully slow. The i.MX6 chip with its weak GPU and corresponding wonky drivers is an especially popular way to get user interfaces that can't keep 60 fps.
Regarding mainline Linux support, AFAIK you don't get mainline Linux support anyway with i.MX6 and the gal3d driver. You can only use mainline with etnaviv, which is semi-officially(?) supported by Pengutronix. I've heard others say good things about etnaviv.
Today, things are different. Single-threaded performance isn't going to be improving much in foreseeable future; the effort shifted to improving parallel performance and, more recently, power consumption. So if you write slow code - perhaps by choosing a slow software stack - your code will remain slow.
But TBH in this particular field Moore's law still rules. Sometimes you are forced to upgrade to a better component for the same price because the component you chose five years ago has reached end-of-life.
Yet paying attention about optimization allows you to do more with what you have, or sometimes allows you to use less optimal but more convenient or simpler approaches.
If you are releasing consumer applications either your program works smoothly on the device a consumer has or not, let alone has the ability to buy either financially or fundamentally (as in you don’t find a phone with desktop level performance anywhere, because they don’t simply exist).
Premature optimization, or at least one of its manifestations, is failing to consider the opposite.
Maybe this is just my cynical perception, but I often hear people try to justify situational bad practice by citing outliers unrelated to the situation at hand, particularly with optimization. As you say, they usually imagine a different scenario is at hand. For those situations I quote HL Mencken:
Explanations exist; they have existed for all time; there is always a well-known solution to every human problem—neat, plausible, and wrong.
I interpret the premature optimization dictum to mean:
Really the only time to talk about optimization at the early stage of a project is to set performance objectives or when the project is about optimization. Otherwise people should seek relatively optimal solutions which optimize efficiency at delivery. Optimization starts when they have running code that doesn't meet performance goals. Other optimization is premature, in one sense or another.
I think Knuth (in his famous "... root of all evil" quote) was referring specifically to programming, and to spending time on optimizations prior to functional completion. The mantra, "First make it. Then make it work. Then make it better." [or similar] holds water. But it's pointless to debate in general terms what precisely constitutes a "premature" optimization, vs a merely timely one, or adherence to best practices, given the infinite combinations of circumstance and context relating to software development projects.
We don't have to speculate, the paper is online[1] and he is very explicit about what he meant.
The paper is, in fact, an ode to optimisation and the necessity of optimisation, including, very specifically, micro-optimisation. The "root of all evil..." part is a "yes, but". You actually have to leave out much of the actual sentence in order to strip it of its meaning:
"We should forget about small efficiencies, say about 97% of the time, premature optimization is the root of all evil."
If that wasn't clear, the very next sentence is as follows:
"Yet we should not pass up our opportunities in that critical 3%"
A little later in the paper:
"The conventional wisdom [..] calls for ignoring efficiency in the small; but I believe this is simply an overreaction [..] In established engineering disciplines a 12% improvement, easily obtained, is never considered marginal; and I believe the same viewpoint should prevail in software engineering."
[1] https://www.cs.sjsu.edu/~mak/CS185C/KnuthStructuredProgrammi...
That only works when you do simple things, for harder things the "make it better" part usually requires a complete rewrite if you didn't properly think things through from the beginning.
A better mantra would be "First make it, then make it again, then make the real version".
When this principle has come up for me it's not so much about optimization, but about the cost you're paying to have that optimization: In particular, the cost in terms of code complexity. If you've already got generic code for a self-balancing red-black tree, and you can just plug your new data structure into it, and you're reasonably sure that your thing will get 10 nodes on occasion, then sure, use it, even if you don't know whether you'll ever get much larger than that. But if you don't have that code handy, then don't write a self-balancing red-black tree unless you have benchmarks to show that it will help. And don't use a self-balancing R-B tree if you don't know whether the number of nodes ever goes past 2.
(Or, I mean, unless it's a personal project and you want to practice writing a self-balancing R-B tree; but at that point you're not optimizing, you're practicing / having fun, so the advice isn't applicable.)
If code structure A and code structure B are both about equally comprehensible, and you think code structure A will be more effecient, go ahead and use it. But if structure A is extremely complicated, and will make the understanding and maintenance of the system more difficult and prone to error, then don't use it unless you know it's actually worth the cost.
In a more capable language, that code has already been written and put in a library, and been very thoroughly tested and optimized already, and is faster than you could afford to do just now. Less capable languages can't express such a library in usable form, or call into one.
It is not an accident that Linux and BSD kernels have numerous hand-specialized red-black trees in them, now languishing for the attention that is needed to modernize them to perform reasonably on current hardware.
What he said is, quote, "... we should forget about the small efficiencies, say, about 97% of the time" and "we should not pass up our opportunities in that critical 3%."
What he was talking about in the article[1] is the tendency of programmers to concern themselves with the efficiency of things like the modulo operator, when much larger efficiencies are far more important, such as the design of the algorithm or data structures.
Premature optimization, as when deciding that this small efficiency is important enough to optimize, causes you to forget about the larger efficiencies that cause your program to be slow.
[1] https://web.archive.org/web/20130731202547/http://pplab.snu....
And there is early optimisation, when you know upfront the hill is steep because of the sheer amount of calculation involved in the very nature of the project (gamedev, big data, etc). And this can lead to low level optimizations (e.g McCarmack's fast inverse square root) or architectural measures (distributing code accross computers).
Premature Architecture ?
On HN we would say: first make it, then sell it, then make it work, and finally, make it better :)
I work in web development and we never had to run a profiler even once to find performance issues. "Premature optimization" was in my experience always the discussion about readability. In the JavaScript world there is always this one guy who can do things in 3 lines of code instead of using 5 methods to understand the code in 5 month again.
We called it "Perl coding" vs "standard code".
https://twitter.com/ID_AA_Carmack/status/1210997702152069120
"My formative memory of Python was when the Quake Live team used it for the back end work, and we wound up having serious performance problems with a few million users. My bias is that a lot (not all!) of complex “scalable” systems can be done with a simple, single C++ server."
And so a lot of people seem to feel the need to once again bring back all the discussion in absolutes of optimisation being useless, or the only thing that matters.
I've found the same as John Carmack btw. Taking some component of a customer system, translating it to C++, can make a system that needed 10+ servers suddenly run a lot faster on a single server (meaning higher throughput AND lower latency, because in addition to the raw speed advantage of C++ there's so much you can do in C++ that's not really feasible in, say Python. For example, mmapping files).
But C++ is not exactly the first thing I reach for when something new springs to mind, or I want some data analysis done, or ... (even though C++ is excellent for running production data analysis jobs)
> But C++ is not exactly the first thing I reach for when something new springs to mind, or I want some data analysis done, or ... (even though C++ is excellent for running production data analysis jobs)
Me too. C++ is a pain in the ass (although I only touch that thing in my college day building simple A* AI). I always go to seeking libs in TS (my go-to language) or at least JS before consulting to other languages.
> I've found the same as John Carmack btw. Taking some component of a customer system, translating it to C++, can make a system that needed 10+ servers suddenly run a lot faster on a single server (meaning higher throughput AND lower latency, because in addition to the raw speed advantage of C++ there's so much you can do in C++ that's not really feasible in, say Python. For example, mmapping files)
I think it's just the nature of true compiled language that comes with a very minimum runtime. Multi steps compilation in Java and interpretation in JS or Python always need sacrifice. I have seen great devops engineers pulling hairs over kubernetes configuration issue happening just because a Java spring boot service needs an enormous memory just to initialize some runtime objects.
> And so a lot of people seem to feel the need to once again bring back all the discussion in absolutes of optimisation being useless, or the only thing that matters.
And then, I found Rust, which is a pretty nice language. It bridges that memory safety VS optimisation issue. Although the learning curve is pretty heavy on the syntax and the new paradigm it brought, it's pretty easy for me who is used to code in TypeScript. I'm just surprised at the minimum mention of Rust in that tweet.
.
Say you already have a function that returns the list of children in a node..
.
But you need a function that brings back only the first child if it exists.
.
1. Do you copy the function and return just the first item when you have it (with the associated code around the function) for efficiency sake.
2. Or.. Call the existing function and return the first item if there is at least one element?
.
1 Will be the best answer if you have a million records to load from disk.
2.Will be the best answer if you only have 20-30 records on average.
.
But 2 is the best answer before debugging, check that the code works properly before duplicating it and modifying it.
Answer 3 would be to add a limit parameter, and call the other two functions with it. That way, if limit=0, return all records. if limit=1, return one record maximum.
.
Sometimes the answer is to think differently about the problem altogether.
You bring up a very real point, but the most obvious cases are also most obvious to the people developing the stack below you and have almost certainly gone through the trouble of solving those problems.
This issue rears its head when edge cases are non-obvious and typically manifest through profiling, not through design meetings.
For example "The application must start in under one second".
Then during development you can divide up the budget - 400 milliseconds for loading dependencies, 200 milliseconds for rendering the UI, etc.
Then you can decide if any given optimization is needed or necessary to meet your goals.
Okay... We'll defer some work and show a dummy screen to be "started" in less than 1 second, except now we're loading/drawing the dummy screen, so we're usable in 1.4 seconds, and after a double-start flash, so let's smooth that out with a transition to the interactive UI and we're usable in 2.2 seconds, but we "started" the app in 0.4.
Yay?
It may sound contrived, but I've seen this very response to strict start KPI's before. People end up optimizing the micro-goal (KPI) rather than the macro-goal (better experience).
The flip side problem is, when you have multiple people responsible for parts of the work, people will stop optimizing when they hit their budgeted allotment, rather than working to better the whole. A Dev with a 400ms budget might sleep for 390ms to buy himself three years of squeezing out optimizations...
More likely, he'll stop when he gets to 350ms, even though he could have gotten to 250ms without too much effort.
When it is required then focusing on user value can help: e.g. "<x> seconds to user login being available" rather than "...page loaded".
There's still the question of absolute numbers rather than statistical distributions, but that's another topic.
If the startup screen allows you to, say, launch an "Open File/Project/Folder" dialog or load one of the recently-worked-on items, but won't let you do anything meaningful - then yes, Yay.
It's quite realistic to load that kind of UI in a lot less time than the "meat" of an app is usable. I would take 0.4 seconds for that and 2.2 for the whole app over 1.2 for the whole app - any day of the week.
You also have to specify and measure exactly the correct element. Sometimes the latency budget is split in not clearly-cut parts, and on events or categories of events that are not clearly defined. Saying 'all requests should give a complete result in < 20ms' just isn't realistic and creates a world of hurt. What kind of request? Always, always? In what load conditions? What about error conditions? Fail-over conditions? Hot/cold start?... It's not simple like specifying a clear-cut feature.
Performance budget should often not be all black and white. Especially when trying to push the envelope of what modern PC hardware (with OoO execution, complex memory hierarchies, multicore CPU/GPU rapid-busy-bused hybrid archs) can do. It should probably be a risk law, and at least a critical spec, and thoroughly tested and regression-tested as such.
And here, sometimes premature optimization will be necessary. If someone gives you hard latency requirements, you'll have to say, very quick, 'I'll need a soft/hard real-time OS it won't do extreme high-throughput'. You'll have to bench...
Premature /micro/-optimization is a problem, sure. Make it work, make it right, make it fast.
But global optimization must start at the system design level. How much money do you have? What can you do for $X?
Optimization is premature only if the code is not already fantastically stupid, which may happen too often irl to ignore that.
Couldn’t agree with constant factors though. These are pretty random, n-independent (i.e. scalable) and the net expense of making code less obvious is usually bigger than throwing more/better hardware at it, but ymmw.
We are loading a number of data files and the source of truth is remote. This is O(n) the amount of data.
Two ways to do it: always request the remote data, or cache it, and only ask the remote for changes.
These differ by a constant factor, and it's always a good idea to maintain a local cache when it's possible. Otherwise there's a very good chance that startup time will be dominated by network requests.
But this also falls into “fantastically stupid” category. Just like all web 2.0 e-stores I have to use, which rerequest their dataset every time you touch sort or filter controls. When their largest category is 150kb json and the entire site json is 10x smaller than their ui/ad frameworks.
We are deep into the Post-Moore's Law era, where a new generation gives, now, 120% rather than 200% of the previous generation's performance. Next generation we might get 115% of this, or 110%.
Another consequence is that the improvements we get have become dodgier and less reliable, so that tiny, irrelevant-looking changes in the code may mean a 2x speedup, but more commonly a 2x slowdown. (This is in no way an exaggeration.) The bargain we get from pervasive penetration of more kinds of caches is that sometimes our programs are faster, but we no longer know how fast they should be, or whether another factor of two or ten has been left on the table.
Sorting algorithms are quite mature now, so that a 20% improvement in a relevant case is important, yet a factor of 2 or more may come from the compiler choosing one instruction over another.
Compiler regression bug reports now routinely complain of a 2x performance loss from that instruction choice, but fixing them would result in 2x losses in some other set of programs, instead. We get new unportable compiler intrinsics to patch the failure, that often don't, for obscure reasons.
We did not go from 1MHz 6502s to 4GHz Pentiums without a generous series of doublings. Twelve, in fact.
With feature sizes approaching a single lattice unit cell, its final stage will be reached shortly.
To insist that transistor count is the only point of Moore's Law is to be deliberately obtuse: it was the exactly the extra value provided by the extra transistors and the machinery built of them, and the faster clocks, that would (and did) generate the capital investment needed to develop each succeeding, more expensive, generation.
You are welcome to die on your "Moore's Law is about feature size and nothing else" hill, but you will have sparse company there.
https://en.m.wikipedia.org/wiki/Moore%27s_law
It doesn't matter how forcefully you repeat yourself without backing it up.
Also performance has increased with transistor density with more cores.
I also see that you have confused "much smaller increase", which is observed by everyone, with "no increase", which literally no one has said.
Anybody can read Wikipedia, but evidently not everybody can understand what it says.
2015, Gordon Moore: "I see Moore's law dying here in the next decade or so." <http://spectrum.ieee.org/computing/hardware/gordon-moore-the...
Brian Krzanich, the former CEO of Intel: "Our cadence today is closer to two and a half years than two." <https://blogs.wsj.com/digits/2015/07/16/intel-rechisels-the-...
John L. Hennessy; David A. Patterson (June 4, 2018): "The ending of Dennard Scaling and Moore’s Law also slowed this path; single core performance improved only 3% last year!" <https://iscaconf.org/isca2018/turing_lecture.html>
You have a quote about the time frame increasing which has never been disputed either.
I'm sure you can find links to some tech blogs that have the same misunderstandings as you do, why don't you go hunt those down too?
Dennard scaling was a nice side benefit of transistor shrinks.
Currently, I'm working on a project with a ring buffer (a kind of FIFO buffer). It isn't fast (not lockless) but has a well defined interface so I can swap it for fast one later if I need to.
We shouldn't reinvent a phrase. Premature optimization has always been about programming efficiently, ie. a newbie programmer or even expert "elite" programmer could easily fall into the trap of optimizing prematurely. That means: Spending too much time on very little gain performance-wise, thinking it's important to eke out every little drop of performance. It's a programming lesson only. Experience even show that premature unproven tweaks can both reduce performance and make code harder to read and maintain.
Then there's the business lesson: Since for the last decades we've had Moore's Law and then more, it's been very hard to make the effort pay off by programming for performance. So businesses have learnt to focus on reducing programming time. Coincidentally, it's been shown that quick lead times are beneficial in the competitive marketplace as well. This is a business lesson (not about the programming phrase "premature optimization"!).
We're seeing a reintroduction of optimization and performance, because meeting a ceiling in CPU cycles and the need to utilize more cores efficiently. So we have Golang, Rust, WebAssembly, etc. Having a snappy website and not annoy your users will pay off as well (hello there multiple choice agreement-notices!).
But the programming lesson still stands: For many types of workloads, it doesn't make sense to spend too much time optimizing, performance wise, unless you see proven benefit outweighing the costs. In most cases, it's actually better to optimize afterwards (ie. prototyping and iterating), unless one has a specific algorithm or solution in mind beforehand.
The business lesson is similar, with the added twist of being a criteria wether you make it or break it. For programming, you could just do it for fun or a hobby, and can premature optimize to your hearts content if you like. But it'll be harder now to fall into that trap instead of making something more worthwhile! ;-)
What's "evil" is optimizing without benchmarks/profiles/etc. Naive implementations are usually easier to write, and can give you a baseline for how much there is to gain (as well as providing "correct examples" for more complicated algorithms).
If you know you will need to cache something just cache it, it's not premature, it's best practices.
Exercise the Pareto principal during development and the areas that truly need optimized will present themselves in time.
I have coined the term "voodoo optimization" in response to a point Martin Fowler made in his book "Refactoring 2nd Edition": When running Javascript, for example, you are working with a compiler and engine that has had thousands of man-hours and millions of dollars invested into it.
The compiler is throwing away variable declarations. It's merging for-loops. What you put in is not what comes out. You need concrete numbers and FACTS to optimize your code. Deciding "this looks slow" is not an effective optimization method.
> Today, it is not at all uncommon for software engineers to extend this maxim to "you should never optimize your code!" Funny, you don't hear too many computer application users making such statements.
Funny, you don't hear too many computer application users asking for optimization, either. The rare, high-profile cases where people complain that something is slow get a lot of attention, but the majority of the time, the feedback you get from users is a resounding silence. I wish users would give me unsolicited actionable feedback on my software, but the reality is, it takes effort to get feedback, and usually people don't complain about performance, they just have a general feeling of malaise about the software that doesn't rise to the level of an explicit complaint. In 11 years of software development, I've had only a handful of users ever complain about performance. The times I've optimized are almost always a result of performance logging. Performance logging lets me say to stakeholders, "This DB query is taking a full second, and 30% of users are exiting the application on that screen--can I spend time to optimize this?"
Funny, you don't actually hear too many software engineers actually saying "you should never optimize your code", either.
I stopped reading at the "observations" section, which were just too full of cringe.
I skimmed the rest, though, and noticed that the author's suggests a few books on assembly language. Good call, guy, I'll be sure to tie my application to a specific processor architecture so I can make it extra difficult to understand why memory is getting thrashed or thread switches are happening at such inopportune times.
Software does need to be architected for performance up front. If you aren't able to work on data with a lot of locality or have latency between fundamental operations, you won't get fast software until you address these issues.
If you are really starting from scratch you will barely understand the problem, but once you do, you can make sure your architecture will align with what you are doing. After that, optimization becomes much lower hanging fruit.
Embedded programmers can probably be identified by their insistence on code efficiency. Speed, space, storage, all critical to them.
Well it really mattered to me when I lost my patience and replaced a piece of code written in Python that was doing some data manipulation/processing with the native one. Suddenly what used to take an hour got down to less then 1 minute.
Yes I understand it may not matter much for many database front end apps but the world does not end on those.
Is 'performance' the right word for this? Its more like user experience or latency - the controls/graphics should be run on a different thread than the data processing.
It is both. All my desktop apps are strictly native and written with care. Many use DirectX graphics for output. Also I've never bought into this Microsoft's move to .NET on desktop propaganda. Electron etc. - would not touch such frameworks with the wooden pole.
I think that this is important to be shared once in a while
I've never met any of these engineers who think optimization is always wrong.
"No gotos" "You aint gonna need it" "No benefit for the customer"
And of course, the topic of this link.
And it still might be that way, if the piece you're optimizing isn't performance critical at all, and the effort might be better spent elsewhere. But it might not.
The whole thing is a grey area and a good software developer learns to spot when they're spending time on something that doesn't need this effort right now.