Is premature optimization really the root of all evil?

Question

A colleague of mine today committed a class called ThreadLocalFormat, which basically moved instances of Java Format classes into a thread local, since they are not thread safe and "relatively expensive" to create. I wrote a quick test and calculated that I could create 200,000 instances a second, asked him was he creating that many, to which he answered "nowhere near that many". He's a great programmer and everyone on the team is highly skilled so we have no problem understanding the resulting code, but it was clearly a case of optimizing where there is no real need. He backed the code out at my request. What do you think? Is this a case of "premature optimization" and how bad is it really?

Answer 1

It's important to keep in mind the full quote (see below):

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

What this means is that, in the absence of measured performance issues you shouldn't optimize because you think you will get a performance gain. There are obvious optimizations (like not doing string concatenation inside a tight loop) but anything that isn't a trivially clear optimization should be avoided until it can be measured.

The biggest problems with "premature optimization" are that it can introduce unexpected bugs and can be a huge time waster.

---

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

Answer 2

Premature micro optimizations are the root of all evil, because micro optimizations leave out context. They almost never behave the way they are expected.

What are some good early optimizations in the order of importance:

• Architectural optimizations (application structure, the way it is componentized and layered)
• Data flow optimizations (inside and outside of application)

Some mid development cycle optimizations:

• Data structures, introduce new data structures that have better performance or lower overhead if necessary
• Algorithms (now its a good time to start deciding between quicksort3 and heapsort ;-) )

Some end development cycle optimizations

• Finding code hotpots (tight loops, that should be optimized)
• Profiling based optimizations of computational parts of the code
• Micro optimizations can be done now as they are done in the context of the application and their impact can be measured correctly.

Not all early optimizations are evil, micro optimizations are evil if done at the wrong time in the development life cycle, as they can negatively affect architecture, can negatively affect initial productivity, can be irrelevant performance wise or even have a detrimental effect at the end of development due to different environment conditions.

If performance is of concern (and always should be) always think big. Performance is a bigger picture and not about things like: should I use int or long?. Go for Top Down when working with performance instead of Bottom Up.

Answer 3

optimization without first measuring is almost always premature.

I believe that's true in this case, and true in the general case as well.

Answer 4

Optimization is "evil" if it causes:

• less clear code
• significantly more code
• less secure code
• wasted programmer time

In your case, it seems like a little programmer time was already spent, the code was not too complex (a guess from your comment that everyone on the team would be able to understand), and the code is a bit more future proof (being thread safe now, if I understood your description). Sounds like only a little evil. :)

Answer 5

I'm surprised that this question is 5 years old, and yet nobody has posted more of what Knuth had to say than a couple of sentences. The couple of paragraphs surrounding the famous quote explain it quite well. The paper that is being quoted is called "Structured Programming with go to Statements", and while it's nearly 40 years old, is about a controversy and a software movement that both no longer exist, and has examples in programming languages that many people have never heard of, a surprisingly large amount of what it said still applies.

Here's a larger quote (from page 8 of the pdf, page 268 in the original):

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 penny-wise-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 one-shot 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.

Another good bit from the previous page:

My own programming style has of course changed during the last decade, according to the trends of the times (e.g., I'm not quite so tricky anymore, and I use fewer go to's), but the major change in my style has been due to this inner loop phenomenon. I now look with an extremely jaundiced eye at every operation in a critical inner loop, seeking to modify my program and data structure (as in the change from Example 1 to Example 2) so that some of the operations can be eliminated. The reasons for this approach are that: a) it doesn't take long, since the inner loop is short; b) the payoff is real; and c) I can then afford to be less efficient in the other parts of my programs, which therefore are more readable and more easily written and debugged.

Answer 6

I've often seen this quote used to justify obviously bad code or code that, while its performance has not been measured, could probably be made faster quite easily, without increasing code size or compromising its readability.

In general, I do think early micro-optimizations may be a bad idea. However, macro-optimizations (things like choosing an O(log N) algorithm instead of O(N^2)) are often worthwhile and should be done early, since it may be wasteful to write a O(N^2) algorithm and then throw it away completely in favor of a O(log N) approach.

Note the words may be: if the O(N^2) algorithm is simple and easy to write, you can throw it away later without much guilt if it turns out to be too slow. But if both algorithms are similarly complex, or if the expected workload is so large that you already know you'll need the faster one, then optimizing early is a sound engineering decision that will reduce your total workload in the long run.

Thus, in general, I think the right approach is to find out what your options are before you start writing code, and consciously choose the best algorithm for your situation. Most importantly, the phrase "premature optimization is the root of all evil" is no excuse for ignorance. Career developers should have a general idea of how much common operations cost; they should know, for example,

• that strings cost more than numbers
• that dynamic languages are much slower than statically-typed languages
• the advantages of array/vector lists over linked lists, and vice versa
• when to use a hashtable, when to use a sorted map, and when to use a heap
• that (if they work with mobile devices) "double" and "int" have similar performance on desktops (FP may even be faster) but "double" may be a hundred times slower on low-end mobile devices without FPUs;
• that transferring data over the internet is slower than HDD access, HDDs are vastly slower than RAM, RAM is much slower than L1 cache and registers, and internet operations may block indefinitely (and fail at any time).

And developers should be familiar with a toolbox of data structures and algorithms so that they can easily use the right tools for the job.

Having plenty of knowledge and a personal toolbox enables you to optimize almost effortlessly. Putting a lot of effort into an optimization that might be unnecessary is evil (and I admit to falling into that trap more than once). But when optimization is as easy as picking a set/hashtable instead of an array, or storing a list of numbers in double[] instead of string[], then why not? I might be disagreeing with Knuth here, I'm not sure, but I think he was talking about low-level optimization whereas I am talking about high-level optimization.

Remember, that quote is originally from 1974. In 1974 computers were slow and computing power was expensive, which gave some developers a tendency to overoptimize, line-by-line. I think that's what Knuth was pushing against. He wasn't saying "don't worry about performance at all", because in 1974 that would just be crazy talk. Knuth was explaining how to optimize; in short, one should focus only on the bottlenecks, and before you do that you must perform measurements to find the bottlenecks.

Note that you can't find the bottlenecks until you have written a program to measure, which means that some performance decisions must be made before anything exists to measure. Sometimes these decisions are difficult to change if you get them wrong (for example, if you choose to write your software in JavaScript instead of C#/Java, your code will have a much lower performance ceiling, which might be fine or frustrating depending on whether you hit that ceiling and how hard it is to overcome it when it is reached). For this reason, it's good to have a general idea of what things cost so you can make reasonable decisions when no hard data is available.

How early to optimize, and how much to worry about performance, depends on the job. When writing scripts that you'll only run a few times, worrying about performance at all is usually a complete waste of time. But if you work for Microsoft or Oracle and you're working on a library that thousands of other developers are going to use in thousands of different ways, it may pay to optimize the hell out of it, so that you can cover all the diverse use cases efficiently. Even so, the need for performance must always be balanced against the need for readability, maintainability, elegance, extensibility, and so on.

Answer 7

Personally, as covered in a previous thread, I don't believe early optimization is bad in situations where you know you will hit performance issues. For example, I write surface modelling and analysis software, where I regularly deal with tens of millions of entities. Planning for optimal performance at design stage is far superior than late optimization of a weak design.

Another thing to consider is how your application will scale in the future. If you consider that your code will have a long life, optimizing performance at design stage is also a good idea.

In my experience, late optimization provides meagre rewards at a high price. Optimizing at design stage, through algorithm selection and tweaking, is way better. Depending on a profiler to understand how your code works is not a great way of getting high performance code, you should know this beforehand.

Answer 8

In fact I learned that premature non-optimization is more often the root of all evil.

When people write software it will initially have problems, like instability, limited features, bad usability and bad performance. All of these usually get fixed, when the software matures.

All of these, except performance. Noone seems to care about performance. The reason is simple: if a software crashes, someone will fix the bug and that's it, if a feature is missing, someone will implement it and done, if the software has bad performance it is in many cases not due to missing microoptimization, but due to bad design and no one is going to touch the design of the software. EVER.

Look at Bochs. It's slow as hell. Will it ever get faster? Maybe, but only in the range of a few percent. It will never get performance comparable to virtualization software like VMWare or VBox or even QEMU. Because it's slow by design!

If the problem of a software is that it is slow, then because it is VERY slow and this can only be fixed by improving the performance by a multitude. +10% will simply not make a slow software fast. And you will usually not get more than 10% by later optimizations.

So if performance is ANY important for your software, you should take that into account from the beginning on, when designing it, instead of thinking "oh yes, it's slow, but we can improve that later". Because you can't!

I know that does not really fit to your specific case, but it answers the general question "Is premature optimization really the root of all evil?" - with a clear NO.

Every optimization, like any feature, etc. has to be designed carefully and implemented carefully. And that includes a proper evaluation of cost and benefit. Do not optimize an algorithm to save a few cycles here and there, when it doesn't create a measurable performance gain.

Just as an example: you can improve a function's performance by inlining it, possibly saving a handful of cycles, but at the same time you probably increase the size of your executable, increasing the chances of TLB and cache misses costing thousands of cycles or even paging operations, which will kill performance entirely. If you don't understand these things, your "optimization" can turn out bad.

Stupid optimization is more evil than "premature" optimization, yet both are still better than premature non-optimization.

Answer 9

From a different perspective, it is my experience that most programmers/developers do not plan for success and the "prototype" is almost always becomes Release 1.0. I have first hand experience with 4 separate original products in which the classy, sexy, and highly functional front-end (basically the UI) resulted in wide-spread user adoption and enthusiasm. In each of these products, performance problems began to creep in within relatively short times (1 to 2 years) particularly as larger, more demanding customers, began to adopt the product. Very soon performance dominated the issues list, although new feature development dominated management's priority list. Customers became more and more frustrated as each release added new features which sounded great but were almost inaccessible due to performance issues.

So, very fundamental design and implementation flaws that were of little or no concern in the "proto-type" became major stumbling blocks to long-term success of the products (and the companies).

Your customer demo may look and perform great on your laptop with XML DOMs, SQL Express, and lots of client-side cached data. The production system will probably crash a burn if you are successful.

In 1976 we were still debating the optimal ways of calculating a square root or sorting a large array and Don Knuth's adage was directed at the mistake of focusing on optimizing that sort of low level routine early in the design process rather than focusing on solving the problem and then optimizing localized regions of code.

When one repeats the adage as an excuse for not writing efficient code (C++, VB, T-SQL or otherwise), or for not properly designing the data store, or for not considering the net work architecture, then IMO they are just demonstrating a very shallow understanding of the real nature of our work. Ray

Answer 10

There are two problems with PO: firstly, the development time being used for non-essential work, which could be used writing more features or fixing more bugs, and secondly, the false sense of security that the code is running efficiently. PO often involves optimising code that isn't going to be the bottle-neck, while not noticing the code that will. The "premature" bit means that the optimisation is done before a problem is identified using proper measurements.

So basically, yes, this sounds like premature optimisation, but I wouldn't necessarily back it out unless it introduces bugs - after all, it's been optimised now(!)

Answer 11

I believe it's what Mike Cohn calls 'gold-plating' the code - i.e. spending time on things which could be nice but are not necessary.

He advised against it.

P.S. 'Gold-plating' could be bells-and-whistles kind of functionality spec-wise. When you look at the code it takes form of unnecessary optimisation, 'future-proofed' classes etc.

Answer 12

Since there is no problem understanding the code, then this case could be considered as an exception.

But in general optimization leads to less readable and less understandable code and should be applied only when necessary. A simple example - if you know that you have to sort only a couple of elements - then use BubbleSort. But if you suspect that the elements could increase and you don't know how much, then optimizing with QuickSort (for example) is not evil, but a must. And this should be considered during the design of the program.

Answer 13

I've found that the problem with premature optimization mostly happens when re-writing existing code to be faster. I can see how it could be a problem to write some convoluted optimization in the first place, but mostly I see premature optimization rearing its ugly head in fixing what ain't (known to be) broke.

And the worst example of this is whenever I see someone re-implementing features from a standard library. That is a major red flag. Like, I once saw someone implement custom routines for string manipulation because he was concerned that the built-in commands were too slow.

This results in code that is harder to understand (bad) and burning a lot of time on work that probably isn't useful (bad).

Answer 14

Most of those who adhere to "PMO" (the partial quote, that is) say that optimizations must be based on measurements and measurements cannot be performed until at the very end.

It is also my experience from large systems development that performance testing is done at the very end, as development nears completion.

If we were to follow the "advice" of these people all systems would be excruciatingly slow. They would be expensive as well because their hardware needs are much greater than originally envisaged.

I have long advocated doing performance tests at regular intervals in the development process: it will indicate both the presence of new code (where previously there was none) and the state of existing code.

• The performance of newly-implemented code may be compared with that of existing, similar code. A "feel" for the new code's performance will be established over time.
• If existing code suddenly goes haywire you understand that something has happened to it and you can investigate it immediately, not (much) later when it affects the entire system.

Another pet idea is to instrument software at the function block level. As the system executes it gathers information on execution times for the function blocks. When a system upgrade is performed it can be determined what function blocks perform as they did in the earlier release and those that have deteriorated. On a software's screen the performance data could be accessed from the help menu.

Check out this excellent piece on what PMO might or might no mean.

Answer 15

I suppose it depends on how you define "premature". Making low-level functionality quick when you're writing is not inherently evil. I think that's a misunderstanding of the quote. Sometimes I think that quote could do with some more qualification. I'd echo m_pGladiator's comments about readability though.

Answer 16

The answer is: it depends. I'll argue that efficiency is a big deal for certain types of work, such as complex database queries. In many other cases the computer is spending most of its time waiting for user input so optimising most code is at best a waste of effort and at worst counterproductive.

In some cases you can design for efficiency or performance (perceived or real) - selecting an appropriate algorithm or designing a user interface so certain expensive operations happen in the background for example. In many cases, profiling or other operations to determine hotspots will get you a 10/90 benefit.

One example of this I can describe is the data model I once did for a court case management system which had about 560 tables in it. It started out normalised ('beautifully normalised' as the consultant from a certain big-5 firm put it) and we only had to put four items of denormalised data in it:

• One materialised view to support a search screen

• One trigger-maintained table to support another search screen that could not be done with a materialised view.

• One denormalised reporting table (this only existed because we had to take on some throughput reports when a data warehouse project got canned)

• One trigger-maintained table for an interface that had to search for the most recent of quite a large number of disparate events within the system.

This was (at the time) the largest J2EE project in Australasia - well over 100 years of developer time - and it had 4 denormalised items in the database schema, one of which didn't really belong there at all.

Answer 17

Premature optimization is not the root of ALL evil, that's for sure. There are however drawbacks to it:

• you invest more time during development
• you invest more time testing it
• you invest more time fixing bugs that otherwise wouldn't be there

Instead of premature optimization, one could do early visibility tests, to see if there's an actual need for better optimization.