10

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

20

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

7

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

4

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.

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.

1

I'll try to describe how I look upon the development process with respect to performance and (not always) premature optimization. Also, make sure you have the complete 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 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.

(Donald Knuth)

Yet attempts at optimization "after the fact" i e after the system development has completed are very costly and should not be justified. It's like building a new aircraft and a few days before the first test flight realizing it's too heavy. After a period of frenzy trying to make the plane lighter it is able to get off the ground, but for any sort of practical use a total redesign is necessary. We can laugh at the thought but this scenario is commonplace with computer systems.

To me it's very much about project organization.

All too many projects are unconcerned with good response times being necessary for the user productivity/experience. Lip service will be paid to the concept of a "well-performing" or "high-performance" system. Many will assume that "the machines are so fast that that won't be a problem" or "if performance tests show that we have a problem we'll fix it then." In such organizations optimizations are almost always premature. Anyone concerned with performance will be put in his place or even reprimanded for just trying to quantify it. "We'll do it ... later." We'll turn the steering wheel after we've gone off the cliff.

So you've finally completed the system but performance testing indicates that you'll have response times of twenty-three seconds instead of "no more than three." So you do optimizations and lowering by a third is a reasonable goal (at least the first time you do it) but even then we're still talking about fifteen seconds rather than "no more than three". So now you have to go your customer and explain why his server hardware is going to cost eight times and the upgraded internet connection three times as much as you'd led him to believe. "Actually the system is better than we originally planned" - except no one will want to use it.

To sum it up premature optimization is NOT the root of all evil, especially if we're talking SW development. There are plenty of more worthy candidates to consider first: poor planning, poor guidelines, poor leadership, indifferent developers, poor follow-up, timid project management and so on.

Mark Twain's quote "everyone talks about the weather but no one does anything about it" is very apt in that many developers talk performance and yet do nothing about it - except perhaps to make it less achievable. In fact, a great deal can be done from the very start of a project to assure and later to achieve good (if not stellar) performance.

Relatively speaking few projects will be organized such that performance has a reasonable chance to be attained:

Optimization begins at the drawing board when you think through how the program is supposed to work and what performance it needs to attain. Performance is often called a non-functional requirement tested with non-functional testing but I disagree. BTW, doesn't that sound horrible - "non-functional"? It's as if it's destined never to be. I claim that performance in the form of response time can make or break a system. What use is the greatest system on earth if the user tires from waiting thirty seconds or more for a response? So bring in performance at the very start and let it go head to head with the system's other requirements.

At the planning stage you should have identified some critical areas where you do not know if or how adequate performance can be achieved. Then you experiment with different solutions and time them using rdtsc. A typical problem area is SQL-databases where many designers have "a by the book" approach rather than a practical one. This may result in unnecessarily many tables.

So now you know how to move forward through the critical areas. Now you set up guidelines. In a C/S-system the client should have real capabilities. Too many Clients send too detailed requests to the server, thereby overloading it. Or expect the server to order the data because the client developers are too ignorant to see the performance impact and/or too lazy to implement ordering in the client: "why should I, the server already has that functionality? Should I implement it again - that's wasting resources!" Forbid the clients to formulate SQL statements directly to the server. You might also want to integrate timing at the functionality level into the apps themselves (using rdtsc on x86 for example).

So now development starts. As part of the development guidelines you have performance requirements such as that no client-serving functionality can consume more than 20 (or 5 or whatever) ms of server execution time. Any software exceeding that runs the risk of being rejected. Your guidelines may also contain code constructs to be avoided as well as those to use. Guidelines to keep SOAP data size under control if frameworks are being used.

Since you have timing in place in the apps you will be able to continuously monitor their processing efficiency during the development process. Certain functionality will execute too slowly and this is treated as a bug which will be prioritized and eventually corrected. Yes, "corrected" just like a bug - it is a bug!

In the end you will performance test your apps. If the previous steps have been in place and enforced the tests will just acknowledge that you have the performance you planned for all along.

So now you're "faced with" the luxury issue of having a product that performs the way it should with planned-for and achieved response times. You may opt for "shooting for the moon" i e lowering the response times to further enhance the end-user's experience. A typical and achievable goal is lowering them by a third from say 1.5 to 1 second. To do this you use the built-in timing to identify the sequences that matter, write bug reports and then correct them.

Why the "don't-optimizers" you mention in your question are so vocal (why not "rabid?") we can only speculate about. I'll offer a few suggestions: they may have tried it themselves but were unsuccessful (lack of strategy, lack of skills, thought it was boring). They may be under the impression that any source code (good as well as bad) can be translated by the compiler into good and fast code or executed quickly by the interpreter. This is not true. Just as it is possible to write an app which kills even the most capable hardware it is also possible to write one which makes the most efficient use of it. The don't-optimizers will typically pepper their responses with words like always, never, waste of time, stupid, brain-dead etc. That they feel they have something worthwhile to say without really knowing the different issues involved is, well, embarassing. But I guess that if you don't know what you're talking about then you can always act as if you do.

0

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.

0

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.