Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

"Premature optimization is root of all evil" is something almost all of us have heard/read. What I am curious what kind of optimization not premature, i.e. at every stage of software development (high level design, detailed design, high level implementation, detailed implementation etc) what is extent of optimization we can consider without it crossing over to dark side.

share|improve this question
2  
1  
See also: Is micro-optimisation important when coding? – gnat May 7 '13 at 8:50

12 Answers 12

up vote 94 down vote accepted

When you're basing it off of experience? Not evil. "Every time we've done X, we've suffered a brutal performance hit. Let's plan on either optimizing or avoiding X entirely this time."

When it's relatively painless? Not evil. "Implementing this as either Foo or Bar will take just as much work, but in theory, Bar should be a lot more efficient. Let's Bar it."

When you're avoiding crappy algorithms that will scale terribly? Not evil. "Our tech lead says our proposed path selection algorithm runs in factorial time; I'm not sure what that means, but she suggests we commit seppuku for even considering it. Let's consider something else."

The evil comes from spending a whole lot of time and energy solving problems that you don't know actually exist. When the problems definitely exist, or when the phantom psudo-problems may be solved cheaply, the evil goes away.


Steve314 and Matthieu M. raise points in the comments that ought be considered. Basically, some varieties of "painless" optimizations simply aren't worth it either because the trivial performance upgrade they offer isn't worth the code obfuscation, they're duplicating enhancements the compiler is already performing, or both. See the comments for some nice examples of too-clever-by-half non-improvements.

share|improve this answer
19  
Occasionally, solving a phantom problem easily is still mildly evil, as it can result in harder to read, harder to maintain code. Not much harder (or it wouldn't be an easy solution), but perhaps occasionally still relevant. An example might be using a clever bitwise trick that some people won't recognise, and which the compiler will probably apply anyway if it's useful. – Steve314 Jan 1 '11 at 12:03
21  
I agree with Steve here, sometimes the "optimization" is simply not worth it, especially because compilers are so damn good. Example ? if i is unsigned, i / 2 can be replaced by i >> 1. It is faster. But it is also more cryptic (not everyone will see the effect, even those who do may lose time). But the worst of it is that the compiler will do it anyway, so why obfuscate the source code ;) ? – Matthieu M. Jan 1 '11 at 13:53
17  
@Larry : I didn't, so I guess it's a good example. – Joris Meys Jan 1 '11 at 15:01
16  
In my view, optimisations, even simple ones, should also be regarded evil if they impact readabiliy/maintainabiliy of the code and are not based on actual performance measurements. – Bart van Ingen Schenau Jan 1 '11 at 17:17
10  
@Matthew: Teach them what? Dirty and unnecessary tricks? Why? If profiling shows that a i/2 is indeed a hot spot and that (unbelievable, but let's assume) i>>1 makes it faster, so do it, and put a comment to it that this profiling showed that this is faster. If this is indeed needed anywhere (which I doubt, since, as Matthieu said, compilers should be smart enough to do this themselves), novices will learn something, if it isn't (which is likely), why do you want to plug their heads with unneeded folklore? – sbi Jan 2 '11 at 20:23

what kind of optimization [is] not premature

The kind that come as a result of known issues.

share|improve this answer

You should always choose a "good enough" solution in all cases based on your experiences.

The optimization saying refers to writing "more complex code than 'good enough' to make it faster" before actually knowing that it is necessary, hence making the code more complex than necessary. Complexity is what makes things hard, so that isn't a good thing.

This means that you should not choose a super complex "can sort 100 Gb files by transparently swapping to disk" sorting routine when a simple sort will do, but you should also make a good choice for the simple sort in the first place. Blindly choosing Bubble Sort or "pick all entries randomly and see if they are in order. Repeat." is rarely good.

share|improve this answer

Application code should only be as good as necessary, but library code should be as good as possible, since you never know how your library is going to be used. So when you're writing library code, it needs to be good in all aspects, be it performance, robustness, or any other category.

Also, you need to think about performance when you design your application and when you pick algorithms. If it isn't designed to be performant, no degree of hackery can make it performant afterwards and no micro-optimizations will outweigh a superior algorithm.

share|improve this answer
4  
Library code should document whether it's trying to be "as good as possible", or what its objective is. Code need not be absolutely optimal in order to be useful, provided that consumers only use it when appropriate. – supercat May 13 '14 at 1:56
    
Sorry, but "be good in all aspects" sounds suspiciously like overengineering. Plus, it's probably not realistic - life is always about tradeoffs. – sleske Jun 17 '15 at 10:23
1  
+1 for emphasizing the design phase; if you're deliberately weighing its benefits, it's not premature. – Nathan Tuggy Jan 3 at 23:14
    
Conversely, if you never know how your library is going to be used, you don't know whether spending time on improving it has any business value at all. So that's hardly an argument. – RemcoGerlich Jan 7 at 9:54

My general rule of thumb: if you're not sure you'll need the optimization, assume you don't. But keep it in mind for when you do need to optimize. There are some issues that you can know about up front though. This usually involves choosing good algorithms and data structures. For instance, if you need to check membership in a collection, you can be pretty sure you will need some type of set data structure.

share|improve this answer

In my experience, at the detailed implementation phase the answer lies in profiling the code. Its important to know what needs to be faster and what is acceptably fast.

It is also important to know where exactly the performance bottleneck is - optimizing a part of the code which takes only 5% of the total time to run wont do any good.

Steps 2 and 3 describe non-premature optimization:

  1. Make it work
  2. Test. Not fast enough? Profile it.
  3. Using the data from step 2, optimize the slowest sections of the code.
share|improve this answer
    
You forgot step 0, which is: architect the application properly so that you can expect reasonable performance from the start. – Robert Harvey Jan 6 '11 at 23:53
    
I was only speaking about the detailed implementation phase. – Gorgi Kosev Jan 7 '11 at 1:21
1  
I question step #3--very often the best answer is to figure out a different approach so you're not doing the slow bit of code in the first place. – Loren Pechtel Jan 14 '11 at 5:25
1  
Pick the right data structures. – jasonk Mar 15 '12 at 13:25

The full quote defines when optimization is not premature:

A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. [emphasis mine]

You can identify critical code in many ways: critical data structures or algorithms (e.g. used heavily or the "core" of the project) can give major optimizations, many minor optimizations are identified through profilers, and so on.

share|improve this answer
3  
Yeah... It's all well and good to shave 90% off the time a random function call takes, but maybe you'd get a bigger impact by looking at the code where your app actually spends 80% of its time and shaving off a few percent there. – fennec Jan 14 '11 at 3:51

It's not optimisation when picking things that are hard to change eg: hardware platform.

Picking data structures is a good example - critical to meeting both functional and non-functional (performance) requirements. Not easily changed and yet it will drive everything else in your app. Your data structures change what algorithms are available etc.

share|improve this answer

Most people would call optimization premature, if you're optimizing something that isn't resulting in a "soft failure" (it works but it's still useless) of the system due to performance.

Real world examples.

  • If my bubble sort takes 20ms to run, optimizing it to 1ms quicksort is not going to enhance the overall utility in any meaningful way despite being a 2000% performance increase.

  • If a web page takes 20s to load and we decrease it to 1s, this can increase the utility of the website from 0 to near infinity. Basically something that was broken because it was too slow, is now useful.

share|improve this answer

When the requirements or the market specifically asks for it.

For example performance is a requirement in most financial applications because low latency is crucial. Depending on the nature of the traded instrument, optimization can go from using non-locking algorithms in a high-level language to using a low-level language and the even the extreme - implementing the order matching algorithms in hardware itself (using FPGA for example).

Other example would be some types of embedded devices. Take for example the ABS brake; firstly there is the safety, when you hit the break the car should slow down. But there is also performance, you would not want any delays when you hit the break.

share|improve this answer

I only know of one way to answer this question, and that is to get experience in performance tuning. That means - write programs, and after they are written, find speedups in them, and do it iteratively. Here's one example.

Here's the mistake most people make: They try to optimize the program before actually running it. If they have taken a course in programming (from a professor who doesn't actually have much practical experience) they will have big-O colored glasses, and they will think that's what it's all about. It's all the same problem, prior optimization.**

Somebody said: First make it right, Then make it fast. They were right.

But now for the kicker: If you have done this a few times, you recognize the silly things you earlier did that cause speed problems, so you instinctively avoid them. (Things like making your class structure too heavy, getting swamped with notifications, confusing size of function calls with their time cost, the list goes on and on ...) You instinctively avoid these, but guess what it looks like to the less-experienced: premature optimization!

So these silly debates go on and on :)

** Another thing they say is you don't have to worry about it any more, because compilers are so good, and machines are so fast nowadays. (KIWI - Kill It With Iron.) There are no exponential hardware or system speedups (done by very smart hard-working engineers) that can possibly compensate for exponential software slowdowns (done by programmers who think this way).

share|improve this answer

Donald Knuth in favor of goto statements for speeding up software:

[...] again, this is a noticeable saving in the overall running speed, if, say, the average value of n is about 20, and if the search routine is performed about a million or so times in the program. Such loop optimizations [using gotos] are not difficult to learn and, as I have said, they are appropriate in just a small part of a program, yet they often yield substantial savings. [...]

Knuth continues:

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 pennywise-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 oneshot 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 [i.e., goto statements in this context].

... Pay careful attention to how he used "optimized" in quotes and the implications of that.

Finally, to the frequently-quoted part:

There is no doubt that the grail of efficiency leads to abuse. 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 forgot about small efficiencies, say 97% of the time; premature optimization is the root of all evil.

... and then some more:

It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail. After working with such tools for seven years, I've become convinced that all compilers written from now on should be designed to provide all programmers with feedback indicating what parts of their programs are costing the most; indeed, this feedback should be supplied automatically unless it has been specifically turned off.

After a programmer knows which parts of his routines are really important, a transformation like doubling up loops will be worthwhile. Note that this transformation introduces go to statements -- and so do several other loop optimizations.

What most people don't realize is that Knuth's quote was part of an argument to use goto as a micro-optimization to speed up software.

What Knuth was talking about in using "premature" was really more like "misguided", just like how he used "optimized" (somewhat condescending, but the likely implication of that is that these programs made by "pennywise-and-pound-foolish programmers" aren't actually efficient at all). It was a careful statement to qualify that his suggestion to use goto to optimize code should really be backed by experience and utilized by people who what they are doing, and applied for actual performance-critical execution paths in their software (not blindly throughout a codebase).

It's an argument in favor of optimizations (especially micro-optimizations which have a real impact), but with the wise precaution to only do this with experience (from either recent or past measurements, knowing full well how human predictions of hardware behavior are often wrong) and knowing what actually makes a real difference, and to only do this in places that genuinely benefit from it.

What constitutes "premature" in this context, above all, is superstition, inexperienced hunches, and trying to apply optimizations (of any form) to places that aren't necessarily even critical execution paths (poor prioritization). It's trying to save pennies over pounds.

Knuth's micro-optimizations, on the other hand, weren't "premature" (as in misguided, based on a lack of knowledge, ineffective) since they were being applied to critical paths and showed a demonstrable improvement (12%, e.g.). And most importantly, while he would never be so bold to say this, they were being applied by someone with the prerequisite experience.

Knuth as the Ultimate Micro-Optimizer

Knuth was a pioneering micro-optimizer pushing for careful, experienced micro-optimizations of code -- the hallmark of an experienced developer working in performance-critical areas.

While optimizing compilers have often made a lot of Knuth's former suggestions to use goto for speed moot today, a modern version of this might resemble advice suggesting to use SIMD intrinsics, multithreading, and cache-friendly memory optimizations in the smallest, most critical places that really benefit from it most, and to not apply these kinds of optimizations blindly throughout a codebase based on preconceived hunches about inefficiencies that might not even exist (or at least don't actually matter).

Knuth's argument is actually one of the ultimate for, not against, micro-level optimizations. The difference is that his caveat about premature optimization is to warn that people who do this kind of stuff should really know what they are doing, and should apply such micro-optimizations judiciously.

I tend to imagine (not necessarily accurately) Dijkstra as being the more dogmatic type saying "gotos are evil!", with Knuth being the more pragmatic type responding, "but gotos are really fast, they just shouldn't be abused!" And this kind of basic argument that Knuth made in favor of micro-optimizations still rages on today, but for different features than goto statements. It might be, "Multithreading is evil! Yes, but some of us have machines with 32 cores already and 31 of them are often wasted!"

History in Context

It's worth noting that at Knuth's time, there weren't rich libraries and frameworks available which were already micro-optimized to death for us to use. Even quicksorting an array was a manual endeavor.

A lot of the modern transformation of "premature optimization" can veer towards wanting to dismiss all forms of micro-optimization. That's an easier mindset when we're leaning on libraries and compilers that have been micro-optimized already, but there's still plenty of new territory to cover which these don't cover.

Knuth's arguments to favor discreet micro-optimizations make the most sense in those uncovered (or possibly outright explored) territories when we have to do things like actually implement our own data structures not available through a standard library, or are the library implementors providing this functionality that so many programmers worldwide depend upon to do their daily work.

Penny-Wise and Pound-Foolish

I think Knuth's description here often hits a lot of what we consider premature optimization. If we observe someone who is:

  1. Trying to optimize a 200-line function call involving dynamic dispatch (the function call itself, not the function)...
  2. Applying this "optimization" in an area that isn't even shown to be critical and looks very dubious as to whether it's actually being called often...

... then this is generally a very strong sign of premature optimization, in that 1 suggests they are trying to save pennies over pounds, and 2 suggests that they're trying to save pennies that don't even compound.

I think Knuth's wording involving "premature" was a bit misleading, since this is often the bigger point. No matter how early or late an optimization is applied, if it's ineffective in this regard, it would fit Knuth's idea of "premature" (which I think is far better worded as "misguided"). It's not about timing, since these optimizations would often degrade maintainability a whole lot to gain so little (and sometimes even make performance worse).

The part of Knuth's description which calls for the word, "premature", is that such temptations to do something like this are often based on hunches about how the hardware works or about how the compiler works which are often wrong. They're premature in the sense that they're being applied before the prerequisite experience to do this correctly is acquired.

Measurements

Measurements definitely give the necessary experience to optimize effectively, to start saving pounds over pennies. People with profilers in their hand don't end up spending all day optimizing an execution path that takes 0.00001% of the time. The profiler keeps them honest. So we can generally discount people who are profiling from the "premature optimizer" list, unless they're running their profilers over operations that users don't even care about (I think it's generally good enough to give the benefit of the doubt once someone actually demonstrates that they're profiling and measuring here).

But Knuth's point wasn't necessarily that all such optimizations need be applied in hindsight after measuring. If someone designs their data structures upfront to be memory efficient in ways that definitely improve locality of reference, it's not necessarily premature. Measuring would still definitely reveal that the developer is doing this correctly, but someone designing a particle system upfront with sequential access patterns to use SoA fields doesn't necessarily need to profile their code first using an AoS representation only to rewrite it all to SoA. The difference here is that there would be sufficient experience to know that, given the sequential access patterns and the heavy load that particle systems almost always have to deal with, the fastest optimal representation would be SoA (possibly due to previous measurements elsewhere, or just a solid enough understanding of the memory hierarchy and SIMD instructions).

In the same sense, if you know you are going to deal with the need to sort inputs spanning a million or more entries upfront, it's not necessarily premature to reach for an efficient sorting algorithm here like quicksort upfront, even when working in a scenario that doesn't provide such algorithms through a library and must be written by hand. The difference is that the person doing this would have the sufficient experience in advance to be absolutely sure that it would pay off, that choosing a bubble sort here would be a very foolish choice that would only end up needing a rewrite.

It's experience, above all else, that hits the "premature" side, not the timing in which an optimization is applied.

Testing

A lot of people suggest that optimizing prior to testing is premature, but that's the modern TDD mentality. Knuth's suggestions to use goto discreetly to speed up code weren't necessarily backed by a unit and integration testing mindset over continuous integration. Such concepts were unheard of at the time.

I like that mindset and agree with it, but it was far past the concerns at the time the paper was written. This is a great modern and updated mindset of what constitutes "premature optimization", to base it on testing and soundness of the software first, but if we're trying to get at the heart of what Knuth was trying to say, this kind of test-driven mindset wasn't included. Instead Knuth was an advocate of meticulous documentation (commenting) of code with literate programming (something I think most of us don't agree with today), not necessarily the most sound when it came to writing tests.

share|improve this answer
1  
It's refreshing to see someone bring a fresh take to this old chestnut. All it takes is to read Knuth's entire quote, and not just one sentence, eh? – Robert Harvey Jan 7 at 15:04
    
@RobertHarvey I have a little bit of a pet peeve there -- since so many seem to quote just that one sentence, and so much important contextual info ends up being lost in the process. I'm not sure it's such a great answer since I got a tad ranty. :-D – Ike Jan 7 at 16:56

protected by MichaelT Jun 15 '15 at 20:07

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.