When is optimisation premature?

Question

As Knuth said,

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

This is something which often comes up in Stack Overflow answers to questions like "which is the most efficient loop mechanism", "SQL optimisation techniques?" (and so on). The standard answer to these optimisation-tips questions is to profile your code and see if it's a problem first, and if it's not, then therefore your new technique is unneeded.

My question is, if a particular technique is different but not particularly obscure or obfuscated, can that really be considered a premature optimisation?

Here's a related article by Randall Hyde called The Fallacy of Premature Optimization.

Answer 1

As I posted on a similar question, the rules of optimisation are:

1) Don't optimise

2) (for experts only) Optimise later

When is optimisation premature? Usually.

The exception is perhaps in your design, or in well encapsulated code that is heavily used. In the past I've worked on some time critical code (an RSA implementation) where looking at the assembler that the compiler produced and removing a single unnecessary instruction in an inner loop gave a 30% speedup. But, the speedup from using more sophisticated algorithms was orders of magnitude more than that.

Another question to ask yourself when optimising is "am I doing the equivalent of optimising for a 300 baud modem here?". In other words, will Moore's law make your optimisation irrelevant before too long. Many problems of scaling can be solved just by throwing more hardware at the problem.

Last but not least it's premature to optimise before the program is going too slowly. If it's web application you're talking about, you can run it under load to see where the bottlenecks are - but the likelihood is that you will have the same scaling problems as most other sites, and the same solutions will apply.

edit: Incidentally, regarding the linked article, I would question many of the assumptions made. Firstly it's not true that Moore's law stopped working in the 90s. Secondly, it's not obvious that user's time is more valuable than programmer's time. Most users are (to say the least) not frantically using every CPU cycle available anyhow, they are probably waiting for the network to do something. Plus there is an opportunity cost when programmer's time is diverted from implementing something else, to shaving a few milliseconds off something that the program does while the user is on the phone. Anything longer than that isn't usually optimisation, it's bug fixing.

Answer 2

Unless you find that you need more performance out of your application, due to either a user or business need, there's little reason to worry about optimizing. Even then, don't do anything until you've profiled your code. Then attack the parts which take the most time.

Answer 3

It's worth noting that Knuth's original quote came from a paper he wrote promoting the use of goto in carefully selected and measured areas as a way to eliminate hotspots. His quote was a caveat he added to justify his rationale for using goto in order to speed up those critical loops.

[...] 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. [...]

And 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].

Keep in mind how he used "optimized" in quotes (the software probably isn't actually efficient). Also note how he isn't just criticizing these "pennywise-and-pound-foolish" programmers, but also the people who react by suggesting you should always ignore small inefficiencies. 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 about the importance of profiling tools:

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.

People have misused his quote all over the place, often suggesting that micro-optimizations are premature when his entire paper was advocating micro-optimizations! One of the groups of people he was criticizing who echo this "conventional wisdom" as he put of always ignoring efficiencies in the small are often misusing his quote which was originally directed, in part, against such types who discourage all forms of micro-optimization.

Yet it was a quote in favor of appropriately applied micro-optimizations when used by an experienced hand holding a profiler. Today's analogical equivalent might be like, "People shouldn't be taking blind stabs at optimizing their software, but custom memory allocators can make a huge difference when applied in key areas to improve locality of reference," or, "Handwritten SIMD code using an SoA rep is really hard to maintain and you shouldn't be using it all over the place, but it can consume memory much faster when applied appropriately by an experienced and guided hand."

Any time you're trying to promote carefully-applied micro-optimizations as Knuth promoted above, it's good to throw in a disclaimer to discourage novices from getting too excited and blindly taking stabs at optimization, like rewriting their entire software to use goto. That's in part what he was doing. His quote was effectively a part of a big disclaimer, just like someone doing a motorcycle jump over a flaming fire pit might add a disclaimer that amateurs shouldn't try this at home while simultaneously criticizing those who try without proper knowledge and equipment and get hurt.

What he deemed "premature optimizations" were optimizations applied by people who effectively didn't know what they were doing: didn't know if the optimization was really needed, didn't measure with proper tools, maybe didn't understand the nature of their compiler or computer architecture, and most of all, were "pennywise-and-pound-foolish", meaning they overlooked the big opportunities to optimize (save millions of dollars) by trying to pinch pennies, and all while creating code they can no longer effectively debug and maintain.

If you don't fit in the "pennywise-and-pound-foolish" category, then you aren't prematurely optimizing by Knuth's standards, even if you're using a goto in order to speed up a critical loop (something which is unlikely to help much against today's optimizers, but if it did, and in a genuinely critical area, then you wouldn't be prematurely optimizing). If you're actually applying whatever you're doing in areas that are genuinely needed and they genuinely benefit from it, then you're doing just great in the eyes of Knuth.

Answer 4

Don Knuth started the literate programming movement because he believed that the most important function of computer code is to communicate the programmer's intent to a human reader. Any coding practice that makes your code harder to understand in the name of performance is a premature optimization.

Certain idioms that were introduced in the name of optimization have become so popular that everyone understands them and they have become expected, not premature. Examples include

• Using pointer arithmetic instead of array notation in C, including the use of such idioms as

  for (p = q; p < lim; p++)
  

• Rebinding global variables to local variables in Lua, as in

  local table, io, string, math
      = table, io, string, math
  

Beyond such idioms, take shortcuts at your peril.

All optimization is premature unless

• A program is too slow (many people forget this part).

• You have a measurement (profile or similar) showing that the optimization could improve things.

(It's also permissible to optimize for memory.)

Direct answer to question:

• If your "different" technique makes the program harder to understand, then it's a premature optimization.

---

EDIT: In response to comments, using quicksort instead of a simpler algorithm like insertion sort is another example of an idiom that everyone understands and expects. (Although if you write your own sort routine instead of using the library sort routine, one hopes you have a very good reason.)

Answer 5

First, get the code working. Second, verify that the code is correct. Third, make it fast.

Any code change that is done before stage #3 is definitely premature. I am not entirely sure how to classify design choices made before that (like using well-suited data structures), but I prefer to veer towards using abstractions taht are easy to program with rather than those who are well-performing, until I am at a stage where I can start using profiling and having a correct (though frequently slow) reference implementation to compare results with.

Answer 6

IMHO, 90% of your optimization should occur at design stage, based on percieved current, and more importantly, future requirements. If you have to take out a profiler because your application doesn't scale to the required load you have left it too late, and IMO will waste a lot of time and effort while failing to correct the problem.

Typically the only optimizations that are worthwhile are those that gain you an order of magnitude performance improvement in terms of speed, or a multiplier in terms of storage or bandwidth. These types of optimizations typically relate to algorithm selection and storage strategy, and are extremely difficult to reverse into existing code. They may go as deep as influencing the decision on the language in which you implement your system.

So my advice, optimize early, based on your requirements, not your code, and look to the possible extended life of your app.