Saturday, August 13 2011
Donald Knuth famously said that Premature Optimization is the root of all evil. People incant it as a retort to pretty much any and all commentary on runtime performance, grossly misrepresenting or misinterpreting Knuth's original intention.
When is it a mature time to start to consider performance, however?
Most will say the time to optimize is once you're fairly well along in development: Hook a profiler up and find the low hanging fruit, achieving most of what you would have achieved if you focused intently on performance all along. This is the common wisdom.
After many years and many projects, I must vigorously disagree. It seldom turns out like that.
Here's the function runtimes of an idealized hypothetical program, written with performance as a driving consideration.
When we fire up our profiler on our "no premature optimization!" project, we expect to be confronted by something like this.
It never actually happens that way. Ever. When performance wasn't a consideration from day one, inefficiency becomes endemic, corrupting every square mibbibyte of the project. Why not iterate a giant array instead of using hashes? Why not use LINQ everywhere, repeatedly and inefficiently filtering a massively excessive superset of the needed data?
Most of the time our profile report looks more like the following.
It is devastatingly common: If performance doesn't matter, it really won't matter and it is seldom something that you can fix by a few updates in a single critical path function. It infects everything. Moore's law isn't there to save you either -- the speed of a single core has barely improved in years. Just as nine women can't produce a baby in one month, unless you've put down on parallelization, the single delivery performance is limited by that sloth. The fastest render time of a SugarCRM PHP page has a lower bound in the >100ms range, even if running on the fastest computer in the world. In the web app world this traditionally hasn't really mattered — people just became accustomed to every interaction taking seconds — but it has become a serious competitive advantage of a few offerings. I love Rdio*, yet if a competitor offered a solution that didn't have the second long pauses between every interaction (just navigating between pages), I would seriously consider switching.
Just as you can't add quality to your code just before shipping, seldom can you significantly improve performance without dramatic rewriting. In the same way that you can't easily parallelize an application that was't written as such in the first place. These are principal considerations.
I have little more to add over what I said four years ago on the topic of premature optimization. People have broadened Knuth's intention to the point of absurdity. When people talk about premature optimization, seldom is the context that intended by Knuth.
Update: A torrent of readers and my meager server's CPU usage sits at a constant <1%. Hardly miraculous — it should be the norm — but compare it to the countless sites that fall over when they receive any attention at all. When I built this trivial blog engine, largely for a laugh, efficiency was a principal consideration right at the outset, and was an architectural concern with every decision. This is actually a mostly unrelated aside (caching happens to be the easiest thing to layer overtop of a terrible solution, so it doesn't really follow with this post. It is more probably a counterpoint than a proof), but I had to take the opportunity to encourage everyone to be prepared to go to the frontpage of various social news sites. It is bizarre to endlessly see "too many database connections" when browsing the top links collections. That is an issue that we've known the solution to for a decade and a half.
* - Rdio is a great service, but I had to take a moment to point and laugh at their "native" application that is now available. It, they say, frees you from the browser. It does this by giving you a ClickOnce .NET application that needs to be updated seemingly every time I launch it. In return for the constant updates, it offers you an identical experience to the web application, only using far more resources (it regularly consumes 300MB+) and actually seeming to offer a slower interface. Not sure what drove that move, but it was very poorly conceived.
Very well said, and yes, it's very true as well.
Paweł Gościcki @ 8/13/2011 2:22:46 AM
It might be worth discussing Knuth’s intended context, for completeness’ sake.
As my own two cents, one should worry about the performance of the algorithms they select early on; i.e. if most interactions with a structure are by key, maybe use a hash table or an appropriate tree instead of crawling over a linked list. On the other hand, one shouldn’t worry about line-by-line optimization early on; it’s likely to be unnecessary.
At the same time, performance CAN be important in non-traditional areas (as you describe very nicely in your post), and so perhaps another lesson to take from this is “profile early, profile often”?
As my own two cents, one should worry about the performance of the algorithms they select early on; i.e. if most interactions with a structure are by key, maybe use a hash table or an appropriate tree instead of crawling over a linked list. On the other hand, one shouldn’t worry about line-by-line optimization early on; it’s likely to be unnecessary.
At the same time, performance CAN be important in non-traditional areas (as you describe very nicely in your post), and so perhaps another lesson to take from this is “profile early, profile often”?
Rob Rix @ 8/13/2011 10:31:11 AM
Of course, it would help if I read the article you linked to. A thorough discussion, and well-written; my apologies :)
Rob Rix @ 8/13/2011 10:32:28 AM
I agree and would like to even clarify further, the only way to tell if something is *premature* is by measurability. If while producing a system you are doing constant performance tests you will find out what *needs* to be optimised by empirical data. Anything else is indeed premature. Now also having experienced folk around to point out the differences when the system will be in an operational environment also helps - even empirical data requires critical thinking :-)
No trite incantation ever replaces wisdom and experience in technology, however Mr Knuth did pretty much hit the nail on the head. The problem as you highlight is definitely *how* someone decides what is premature.
Thanks for the article!
No trite incantation ever replaces wisdom and experience in technology, however Mr Knuth did pretty much hit the nail on the head. The problem as you highlight is definitely *how* someone decides what is premature.
Thanks for the article!
Neil Ellis @ 8/13/2011 10:45:06 AM
No, not well said, and no it's not very true.
That is a very stupid way of looking at it as it goes to the point that you actually expect people NOT to write good code that executes fast.
If you keep your code clean, have tests and try to adhere to best practices you will have a VERY easy time fixing those bottlenecks regardless of how your first profiling looks like.
That is a very stupid way of looking at it as it goes to the point that you actually expect people NOT to write good code that executes fast.
If you keep your code clean, have tests and try to adhere to best practices you will have a VERY easy time fixing those bottlenecks regardless of how your first profiling looks like.
Seivan Heidari @ 8/13/2011 11:11:02 AM
"no premature optimization" is completely different from "performance wasn't a consideration".
Robert @ 8/13/2011 11:14:16 AM
You are absolutely right. The whole project can have non-optimal architecture. This can't be corrected easily.
So, I think there are 2 types of optimizations:
1) High-level — the optimizations influencing large parts of the project, that do not impact code readability and can't be added easily. These optimizations often are not called optimizations, but clever architecture solutions.
2) Low-level optimizations — they impact code readability, but can be added easily when needed.
I think Don Knuth ment the second type of optimizations.
So, I think there are 2 types of optimizations:
1) High-level — the optimizations influencing large parts of the project, that do not impact code readability and can't be added easily. These optimizations often are not called optimizations, but clever architecture solutions.
2) Low-level optimizations — they impact code readability, but can be added easily when needed.
I think Don Knuth ment the second type of optimizations.
SAn @ 8/13/2011 11:45:03 AM
Well there was a topic like that on programmers.stackexchange.com. And it seems to me that good implementation is not optimization.
"Why not iterate a giant array instead of using hashes?"
If you choose to iterate a giant array there is something wrong to begin with. But if you are already using hashes, optimizations like limiting the amount of data you save to your hash array to a bare minimum, would seem pretty much useless. In my opinion, optimization of a bad implementation is never good, but good implementation of something shouldn't be considered optimization.
"Why not iterate a giant array instead of using hashes?"
If you choose to iterate a giant array there is something wrong to begin with. But if you are already using hashes, optimizations like limiting the amount of data you save to your hash array to a bare minimum, would seem pretty much useless. In my opinion, optimization of a bad implementation is never good, but good implementation of something shouldn't be considered optimization.
zidar @ 8/13/2011 11:56:54 AM
Well, there is optimization and there is properly written code. What you describe as lack of "consideration" is probably just somebody being unprofessional.
Misha @ 8/13/2011 12:07:05 PM
It seems like every week someone writes this article. To me it's a blatant straw-man argument. What you are saying is that there are developers out there who, if you say "don't focus too much on performance", would regularly use the worst possible algorithms and data structures, but if you said "performance is important", would do everything properly.
I don't buy this. I think that if you find something stupid like iterating through a big array to find something, instead of hashing or proper search, then it isn't because the programmer was thinking "Knuth said don't prematurely optimize", it's because the programmer didn't know any better. There are good and bad ways to implement certain functionality, and a good programmer isn't going to choose a bad way because you said "don't focus too much on performance, we'll really tweak this later". Do the world a favour and fire any programmer that uses Knuth to justify making a really stupid implementation decision. Rdio might be better if they had done this (totally joking/musing here, I have no clue what the performance issue there is).
Average code written by a decent programmer should be at least somewhat challenging to optimize, hence Knuth's advice. If you read code that is trivial to optimize, then it was probably written by a shitty programmer who, even if you later said "ok, now it's time to optimize the code", wouldn't know where to start.
I don't buy this. I think that if you find something stupid like iterating through a big array to find something, instead of hashing or proper search, then it isn't because the programmer was thinking "Knuth said don't prematurely optimize", it's because the programmer didn't know any better. There are good and bad ways to implement certain functionality, and a good programmer isn't going to choose a bad way because you said "don't focus too much on performance, we'll really tweak this later". Do the world a favour and fire any programmer that uses Knuth to justify making a really stupid implementation decision. Rdio might be better if they had done this (totally joking/musing here, I have no clue what the performance issue there is).
Average code written by a decent programmer should be at least somewhat challenging to optimize, hence Knuth's advice. If you read code that is trivial to optimize, then it was probably written by a shitty programmer who, even if you later said "ok, now it's time to optimize the code", wouldn't know where to start.
Jordan Frank @ 8/13/2011 12:15:29 PM
i think you're mistakenly confusing premature-optimization-is-the-root-of-all-evil-supporters with optimization?-hashes?-algorithms?-wtf-u-want-dude?-it-workses! kind of developers
there *always* is more performant way to do stuff until we reach physical limit on processing information(there is one!) - and we won't reach it in gazillion years. so it's all about compromise between speed of development and speed of code.
there *always* is more performant way to do stuff until we reach physical limit on processing information(there is one!) - and we won't reach it in gazillion years. so it's all about compromise between speed of development and speed of code.
Max @ 8/13/2011 12:31:16 PM
This is an interesting point. One of the main disadvantages of premature optimization, though, is that many times, one is not even sure of what the target application looks like, and what features it will have. There is the danger spending time optimizing code which will be thrown away.
So, even if optimizing by making small changes is impossible, it might still be cheaper to rewrite the application with a focus on performance, once the feature set is stable, rather than optimizing all the experimental designs.
So, even if optimizing by making small changes is impossible, it might still be cheaper to rewrite the application with a focus on performance, once the feature set is stable, rather than optimizing all the experimental designs.
harsha @ 8/13/2011 12:36:47 PM
I think what one can take from this, is that it's important to plan about efficiency (meaning, use correct data structures, algorithm, and architecture organization), but not worry about minute details until later. By minute details, I mean those that can be changed in a short amount of time, and which usually don't affect performance much.
In essence, early optimization in the form of using the right algorithms and such is not evil, and in fact saves you countless hours down the line. Profiling, however, should go after you've done a good chunk of the code. No use in profiling your just-written core function because you want it to be fast for the future - what determines speed is the usage your application will give that function. So, for instance, no use adding a hash table instead of searching an array if, in practice, your function will be accessed very rarely, and the array isn't big.
These considerations one must take in the design stage, much before code is written. Starting a project with "int main() { ... " and then optimizing each time you write a function is the problem the "root of all evil" saying is taking about. Both design-stage architecture efficiency, and latter-stage profiling and benchmarking are useful, but you can't switch their places and expect gains (i.e. microbenchmarks after writing each/any line of code, or design changes after you've written most of your code).
I think your threading example is a good example of this sort of mindset - adding threading after you've written all your code is nigh impossible. If you want to take advantage of threading, it is much better to think about this in the design stage, because the changes to allow for threading are usually massive, whereas the changes to (say) precompute a few values of a function to speed up a rare use case, aren't. Thus, threading considerations go in the design stage, while precomputation of these seldom used values go in the profiling, test, and review stage.
In essence, early optimization in the form of using the right algorithms and such is not evil, and in fact saves you countless hours down the line. Profiling, however, should go after you've done a good chunk of the code. No use in profiling your just-written core function because you want it to be fast for the future - what determines speed is the usage your application will give that function. So, for instance, no use adding a hash table instead of searching an array if, in practice, your function will be accessed very rarely, and the array isn't big.
These considerations one must take in the design stage, much before code is written. Starting a project with "int main() { ... " and then optimizing each time you write a function is the problem the "root of all evil" saying is taking about. Both design-stage architecture efficiency, and latter-stage profiling and benchmarking are useful, but you can't switch their places and expect gains (i.e. microbenchmarks after writing each/any line of code, or design changes after you've written most of your code).
I think your threading example is a good example of this sort of mindset - adding threading after you've written all your code is nigh impossible. If you want to take advantage of threading, it is much better to think about this in the design stage, because the changes to allow for threading are usually massive, whereas the changes to (say) precompute a few values of a function to speed up a rare use case, aren't. Thus, threading considerations go in the design stage, while precomputation of these seldom used values go in the profiling, test, and review stage.
Federico Lebrón @ 8/13/2011 1:37:20 PM
So stop using C# and hiring the bozo programmers who use it.
C++ guy @ 8/13/2011 1:39:19 PM
All design, and that includes performance oriented aspects of design (and security too, btw) MUST be continuously refined by refactoring with a suite of automated unit tests in place. That's how you evolve software.
I agree that code can become a mess, from a performance standpoint as well as many other facets, but that's why we refactor.
I agree that code can become a mess, from a performance standpoint as well as many other facets, but that's why we refactor.
John Tangney @ 8/13/2011 1:41:19 PM
Knuth did not mean that one should not use the right algorithm for the job. He wouldn't have written volumes on the subject if he did. What he was talking about was "clever" programming, which obfuscates code in advance of any evidence that the cleverness was necessary.
Alan Yoder @ 8/13/2011 1:43:35 PM
Hi Jordan,
"To me it's a blatant straw-man argument."
That is not my intention. Nor is it intended to be an indictment of all who argue against excessive optimization. Nor does it excuse or legitimize excessive optimization.
Premature optimization most certainly exists, and it is a danger.
But I do think many projects have pushed too far in the opposite direction. The avoidance of performance as a critical project delivery is common, and the results are that it *will* suffer. Not in the choice of a single algorithm, but rather project death by a thousand suboptimal implementations. It accumulates.
"To me it's a blatant straw-man argument."
That is not my intention. Nor is it intended to be an indictment of all who argue against excessive optimization. Nor does it excuse or legitimize excessive optimization.
Premature optimization most certainly exists, and it is a danger.
But I do think many projects have pushed too far in the opposite direction. The avoidance of performance as a critical project delivery is common, and the results are that it *will* suffer. Not in the choice of a single algorithm, but rather project death by a thousand suboptimal implementations. It accumulates.
Dennis Forbes @ 8/13/2011 2:17:09 PM
Hi Alan,
"Knuth did not mean that one should not use the right algorithm for the job."
Yes of course. Knuth's original intention has perilously little to do with the common deferment to his authority. A prior commenter observed my use as a strawman, yet there is literally not a day that goes by that I don't see someone declaring the choice of foundational database technologies or platforms, basic architectural choices, and so on, as nothing but dangerous premature optimization. It is a dangerous trend.
"Knuth did not mean that one should not use the right algorithm for the job."
Yes of course. Knuth's original intention has perilously little to do with the common deferment to his authority. A prior commenter observed my use as a strawman, yet there is literally not a day that goes by that I don't see someone declaring the choice of foundational database technologies or platforms, basic architectural choices, and so on, as nothing but dangerous premature optimization. It is a dangerous trend.
Dennis Forbes @ 8/13/2011 2:21:55 PM
If you have a point to make it is negated by your juvenile neologism. Postmature is not a word, if you mean the opposite of "premature" take the time to choose a suitable word. It is anyone's guess what "a mature time to start to consider performance" means.
Alan Yoder and Jordan Frank are right. Your argument is a lazy strawman, the inefficiency of many projects is IMHO more due to unrealistic deadlines and insufficiently experienced staff, which prevent good system design and good implementation. We can only wish that these people were good enough to have heard of Knuth in the first place.
Knuth argued for knowing what you were doing before trying to optimise, the problem is that many managers and implementors have not been practicing long enough to really know what they are doing.
Alan Yoder and Jordan Frank are right. Your argument is a lazy strawman, the inefficiency of many projects is IMHO more due to unrealistic deadlines and insufficiently experienced staff, which prevent good system design and good implementation. We can only wish that these people were good enough to have heard of Knuth in the first place.
Knuth argued for knowing what you were doing before trying to optimise, the problem is that many managers and implementors have not been practicing long enough to really know what they are doing.
Ed @ 8/13/2011 2:48:21 PM
Hi Ed. Thanks for the comment.
"It is anyone's guess what "a mature time to start to consider performance" means."
I would be surprised if anyone but you took issue with the humorous play on words, or if anyone but you had difficulty understanding the point. It has been my experience, however, that when someone feels personally offended by something, even where personal offense isn't intended, they go for the crotch shot. So kudos to you.
"It is anyone's guess what "a mature time to start to consider performance" means."
I would be surprised if anyone but you took issue with the humorous play on words, or if anyone but you had difficulty understanding the point. It has been my experience, however, that when someone feels personally offended by something, even where personal offense isn't intended, they go for the crotch shot. So kudos to you.
Dennis Forbes @ 8/13/2011 2:53:14 PM
Interesting piece. But it's hard to see how good code can ever leave out the issue of scalability these days. The word "optimize" meant something radically different even a decade ago, in most cases having more to do with streamlining the efficiency of individual algorithms than with massive-use parallelization and concurrency issues.
Nowadays, if you aren't considering what will happen as it scales, you're not only writing unoptimized code -- you're writing broken code.
Optimization is kind of the last 10% by definition. So semantically at least, there's an argument to be made that the bar's been raised with the times as to the line between "unoptimized" and "fubar."
Nowadays, if you aren't considering what will happen as it scales, you're not only writing unoptimized code -- you're writing broken code.
Optimization is kind of the last 10% by definition. So semantically at least, there's an argument to be made that the bar's been raised with the times as to the line between "unoptimized" and "fubar."
Josh Strike @ 8/13/2011 3:50:48 PM
Well written, I completely agree :)
To give an example of a case where the programmer is NOT a shitty one and who probably would have made a decent product if he said from the beginning "performance is important": Eiffel.
It's a programming language invented by one of our professors and one goal was to be easy for beginners to learn. But there are also uses in the industry. Unfortunately, performance was appearantly not a goal during the implementation of the compiler, the standard library and the IDE. I'm not so sure who workerd on the code, but the aforementioned professer certainly did a large part of the work. So the people who implemented the stuff are mostly top-notch people who work and study at a renowned university and know their CS.
But because performance wasn't a target from the beginning on, Eiffel is horribly slow. And this not so much due to some big architectural mistakes (Eiffel is actually quite well tought-trough in this regard) but because of a lot of small unoptimized things that add up. To give an example: The method to get/remove the last element of a linked list actually has O(n) runtime because it iterates over the whole thing. The result is an IDE which performs a search-and-replace only marginally faster than a speedy coder.
TL;DR: There are actual real-word cases of this problem.
Cheers, Sam
(P.S.: The CSS of your blog prevents the resize of this textarea in Firefox. If you make it too big, part of it gets hidden without a chance to make it smaller again. Probably an "overflow: hidden" too much somewhere ;)
To give an example of a case where the programmer is NOT a shitty one and who probably would have made a decent product if he said from the beginning "performance is important": Eiffel.
It's a programming language invented by one of our professors and one goal was to be easy for beginners to learn. But there are also uses in the industry. Unfortunately, performance was appearantly not a goal during the implementation of the compiler, the standard library and the IDE. I'm not so sure who workerd on the code, but the aforementioned professer certainly did a large part of the work. So the people who implemented the stuff are mostly top-notch people who work and study at a renowned university and know their CS.
But because performance wasn't a target from the beginning on, Eiffel is horribly slow. And this not so much due to some big architectural mistakes (Eiffel is actually quite well tought-trough in this regard) but because of a lot of small unoptimized things that add up. To give an example: The method to get/remove the last element of a linked list actually has O(n) runtime because it iterates over the whole thing. The result is an IDE which performs a search-and-replace only marginally faster than a speedy coder.
TL;DR: There are actual real-word cases of this problem.
Cheers, Sam
(P.S.: The CSS of your blog prevents the resize of this textarea in Firefox. If you make it too big, part of it gets hidden without a chance to make it smaller again. Probably an "overflow: hidden" too much somewhere ;)
iliis @ 8/13/2011 4:29:18 PM
80-20 Rule.
vas @ 8/13/2011 5:06:19 PM
Basically, all suggestions about optimization have a merit in one or the other context.
The trick is that you need to know the context you are in.
My though process is about a decision while programming:
1. what do i expect how much it impacts the code base ( f.e.: a new method has small object-relational layer large impact.)
2. what performance problems do i expect
if the product of these to expectation is high - you should optimize early.
if it is low. optimize later.
The trick is that you need to know the context you are in.
My though process is about a decision while programming:
1. what do i expect how much it impacts the code base ( f.e.: a new method has small object-relational layer large impact.)
2. what performance problems do i expect
if the product of these to expectation is high - you should optimize early.
if it is low. optimize later.
JE @ 8/13/2011 5:19:20 PM
Nice article, that Ed guy totally missed the point btw. As an architect I constantly have my developers saying we don't have a performance problem yet so upfront architectural decisions concerning performance aren't necessary. I only need to refer them to our legacy projects that were built with performance as an after thought vs those and where performance was given some high level consideration upfront and they see the importance. As you point out an under performing design is so endemic throughout the code it almost always becomes impossible to maintain or even refactor out with a complete re-rewrite.
Mike @ 8/13/2011 5:22:45 PM
Amen. Your point is well articulated and very timely in the industry: the web 2.0 startup community spends tons of time waving their hands around in their air about premature optimization, making poor structural decisions from day one about their projects. The end result is products that are not only sluggish, but difficult to scale and reason about.
I think the culprit here is the reliance on very high level interpreted languages that are too far from the hardware to really produce an understandable performance profile, the common and incorrect assumption that you can scale just about anything "in the cloud," and the explosion of hard drive and RAM which leads people to enumerate way too much data just because the numbers sound reasonable.
Think twice when making architectural decisions in the early days of your software. More often then not you'll be living with your decisions for a long time to come.
I think the culprit here is the reliance on very high level interpreted languages that are too far from the hardware to really produce an understandable performance profile, the common and incorrect assumption that you can scale just about anything "in the cloud," and the explosion of hard drive and RAM which leads people to enumerate way too much data just because the numbers sound reasonable.
Think twice when making architectural decisions in the early days of your software. More often then not you'll be living with your decisions for a long time to come.
thomas lackner @ 8/13/2011 7:05:57 PM
Perhaps we should to pay more attention to identifying performance requirements? If code does not meet a customer's performance requirement then it is not working software. If such a requirement can be identified then an amount of time proportional to its value to the customer can be spent identifying and optimising the relevant code (or selecting a decent implementation in the first place).
Without any performance requirements, you're left with making an informed trade-off between readability, performance and implementation time. This is how a developer earns their money! The "premature optimisation" dictum reminds us that it's often very difficult to accurately predict the impact of the performance of a small portion on that of the system as a whole. Therefore we should be very wary of sacrificing readability and implementation time in favour of performance. However that's not to say that performance should be totally discounted.
Without any performance requirements, you're left with making an informed trade-off between readability, performance and implementation time. This is how a developer earns their money! The "premature optimisation" dictum reminds us that it's often very difficult to accurately predict the impact of the performance of a small portion on that of the system as a whole. Therefore we should be very wary of sacrificing readability and implementation time in favour of performance. However that's not to say that performance should be totally discounted.
Tom @ 8/14/2011 3:21:52 AM
I think you completely missed the point of Donald's quote. The point of the quote was pick your battles when you consider how to implement and architecture. It wasn't to completely drop any optimization and write shit code. If it is going to take a 6 months to do something 10x faster than doing it in 1 month. This is something that needs consideration. Seriously, if you don't understand this I'm quite confused on how you have managed to be lead software architect or any of your other qualifications.
Bick Black @ 8/14/2011 2:04:48 PM
I'm concerned that you read this entry yet still authored that comment, Bick Black. Did you rush to the comment box to add your wisdom?
The whole point of the entry is that people incant Knuth's name in error: They grossly misrepresent what he said. I couldn't have made that point more obvious.
The whole point of the entry is that people incant Knuth's name in error: They grossly misrepresent what he said. I couldn't have made that point more obvious.
Dennis Forbes @ 8/14/2011 2:10:42 PM
I think most of the disagreement over Knuth's intentions comes down to the word "optimization" being used with two different connotations:
1) ["good-design"-optimization] reducing time/space by a *non*-constant factor, e.g. O(n lg n) algorithm instead of an O(n^2).
2) ["knuthian"-optimization] := reducing time/space by a *constant* factor.
------------------------------------------------------------
I particularly like this quote (http://gcc.gnu.org/wiki/Speedup_areas):
"Basic rule #1: DO NOT ADD ALGORITHMS WITH QUADRATIC OR WORSE BEHAVIOR, EVER."
------------------------------------------------------------
1) ["good-design"-optimization] reducing time/space by a *non*-constant factor, e.g. O(n lg n) algorithm instead of an O(n^2).
2) ["knuthian"-optimization] := reducing time/space by a *constant* factor.
------------------------------------------------------------
I particularly like this quote (http://gcc.gnu.org/wiki/Speedup_areas):
"Basic rule #1: DO NOT ADD ALGORITHMS WITH QUADRATIC OR WORSE BEHAVIOR, EVER."
------------------------------------------------------------
asdf @ 8/14/2011 9:34:16 PM
when you talk about optimization, you have to differentiate between hardware optimization and algorithmic optimization. hardware optimization is a fools game, ace assembly coders like Michael Abrash will tell you that you can never predict how all the factors in the CPU pipeline interrelate and your predictions will almost always be wrong. however a programmer who is trained to use proper algorithms and data structures will always be making his code algorithmically optimized from the start. Programmers like Ken Thompson and Dennis Ritchie have their designs well planned out on the white board well before they type their first line of code. there is nothing wrong with benchmarking, profiling and testing code after its finished, but anyone who has to optimize their code as a seperate process to the original design show a programmer who does not know what they are doing and is fishing for superficial speed gains.
Brad @ 8/15/2011 10:49:08 AM
All design, and that includes performance oriented aspects of design (and security too, btw) MUST be continuously refined by refactoring with a suite of automated unit tests in place. That's how you evolve software.
I agree that code can become a mess, from a performance standpoint as well as many other facets, but that's why we refactor.
I agree that code can become a mess, from a performance standpoint as well as many other facets, but that's why we refactor.
John Tangney @ 8/17/2011 7:21:02 PM
For starters, it was C. A. R. Hoare who originally made the comment about premature optimization.
Secondly, I agree that system designs that inherently are not done with high performance as a goal become near impossible to alter beyond a point. However, I think that it is acceptable to have such a system now that I understand business dynamics much better than I used to do so a few years ago.
The reason is that there are other parameters of product building that we could optimize on: effort, time to market, etc. etc. As long as we have a system that will hold up until we are certain that the overall product that is being built is (economically) sustainable, we can have the sloppier set up. A redesign/rewrite at this point works. It certainly does appear (and actually also is) to be more painful than to do so from the first cut but if you believe in 3 things, it works out
* Optimizing the execution of software is always not the most important thing
* There is non-linear increase in effort to write great software v/s good enough
* Not every product succeeds, so there are other risks that we need to get over before the software becomes the major problem.
In light of this, I do find the comment on premature optimization very reasonable. All that it failed to point out was what the overall trade-offs are.
Secondly, I agree that system designs that inherently are not done with high performance as a goal become near impossible to alter beyond a point. However, I think that it is acceptable to have such a system now that I understand business dynamics much better than I used to do so a few years ago.
The reason is that there are other parameters of product building that we could optimize on: effort, time to market, etc. etc. As long as we have a system that will hold up until we are certain that the overall product that is being built is (economically) sustainable, we can have the sloppier set up. A redesign/rewrite at this point works. It certainly does appear (and actually also is) to be more painful than to do so from the first cut but if you believe in 3 things, it works out
* Optimizing the execution of software is always not the most important thing
* There is non-linear increase in effort to write great software v/s good enough
* Not every product succeeds, so there are other risks that we need to get over before the software becomes the major problem.
In light of this, I do find the comment on premature optimization very reasonable. All that it failed to point out was what the overall trade-offs are.
Arvind Jayaprakash @ 8/19/2011 11:13:50 AM
Name *:
Email Address:
(your email address is not displayed)
Website:
Comment *:
Email Address:
(your email address is not displayed)
Website:
Comment *:
About the Author
Dennis Forbes is a Toronto-based software architect. While focused primarily on the .NET and SQL Server worlds, Dennis frequently ventures outside of this comfort zone into game development and image processing. He has been published in several industry magazines, has been quoted in the Wall Street Journal and has been interviewed by NPR.He is a vice president and lead software architect at an innovative New York City hedge fund back-office services firm.
Dennis has been working on solutions for the financial, telecommunications, and power generation markets for over 15 years.
Jan 03 - What About Android Deactivations?
Nov 10 - Flash (SWF) Is Dead
Oct 25 - Tenom And the Intelligent Home
Oct 07 - The Canonization of Steve Jobs
Sep 29 - The Kindle Fire and Android
Sep 26 - You Are The Product. Get Over It.
Sep 25 - The iPhone's Incredible Halo-Effect
Aug 23 - GUIDs In Your Database
Aug 21 - Software Rules The Earth
Aug 15 - Google buys MMI
The Feed Bag
Oct 24 - Parenthood
Aug 29 - Best SSDs For The Money: August 2011
Jul 24 - The Cost of Patent Trolls
Jul 23 - Cinemagraphs
Jul 20 - Netflix Describes the Chaos Monkeys
Jul 19 - Apple Prints Their Own Money
Jul 08 - Good Database-Related Blog
Jun 23 - tewdew software blog
Jun 13 - Windows 8 Horrifies Devs
May 29 - nvidia demos Kal-El
May 13 - The Problem with HTML5 Audio
May 12 - Google's Unsavory Bullying
May 10 - Android 3.1 Platform