82

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

yannis
  • 39,547
  • 40
  • 183
  • 216
Gaurav
  • 3,729
  • 2
  • 25
  • 43
  • 2
    See also http://programmers.stackexchange.com/questions/14856/best-practices-that-you-disagree-with/14882#14882 – Robert Harvey Jan 01 '11 at 20:52
  • 1
    See also: [Is micro-optimisation important when coding?](http://programmers.stackexchange.com/questions/99445/is-micro-optimisation-important-when-coding) – gnat May 07 '13 at 08:50

14 Answers14

119

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.

Community
  • 1
BlairHippo
  • 8,663
  • 5
  • 41
  • 46
  • 24
    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. –  Jan 01 '11 at 12:03
  • 28
    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 01 '11 at 13:53
  • 2
    @Matthieu: I understood i >> 1 right away. Do you have a better example? – Larry Coleman Jan 01 '11 at 14:46
  • 19
    @Larry : I didn't, so I guess it's a good example. – Joris Meys Jan 01 '11 at 15:01
  • @Larry: Not off the top of my head, sorry, but I can guarantee you I have colleagues who would make a double take on this. – Matthieu M. Jan 01 '11 at 16:55
  • 18
    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 01 '11 at 17:17
  • @Matthieu and Joris: If you're doing C# or Java coding, I guess it's understandable not to know the logical shift operators. The libraries for both are so big that one person cannot possibly know them all, so why bother learning operators you won't have any reason to use? – Larry Coleman Jan 01 '11 at 17:33
  • 10
    @Larry: I have been doing C++ almost exclusively for the past 3 years (with some Python and an introduction to Haskell), nonetheless even if you do know the effect of the shift operators or of bit masking, it does obfuscate the code somewhat, to use `i & ~(unsigned int)1` when one simply wants `i - i%2` (that is, the greatest even number inferior or equal to the current number) or that kind of things. Of course, you can always wrap this up in an inline function with a meaningfull name, but unless inspecting the assembly / measuring shows a difference... I would not bother. – Matthieu M. Jan 01 '11 at 19:29
  • @Matthieu: That is a much better example. You should make an answer out of it. – Larry Coleman Jan 01 '11 at 19:42
  • @Matthieu M. / @Steve314: An excellent point, and one I hadn't considered. I'll integrate it into the answer. – BlairHippo Jan 01 '11 at 21:33
  • 1
    Generally things like which framework or database to work with make the most difference. The higher level decisions, the ones you cannot change later on, are more important. Always benchmark/profile before you do any optimizations and stop when you reach the goal. Smaller optimizations like chaning `i++` to `++i` make about as much difference as a drop in a swimming pool. First plant the right tree (language, framework stack) then pick the lowest hanging fruits first. Or just shake the tree :) – Benbob Jan 01 '11 at 23:09
  • 2
    To the comment over `i/2` versus `i>>1`... this would be a good chance to teach junior devs something instead of just coding to the least common denominator. – Matthew Whited Jan 02 '11 at 14:18
  • 14
    @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 02 '11 at 20:23
  • 8
    You said "Basically, some varieties of 'painless' optimizations simply aren't ... worth the code obfuscation." The thing people need to understand is that **code obfuscation isn't painless**. – Ken Bloom Jan 14 '11 at 01:04
  • 1
    I can't imagine not knowing the bit shift operators for any language. Sure, i / 2 is generally clearer but now and then you're really working at the bit level and thus the bit shift operators are actually clearer. – Loren Pechtel Jan 14 '11 at 05:22
  • 1
    All of these involve could be restated as "X facts show that Y is better than Z in some *non-trivial* manner. Therefore, let us use Y instead of Z." This is the same as not prematurely optimizing, you just didn't need to find the facts, since you already have them. – Spencer Rathbun Mar 15 '12 at 13:31
  • @sbi: I only use the division or remainder operators if there is some reason why I need to those it rather than a shift or bitmask, perhaps because shift and bitmask operators will in most implementations give the results I need with positive or negative divisors, while `/` and `%` will add extra code bloat adjusting the results to be wrong, and necessitate the use of extra code bloat to set it right. Rather than worry about whether `/` or `%` will work correctly, it's easier to just use `>>` and `&`. If there were operators that behaved like `/` and `%` for Euclidian division, I'd use those – supercat May 13 '14 at 01:54
  • 2
    Who says that "painless" optimizations always result in "code obfuscation"? There are far too many "never" and "always" in these comments. Programming is a grey area and noone can say that A or B is always or never a good solution. – Olof Forshell Oct 06 '15 at 13:09
38

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.

Robert Harvey
  • 198,589
  • 55
  • 464
  • 673
sbi
  • 9,992
  • 6
  • 37
  • 56
  • 5
    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 01:56
  • 2
    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 03 '16 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 07 '16 at 09:54
25

what kind of optimization [is] not premature

The kind that come as a result of known issues.

George Marian
  • 4,360
  • 26
  • 31
17

When is optimization not premature and therefore not evil?

It is difficult to say what is good and evil. Who has that right? If we look at nature, it seems we are programmed for survival with a broad definition of "survival" which includes passing on our genes to offspring.

So I would say, at least according to our basic functions and programming, that optimization is not evil when it is aligning with the goal of reproduction. For the guys, there are the blondes, brunettes, red-heads, many lovely. For girls, there are guys, and some of them appear to be okay.

Perhaps we should be optimizing towards that purpose, and there it helps to use a profiler. The profiler will let you prioritize your optimizations and time more effectively on top of giving you detailed information about hotspots and why they occur. This will give you more free time spent towards reproduction and its pursuit.

  • 3
    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 07 '16 at 15:04
  • 1
    @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 –  Jan 07 '16 at 16:56
14

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.

Community
  • 1
Fred Nurk
  • 845
  • 6
  • 11
  • 6
    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. –  Jan 14 '11 at 03:51
11

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.

3

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.

jasonk
  • 1,693
  • 1
  • 11
  • 9
3

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

Community
  • 1
Mike Dunlavey
  • 12,815
  • 2
  • 35
  • 58
3

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.

Jason Baker
  • 9,625
  • 8
  • 44
  • 67
3

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.
Gjorgi Kjosev
  • 131
  • 3
2

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.

Random42
  • 10,370
  • 10
  • 48
  • 65
0

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.

Eric Rini
  • 109
  • 2
  • It's important to note that if your sort is called 1000 times over the course of your program, optimizing from 20ms to 1ms is a big deal. – Beefster Apr 26 '18 at 23:01
0

What kind of optimisation is not premature?

An optimisation that fixes a known performance issue with your application, or an optimisation that allows your application to meet well defined acceptance criteria.

Having been identified, some time should be taken to establish the fix and the performance benefit should be measured.

(i.e. it's not - "I think this bit of the code looks like it could be slow, I'll change X to use Y instead and that will be faster").

I have encountered lot of premature "optimisation" that has ultimately made the code slower - in this instance, I'm taking premature to mean 'not thought through'. Performance should be benchmarked before and after optimisation and only code that actually improves performance kept.

Paddy
  • 2,623
  • 16
  • 17
0

"Premature optimization is root of all evil" is something almost all of us have heard/read

True. Unfortunately it is also one of the most (maliciously) misused programming quotes of all times. Since Donald Knuth coined the meme it's worth to add some original context from the quote:

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 %. ... A good programmer ... will be wise to look carefully at the critical code; but only after that code has been identified. ... the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail

Note that Knuth talked specifically about speed of execution in runtime.

..Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs..

Also, he wrote the article in 1974 when any machine resources where at premium and negative correlation between speed of execution and maintainability of the program (higher speed - less maintainable) was probably stronger than now.

OK, to answer your question, according to Donald Knuth, optimization is NOT premature if it fixes a serious performance bottleneck that has been identified (ideally measured and pinpointed during profiling).

As I said before, "premature optimization" is one of the most maliciously misused memes, so answer won't be complete without some examples of things that are not premature optimizations but sometimes being shrugged off as such:

  • bottlenecks which are visible with the naked eye and can be avoided before being introduced such as O(N^2) number of roundtrips to database with large N where O(1) alternative exists

Further are not even related to speed of runtime execution:

  • thoughtful upfront design

  • static typing (!)

  • etc. / any forms of mental effort

KolA
  • 605
  • 4
  • 10