What optimizations are premature?

Question

I've been here for nearly a month and it seems that people have a tendency to be eager to use the "Premature Optimization is the root of all evil" argument as soon as someone mentions efficiency.

What is really a premature optimization? What is the difference between what is essentially writing a well designed system, or using certain methods and premature optimizations?

Certain aspects that I feel should be interesting topics within this question:

• In what way does the optimization influence code complexity?
• How does the optimization influence development time/cost?
• Does the optimization emphasize further understanding of the platform(if applicable)?
• Is the optimization abstractable?
• How does the optimization influence design?
• Are "general solutions" the better choice instead of specific solutions for a problem because the specific solution is an optimization?

EDIT / update: Found these two links that are very interesting regarding what a premature optimization really is:
http://smallwig.blogspot.com/2008/04/smallwig-theory-of-optimization.html
http://www.acm.org/ubiquity/views/v7i24_fallacy.html

Answer 1

When you optimise something without profiling it. How can you be sure it will actually speed anything up? If anything it is likely to make your code harder to read and less maintainable without any real benefit. Modern compilers have a huge array of optimisations they can use, in many cases you may have no idea what effect (speedwise) your optimisation may have.

In short: Profile, Optimise, Profile, Optimise...

Answer 2

Any optimisation that involves an associated pessimisation (i.e readability, maintainability) without a clear benefit, demonstrable via testing/profiling.

Answer 3

Premature optimization is often meant to refer to something that makes the code less legible while at the same time attempting to increase performance. When asking what, exactly, it might look like I can best describe it as "you know it when you see it" which probably doesn't help.

Some offhand examples that I can think of:

1. Using bit mangling to increment a counter in a for-loop.
2. Creating one gigantic function instead of many smaller functions to avoid function call overhead.
3. Setting everything public to avoid the overhead of mutators and accessors.
4. Creating a list of commonly used strings within a data object so that they do not need to be constantly reallocated (string pooling anyone?)
5. Writing your own collection which mirrors functionality within an existing collection to avoid the overhead of bounds checking.

I'm sure there's more I've seen but, you get the idea.

Answer 4

As an example, I have seen developers focus on specific code optimizations that inevitably make no difference. The focus should be to get the thing working and use profilers to tell you how much time is being spent. Using profilers is akin to going after the low hanging fruit.

The compiler itself will make many optimizations. I would think that if you keep your code complexity low, the compiler will have a better chance to get more optimizations.

Some optimizations are specific to the implementation and if the architecture/design is still influx, there can be a lot of wasted time and effort.

Answer 5

A typical premature optimization I encountered a lot of times is doing everything in the same function because of "function call overhead". The result is an insanely huge function which is difficult to maintain.

The fact is: you don't know where the code is slow until you actually run a profiler. I've seen a very interesting demonstration of this point when I've been asked to optimize some code, a long time ago. I already had a course in code optimization, so I ran gprof and checked. The result was that 70 % of the running time was spent zeroing arrays. When you face such situation, the speedup you can obtain is negligible, and every effort is just going to make things worse.

Another case is handmade loop unrolling. Most compilers support loop unrolling as a feature, but unrolling every loop you create just because you are told it's a possible speedup strategy is wrong. The point of optimization is not to write high-performance code. It is to write high-performance code where there's a need for it.

To answer your questions

In what way does the optimization influence code complexity?

optimized code most likely contains clever tricks, and clever tricks tend to be 1) non portable across platforms, 2) not easy to understand immediately. Optimization necessarily produces more difficult code.

How does the optimization influence development time/cost?

you pay a development price to perform optimization, both for the actual brainwork to do, for the code deployment and testing, and for the less maintainable code you obtain. For this reason, optimization is better done on code that you are not going to touch in the future (e.g. base libraries or frameworks). Pristine new, or research code are better left unoptimized for obvious reasons.

Clearly, performance can be a product, so the important point is to strike the balance between development investment and customer satisfaction.

Does the optimization emphasize further understanding of the platform(if applicable)?

Absolutely. Pipelining requires a specific arrangement of instructions in order not to reset the pipeline. Highly parallel machines require rearrangement and communication that sometimes depend on the architecture or the networking of the cluster.

Is the optimization abstractable?

there are patterns for optimization, so in this sense yes, it can be abstracted. In terms of code, I doubt it, unless you delegate some optimizations to the compiler through auto-detection or pragmas.

How does the optimization influence design?

potentially, a lot, but if you have a good design, optimization tends to be hidden (simple example, replacing a Linked List with a Hash, or performing a do-loop in fortran column-wise instead of row-wise. In some cases however, a better design can have better performance (such as the case of the flyweight pattern).

Are "general solutions" the better choice instead of specific solutions for a problem because the specific solution is an optimization?

Not really. With general solution I assume you talk about general approaches such as a well-known design pattern. If you find out that you need a change in the pattern to satisfy your needs, that's not an optimization. It's a design change aimed at your specific problem. Optimization is aimed at improving performance. In some cases, you change the design to accommodate performance, so in this case the design change is also an optimization for performance, which can either reduce or increase maintainability, depending if the new design is more complex or not. An overdesigned system can also have performance problems.

That said, optimization is a case-by-case thing. You know the art, and you apply it to your specific problem. I'm not a great code-optimizer, but I am a good refactorer and the step is rather short.

Answer 6

A premature optimisation is one that was done too soon to guarantee an optimisation.

This is different to a bad optimisation:

1. Maybe that something really does speed up an important piece of code isn't worth some down-side, even if it was applied after profiling and user-experience demonstrated its value - in which case it is bad, but not premature.

2. On the other hand, maybe something done prematurely actually turns out to be just what was needed - in which case it was good, even though it was premature. Generally people who are guilty of premature optimisation will do this a lot, it's just that they'll balance it by doing stuff that makes things worse even more frequently.

Premature also doesn't mean early, just too early.

If you're designing an application that involves use of communication between two agents, and there is a way to either build a caching mechanism into the communication, or to build on one in an existing communication system (e.g. if you use HTTP), then this caching is not premature, unless the responses won't actually be cacheable (in which case it's premature as it's pointless). Such a fundamental design decision based on analysis of the problem (but not profiling of actual code - the code hasn't been written) made for purposes of efficiency can be the difference between feasibilty and infeasibilty.

Premature doesn't mean going for the option that seems most likely to be efficient given seemingly equivalent choices. You have to go for one of the options after all, so the likely efficiency is one of the factors you should weigh up. This is a case where intuition does have some value: (A) you don't yet have enough data to make an informed decision purely on the facts, (B) some of the other factors you are weighing up are intuitive also (those that affect how readable the code is; measuring it beyond just seeing how readable it is to you is only useful in a few cases, and again you can't measure the readability of something that hasn't been written, and finally it can only be measured statistically so if you're the main dev your opinion matters more than a statistically valid sample of devs). Move too far away from an option just because you fear being accused of premature optimisation, and you're just prematurely optimising for a different feature.

Nor does premature mean a small optimisation. If you can make a small improvement with no downside, go for it. Indeed, when Knuth said "premature optimisation is the root of all evil" he actually brings it up while defending taking the effort of working to gain small efficiency gains:

The improvement in speed from Example 2 to Example 2a is only about 12%, and many people would pronounce that insignificant. 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. 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 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 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. 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. —Knuth, Donald. "Structured Programming with go to Statements", Stanford, 1974

Premature is when it is simply too early to know whether something you are doing, with efficiency (whether in speed, memory, resource use, or a combination of these) in mind will actually produce the benefits intended and not also bring about other lacks and indeed that they won't actually harm the efficiency in the area they are seeking to be efficient in (a classic in the .NET world is people, often acting out of an emotional desire for control, seeing the GC as their enemy and working to "improve the efficiency" of garbage collection, and making it less efficient perhaps 95% or more of the time).

That's premature because it is, well, premature - too early.