The Sad Reality of Post-Mature Optimization(blog.yafla.com)
blog.yafla.com
The Sad Reality of Post-Mature Optimization
http://blog.yafla.com/The_Sad_Reality_of_PostMature_Optimization/
35 comments
http://the-witness.net/news/2011/06/how-to-program-independe...
This was posted on HN recently. Skip to slide 18. In it, the guy talked about premature optimization, curiously, of the same thing: linear iteration over an array vs using a hash implementation.
His example was that in his youth, he was on the Doom forums, and he was doing mods, and took a look at the code that loaded the different asset files. And he was abhorred that the code used an array to linearly iterate over to find the asset to load. He started complaining on the newsgroups, and then Doom guys said you don't know what you're talking about, etc.
In this case, it was where that code just didn't matter in terms of run time, because the order of magnitude difference in looking up an asset and actually loading the asset was huge, and it just didn't matter. And because they used a dumb implementation, they could optimize for developer productivity and go on to code that mattered, like the rendering.
That said, I think the thing to keep in mind is, which parts of your problem space is of the core importance, and keep an eye on difference of order of magnitude in the different solutions you were thinking about implementing
This was posted on HN recently. Skip to slide 18. In it, the guy talked about premature optimization, curiously, of the same thing: linear iteration over an array vs using a hash implementation.
His example was that in his youth, he was on the Doom forums, and he was doing mods, and took a look at the code that loaded the different asset files. And he was abhorred that the code used an array to linearly iterate over to find the asset to load. He started complaining on the newsgroups, and then Doom guys said you don't know what you're talking about, etc.
In this case, it was where that code just didn't matter in terms of run time, because the order of magnitude difference in looking up an asset and actually loading the asset was huge, and it just didn't matter. And because they used a dumb implementation, they could optimize for developer productivity and go on to code that mattered, like the rendering.
That said, I think the thing to keep in mind is, which parts of your problem space is of the core importance, and keep an eye on difference of order of magnitude in the different solutions you were thinking about implementing
I listened to his whole talk, and it was quite eye-opening.
And sure enough, just the other night, I ran into a really hard to find memory leak in some new code. At that point, I regretted tailoring a couple of strictly speaking, unecessary object as helpers, and just replaced them with arrays. It was then somewhat easier to nail down my memory leak.
Point being, that as soon as you need complete comprehension of some code, whether for performance tuning, or debugging, any reduction in the complexity of the code can pay massive dividends.
And sure enough, just the other night, I ran into a really hard to find memory leak in some new code. At that point, I regretted tailoring a couple of strictly speaking, unecessary object as helpers, and just replaced them with arrays. It was then somewhat easier to nail down my memory leak.
Point being, that as soon as you need complete comprehension of some code, whether for performance tuning, or debugging, any reduction in the complexity of the code can pay massive dividends.
Note: "the guy" is Jonathan Blow, who created Braid.
Well,
The easy, general lesson is you need optimize "in the large" from day one, meaning having architecture that won't bottle necks but avoid optimization "in the small", because the small can be changed easily.
On the other hand, I'd say that the test suite you use for optimization should be taken as much from your real world experiences or expectations as possible. It would be different from a suite of unit tests or even integration tests.
The easy, general lesson is you need optimize "in the large" from day one, meaning having architecture that won't bottle necks but avoid optimization "in the small", because the small can be changed easily.
On the other hand, I'd say that the test suite you use for optimization should be taken as much from your real world experiences or expectations as possible. It would be different from a suite of unit tests or even integration tests.
I'd suggest that your happy path integration tests would be a good place to start, coupled with a database loaded more heavily than you expect in the real world.
Good software engineering practices (eg using good data structures, using appropriate algorithms, etc) is not optimization.
Software always requires tradeoffs (I don't consider "it does what it is supposed to" a trade off; that's more an invariant). In general, we put human consumption factors (readability, etc) high on the priority list, which is where it should be, usually.
Optimization is taking code with one set of value priorities and making a different set of priorities. Until you hit the real world, though, you won't know which priorities you need to value: is it hard drive throughput, raw processor cycles, or network latency? Regardless, in the end, you will generally have code that is less fit for humans, meaning the cost of maintenance will go up, so you want to ensure you are only optimizing what really needs to be optimized.
If "optimization" means "I didn't think about what data structure to use", you don't have an optimization problem. You have a software engineering problem.
Software always requires tradeoffs (I don't consider "it does what it is supposed to" a trade off; that's more an invariant). In general, we put human consumption factors (readability, etc) high on the priority list, which is where it should be, usually.
Optimization is taking code with one set of value priorities and making a different set of priorities. Until you hit the real world, though, you won't know which priorities you need to value: is it hard drive throughput, raw processor cycles, or network latency? Regardless, in the end, you will generally have code that is less fit for humans, meaning the cost of maintenance will go up, so you want to ensure you are only optimizing what really needs to be optimized.
If "optimization" means "I didn't think about what data structure to use", you don't have an optimization problem. You have a software engineering problem.
I find that these debates often come down to an either-or proposition: "put off optimization indefinitely" or "optimize to the max the whole way through." But it should never be so black and white. From a business view, both approaches are wrong, as they tend to entail unnecessary costs.
The OP is right that if you completely ignore performance as you code, you'll be doing things so blatantly wrong everywhere that it's difficult or impossible to fix. But, Knuth is right too: It's counterproductive to spend 10 times as long developing version 0.1 just to make sure it's the fastest 0.1 there could possibly be. This is because your early code is likely to change a great deal over the course of the project. You'll refactor, you'll add and remove features, and you'll realize you were wrong about where the bottlenecks are. Much of your early optimization effort will have been wasted.
After much programming experience, including trying both extremes, I've learned that a middle road is the most cost-effecive. The real quote from Knuth, so says Wikipedia, is: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." He's not saying to ignore performance. He's not arguing that you should blindly accept obviously unperformant architectures, such as the OP's example of iterating over a huge array when a hash would clearly be better. He's saying you shouldn't obsess over the "small efficiencies," the time-consuming rewrites of every little, rarely-called function to shave off 5% of execution time. At least not early in a project. I think Knuth would support doing that for a highly mature product, at least in some cases. Indeed, much of Knuth's most well-known work is entirely focused on performance. He's just telling people not to be overzealous.
So how does all this translate into everyday practice? I think a lot of it has to do with instincts and experience, which let you estimate the labor costs and performance benefits of individual optimizations. For example, as a web programmer, this ethos leads to decisions like this:
- I WILL prevent a given method from loading the same database records twice, even if loading them twice is the easy way. - I WON'T rewrite the SQL that my ORM generates in most cases. - I WON'T worry about the performance difference between calling an object's instance variable accessor vs reading the instance variable directly.
The OP is right that if you completely ignore performance as you code, you'll be doing things so blatantly wrong everywhere that it's difficult or impossible to fix. But, Knuth is right too: It's counterproductive to spend 10 times as long developing version 0.1 just to make sure it's the fastest 0.1 there could possibly be. This is because your early code is likely to change a great deal over the course of the project. You'll refactor, you'll add and remove features, and you'll realize you were wrong about where the bottlenecks are. Much of your early optimization effort will have been wasted.
After much programming experience, including trying both extremes, I've learned that a middle road is the most cost-effecive. The real quote from Knuth, so says Wikipedia, is: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." He's not saying to ignore performance. He's not arguing that you should blindly accept obviously unperformant architectures, such as the OP's example of iterating over a huge array when a hash would clearly be better. He's saying you shouldn't obsess over the "small efficiencies," the time-consuming rewrites of every little, rarely-called function to shave off 5% of execution time. At least not early in a project. I think Knuth would support doing that for a highly mature product, at least in some cases. Indeed, much of Knuth's most well-known work is entirely focused on performance. He's just telling people not to be overzealous.
So how does all this translate into everyday practice? I think a lot of it has to do with instincts and experience, which let you estimate the labor costs and performance benefits of individual optimizations. For example, as a web programmer, this ethos leads to decisions like this:
- I WILL prevent a given method from loading the same database records twice, even if loading them twice is the easy way. - I WON'T rewrite the SQL that my ORM generates in most cases. - I WON'T worry about the performance difference between calling an object's instance variable accessor vs reading the instance variable directly.
In my experience it's not the small stuff that kills you: so I iterate over an array rather than caching by ID. Maybe that matters, maybe it doesn't, but it's easy enough to fix if it does.
It's the big stuff that kills you: a snakes nest of dependencies with spooky action at a distance will never be easy to optimize or change. Focusing your design on simplicity of implementation and regularity of interface (in that order) gives you the best shot at reacting to what comes down the road later. And, as you say, it's appears to be experience that gives you the ability to recognize the simplest approach that isn't dead wrong.
It's the big stuff that kills you: a snakes nest of dependencies with spooky action at a distance will never be easy to optimize or change. Focusing your design on simplicity of implementation and regularity of interface (in that order) gives you the best shot at reacting to what comes down the road later. And, as you say, it's appears to be experience that gives you the ability to recognize the simplest approach that isn't dead wrong.
http://www.jwz.org/doc/worse-is-better.html
+1 to the middle road.
Engineering is about making such trade-off decisions, constantly. One of the many traits of a engineers is how quickly and accurately (on hindsight) we can make them.
And back to the blogpost, I feel that the array vs hash and LINQ examples are fairly contrived. In reality, a good engineer shouldn't even consider those approaches in the first place, unless there's a really compelling reason to do so.
Engineering is about making such trade-off decisions, constantly. One of the many traits of a engineers is how quickly and accurately (on hindsight) we can make them.
And back to the blogpost, I feel that the array vs hash and LINQ examples are fairly contrived. In reality, a good engineer shouldn't even consider those approaches in the first place, unless there's a really compelling reason to do so.
"'We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.' He's not saying to ignore performance."
Totally agree. In fact the rest of his quote is "... is the root of all evil. Yet we should not pass up our opportunities in that critical 3%."
Totally agree. In fact the rest of his quote is "... is the root of all evil. Yet we should not pass up our opportunities in that critical 3%."
A good intuition of what will and will not be on a critical path is also helpful. I will never spend time optimizing a method I know is called rarely, but if I know something is on the critical path then I'll keep an eye on performance and build it in such a way that I can visualise a way to refactor it "the right way" further down the road.
This.
And to add, it's important to to decouple pieces of your project so that it's easy to refactor and optimize parts as you get to them.
And to add, it's important to to decouple pieces of your project so that it's easy to refactor and optimize parts as you get to them.
However, optimization comes from "re-coupling" very often.
see for example : monolithic kernels (monolithic, fast) vs micro kernel (decoupled, slow).
If you really want something efficient, you'll have to think about it from the very beginning.
It might be what kinds of stuff I write (the stuff that's at all performance-sensitive is mostly data-processing algorithms), but I've had reasonably good success with the write-and-then-profile approach, and found myself wasting a lot of time on bad guesses if I tried to optimize things up front. I agree it's also possible to make something a really slow mess that's hard to fix, though.
My current method is to think about performance while writing code, but instead of doing anything particularly clever up front (unless it's easy), just make a comment to myself about potential places for improvements, like "doing the naive scan through the list for now, maybe could do [blah blah]". Then I'll profile later, and in a surprisingly large percentage of these cases, the places I identified for potential performance improvements don't matter, so it's a good thing I didn't bother doing something clever that would've taken more time to write, and been more error-prone.
My current method is to think about performance while writing code, but instead of doing anything particularly clever up front (unless it's easy), just make a comment to myself about potential places for improvements, like "doing the naive scan through the list for now, maybe could do [blah blah]". Then I'll profile later, and in a surprisingly large percentage of these cases, the places I identified for potential performance improvements don't matter, so it's a good thing I didn't bother doing something clever that would've taken more time to write, and been more error-prone.
"Just as you can't add quality to your code just before shipping, seldom can you significantly improve performance without dramatic rewriting."
That statement struck me as odd and possibly revealing... You should be able to significantly improve performance with a few changes .. in code written enough. Here, the code is modular so a given sort of slow thing should happen in only one place.
But naturally, in poorly written code, you need rewrite to optimize or to improve quality or to change anything else. It makes me wonder which kind of code he's looking at in making his generalizations. I'd agree it is never too early to write good code.
That statement struck me as odd and possibly revealing... You should be able to significantly improve performance with a few changes .. in code written enough. Here, the code is modular so a given sort of slow thing should happen in only one place.
But naturally, in poorly written code, you need rewrite to optimize or to improve quality or to change anything else. It makes me wonder which kind of code he's looking at in making his generalizations. I'd agree it is never too early to write good code.
Yes, I disagreed with that. In almost any project I've worked with, which has never been profiled, then over 90% of the time is spent in a few functions, which can be easily optimised.
Of course, after a few passes through the profiler, things start getting harder, but that's a seperate issue.
Of course, after a few passes through the profiler, things start getting harder, but that's a seperate issue.
I get to deal with the separate issue fairly often. After a few passes, 90% of the time is being spent in 90 functions taking no more than 2% each. At that point, I have to start ripping out layers of std::map<std::string, boost::shared_ptr<boost::any> >. That's even less fun than it sounds...
> You should be able to significantly improve performance with a few changes .. in code written [well?] enough.
Unfortunately, I don't think that is usually what happens. In an established code base that is reasonably well designed and well written, the performance is rarely dominated by a small number of very expensive bottlenecks that are ripe for local optimisation. Such things have usually been worked out a long time ago and there is no low hanging fruit left to pick.
At that point, if you've got five layers of architecture and each is only running at 75% efficiency because of all the little details, that might take your overall performance down to perhaps 25% of what it could be. If your software is I/O bound anyway or runs in half a second, you might not care. If that is the difference between taking a week to complete your research calculations and taking a month, or it represents a 5x increase in your hardware budget, then you probably care very much.
Unfortunately, I don't think that is usually what happens. In an established code base that is reasonably well designed and well written, the performance is rarely dominated by a small number of very expensive bottlenecks that are ripe for local optimisation. Such things have usually been worked out a long time ago and there is no low hanging fruit left to pick.
At that point, if you've got five layers of architecture and each is only running at 75% efficiency because of all the little details, that might take your overall performance down to perhaps 25% of what it could be. If your software is I/O bound anyway or runs in half a second, you might not care. If that is the difference between taking a week to complete your research calculations and taking a month, or it represents a 5x increase in your hardware budget, then you probably care very much.
...In an established code base that is reasonably well designed and well written, the performance is rarely dominated by a small number of very expensive bottlenecks that are ripe for local optimisation. Such things have usually been worked out a long time ago and there is no low hanging fruit left to pick.
Uh yeah. But I think this discussion is about creating a code and when to optimize it. It is kind of a tautology that when the code has been optimized and low-hanging fruit have been picked, they are, uh, gone.
Uh yeah. But I think this discussion is about creating a code and when to optimize it. It is kind of a tautology that when the code has been optimized and low-hanging fruit have been picked, they are, uh, gone.
Sure, but if you get to "just before shipping" then hopefully you are already well past that point. As the article said, you typically can't just retrofit more performance at that stage without some serious rewriting.
If you don't think ahead, it's easy to expose an API with implicit implications of poor or at least limited performance. The rest of your code base becomes dependent on it, and the month before shipping when you start really focusing on optimizing you realize it's too late to do much of anything to fix it. Sometimes it can be fixed but only by adding a ton of behind-the-scenes code complexity to that API to try to speculatively optimize for anticipated usage patterns.
A simple, innocent-looking example is a string data type that offers (and implicitly encourages) use of random access. If you're using a fixed byte-width for characters that's unproblematic, but it's an issue if you later replace it with a variable width representation like UTF-8. If all your string processing client code is written to rely on random access rather than incremental iterators, you have a problem. You could choose to store an index array alongside the character array. That would roughly double your string storage requirements, but at least you could still offer O(1) random access.
Or you could add code complexity by having each string remember the last index it looked up (sometimes called a finger), and if the next requested index is near by, it uses simple O(distance) forward or backward movement to return the nearby character's value. That seems like a good compromise. But what about multithreading? It looks like we need this cached index to be thread local. Not too bad. But what if we're interleaving accesses to the same string within a single thread? Now the different accesses are fighting over the same cached index. It looks like we need a multiple-entry cache to support this usage pattern.
If you're a good engineer you can probably find the right compromise along the above lines that works for your code base. But it would have been much better if your API design hadn't constrained your future opportunities for changing internal representations and optimizing performance.
Here's another example: OpenGL's immediate mode graphics interface where you can specify vertex data piecemeal. Because everything written in that style is code driven rather than data driven, the driver can't just allocate a single dynamic vertex buffer with a fixed vertex format and push attributes onto it in response to glColor(), glVertex(), etc. What you can do (and what the good OpenGL drivers do) is to speculatively keep around a bunch of staging buffers with different vertex formats behind the scenes that are first created dynamically in response to recurring vertex and primitive patterns. You can see how it goes: It's a lot like the implicit caching in the string random access example, and it has all the same problems, and a whole lot of new ones.
These kinds of late-in-the-day performance fixes for early API design decisions (even though the early API is perfectly clean and modular, in fact maybe too modular) are doable but they are costly in complexity and programmer time. They are also fragile. In my two examples, if you're in the sweet spot of the behind-the-scenes caching system, you'll be seeing good performance. But change one small thing that from your point of view shouldn't impact performance, and you might suddenly fall off a performance cliff because the cache is now too small, or whatever. Incidentally, this problem of fragile automatic optimization isn't restricted to library design. It's also a very serious issue with compilers. Modern compilers rely way too much on a fragile form of "crystal ball optimization", as one of my coworkers likes to call it. It makes it very difficult to write code with predictable high performance and even harder to maintain.
Damn, that was a lot of text.
A simple, innocent-looking example is a string data type that offers (and implicitly encourages) use of random access. If you're using a fixed byte-width for characters that's unproblematic, but it's an issue if you later replace it with a variable width representation like UTF-8. If all your string processing client code is written to rely on random access rather than incremental iterators, you have a problem. You could choose to store an index array alongside the character array. That would roughly double your string storage requirements, but at least you could still offer O(1) random access.
Or you could add code complexity by having each string remember the last index it looked up (sometimes called a finger), and if the next requested index is near by, it uses simple O(distance) forward or backward movement to return the nearby character's value. That seems like a good compromise. But what about multithreading? It looks like we need this cached index to be thread local. Not too bad. But what if we're interleaving accesses to the same string within a single thread? Now the different accesses are fighting over the same cached index. It looks like we need a multiple-entry cache to support this usage pattern.
If you're a good engineer you can probably find the right compromise along the above lines that works for your code base. But it would have been much better if your API design hadn't constrained your future opportunities for changing internal representations and optimizing performance.
Here's another example: OpenGL's immediate mode graphics interface where you can specify vertex data piecemeal. Because everything written in that style is code driven rather than data driven, the driver can't just allocate a single dynamic vertex buffer with a fixed vertex format and push attributes onto it in response to glColor(), glVertex(), etc. What you can do (and what the good OpenGL drivers do) is to speculatively keep around a bunch of staging buffers with different vertex formats behind the scenes that are first created dynamically in response to recurring vertex and primitive patterns. You can see how it goes: It's a lot like the implicit caching in the string random access example, and it has all the same problems, and a whole lot of new ones.
These kinds of late-in-the-day performance fixes for early API design decisions (even though the early API is perfectly clean and modular, in fact maybe too modular) are doable but they are costly in complexity and programmer time. They are also fragile. In my two examples, if you're in the sweet spot of the behind-the-scenes caching system, you'll be seeing good performance. But change one small thing that from your point of view shouldn't impact performance, and you might suddenly fall off a performance cliff because the cache is now too small, or whatever. Incidentally, this problem of fragile automatic optimization isn't restricted to library design. It's also a very serious issue with compilers. Modern compilers rely way too much on a fragile form of "crystal ball optimization", as one of my coworkers likes to call it. It makes it very difficult to write code with predictable high performance and even harder to maintain.
Damn, that was a lot of text.
You're right that if you can create a nice, modular API and have it be slow-as-heck if it's model doesn't correspond to the underlying hardware or processes.
But I would claim you are still in better shape than if you'd done spaghetti code.
Caching of a multitude of type can solve many problems of classes that treat resources as more available than they really are. You, yourself give the solution for your string example - in the yourself, if the actually needs random access in any performance-driven fashion, you'll need the extra-array so there's no problem. Double buffering and similar stuff have put to rest the problem of repainting pieces of windows in ordinary GUI programming. I'd imagine something similar could solve whatever the problem is you're talking about with OpenGL.
And given that you admit optimizations tend to be fragile constructs, it seems your argument strengths the argument, my argument, they should generally be done last.
But I would claim you are still in better shape than if you'd done spaghetti code.
Caching of a multitude of type can solve many problems of classes that treat resources as more available than they really are. You, yourself give the solution for your string example - in the yourself, if the actually needs random access in any performance-driven fashion, you'll need the extra-array so there's no problem. Double buffering and similar stuff have put to rest the problem of repainting pieces of windows in ordinary GUI programming. I'd imagine something similar could solve whatever the problem is you're talking about with OpenGL.
And given that you admit optimizations tend to be fragile constructs, it seems your argument strengths the argument, my argument, they should generally be done last.
> You're right that if you can create a nice, modular API and have it be slow-as-heck if it's model doesn't correspond to the underlying hardware or processes.
Well, the underlying problem is that the design of an apparently abstract interface can commit you to a concrete choice of data representation and implementation strategy. If you expose and encourage use of random access in your string data type, you are committing yourself to a fixed byte-width representation unless you want to pile on implementation complexity of the sort I described while still only managing to solve the problem imperfectly. (As an aside, my favorite implementation trade-off for this problem might be Factor's approach where any given string internally has a fixed byte width of either 1 or 4 depending on whether it contains exclusively ASCII or some non-ASCII characters. It gives you some of the benefits of variable-width representations at virtually no additional implementation complexity.)
> But I would claim you are still in better shape than if you'd done spaghetti code.
Probably, but why the strawman?
> You, yourself give the solution for your string example - in the yourself, if the actually needs random access in any performance-driven fashion, you'll need the extra-array so there's no problem.
But the size of the index array negates any space efficiency advantage a variable width representation might have had in the first place! It would only make sense if you needed to zero-copy pass a UTF-8 or UTF-16 buffer to a foreign API while still supporting constant-time random accesses into the buffer on your side.
> And given that you admit optimizations tend to be fragile constructs, it seems your argument strengths the argument, my argument, they should generally be done last.
Optimizations can definitely be fragile, but in my post I was referring specifically to automagic black box optimizations with my fragility claim. Put another way, performance guarantees should be an explicit part of your API design, along with error conditions and everything else. That's one thing STL got right. You have to lay the groundwork for future performance optimization possibilities with good API design. Those possibilities will be strictly limited if you don't think ahead. That might mean going with a bulk-oriented, data-driven API rather than a chatty, code-driven API, e.g. compare the way render state and shader constants work in Direct3D 10 versus its predecessors.
This is where experience and forward thinking is necessary. Crazy notion, I know.
Edit: Replied to the rest of your post.
Well, the underlying problem is that the design of an apparently abstract interface can commit you to a concrete choice of data representation and implementation strategy. If you expose and encourage use of random access in your string data type, you are committing yourself to a fixed byte-width representation unless you want to pile on implementation complexity of the sort I described while still only managing to solve the problem imperfectly. (As an aside, my favorite implementation trade-off for this problem might be Factor's approach where any given string internally has a fixed byte width of either 1 or 4 depending on whether it contains exclusively ASCII or some non-ASCII characters. It gives you some of the benefits of variable-width representations at virtually no additional implementation complexity.)
> But I would claim you are still in better shape than if you'd done spaghetti code.
Probably, but why the strawman?
> You, yourself give the solution for your string example - in the yourself, if the actually needs random access in any performance-driven fashion, you'll need the extra-array so there's no problem.
But the size of the index array negates any space efficiency advantage a variable width representation might have had in the first place! It would only make sense if you needed to zero-copy pass a UTF-8 or UTF-16 buffer to a foreign API while still supporting constant-time random accesses into the buffer on your side.
> And given that you admit optimizations tend to be fragile constructs, it seems your argument strengths the argument, my argument, they should generally be done last.
Optimizations can definitely be fragile, but in my post I was referring specifically to automagic black box optimizations with my fragility claim. Put another way, performance guarantees should be an explicit part of your API design, along with error conditions and everything else. That's one thing STL got right. You have to lay the groundwork for future performance optimization possibilities with good API design. Those possibilities will be strictly limited if you don't think ahead. That might mean going with a bulk-oriented, data-driven API rather than a chatty, code-driven API, e.g. compare the way render state and shader constants work in Direct3D 10 versus its predecessors.
This is where experience and forward thinking is necessary. Crazy notion, I know.
Edit: Replied to the rest of your post.
`it is never too early to write good code`
Can't word it any better!
Can't word it any better!
there's a difference between non-optimized code and code that's just written by a bonehead. I don't think it's actually more complicated than that.
We of course are all boneheads at one time or another so we should go through our code continuously as we write and refactor it to fix bonehead-isms. But "optimizations", inlinings, making the code harder to read for performance, awkward caching steps that make the code harder to debug, that's always later, once the real world, usages, and data expose what's really important.
We of course are all boneheads at one time or another so we should go through our code continuously as we write and refactor it to fix bonehead-isms. But "optimizations", inlinings, making the code harder to read for performance, awkward caching steps that make the code harder to debug, that's always later, once the real world, usages, and data expose what's really important.
Update: A torrent of readers and my meager server's CPU usage sits at a constant <1%. Hardly miraculous — trivial even — 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.
Web servers typically don't fall over because PHP or Rails can't hand a whole ten requests a second on a CPU that can do a billion operations a second. They fall over because of a performance optimization written into the default Apache configuration in1996 to increase throughput by ~2%
Death to KeepAlive.
Web servers typically don't fall over because PHP or Rails can't hand a whole ten requests a second on a CPU that can do a billion operations a second. They fall over because of a performance optimization written into the default Apache configuration in1996 to increase throughput by ~2%
Death to KeepAlive.
From the article: "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?"
Spending 5 minutes choosing the right algorithm every time you write a component isn't premature optimization, especially if you know to within an order of magnitude or so what N is. If you have no idea what N is, then go with the simplest implementation that works at the time. (That assumes your design doesn't tie a bunch of internal component decisions together, in which case I must say, "good luck with that.")
In any case, the time to optimize is most likely after you've written some tests to verify the code is correct. I've seen too many cases where people spent a lot of time making something really complicated--and completely untested--run faster, and then later said, "Now how can we make this correct?"
Spending 5 minutes choosing the right algorithm every time you write a component isn't premature optimization, especially if you know to within an order of magnitude or so what N is. If you have no idea what N is, then go with the simplest implementation that works at the time. (That assumes your design doesn't tie a bunch of internal component decisions together, in which case I must say, "good luck with that.")
In any case, the time to optimize is most likely after you've written some tests to verify the code is correct. I've seen too many cases where people spent a lot of time making something really complicated--and completely untested--run faster, and then later said, "Now how can we make this correct?"
Yes, the classic 'It is easier to optimize correct code than to correct optimized code' quote comes to mind :)
Incidentally, I just finished reading Knuth's original article from which his now famous quote originated. If you'll forgive the large copy and paste I think it is insightful to see the quote in context.
The original quote from 'Structured Programming with go to Statements' Computing Surveys, VOL 6, No. 4, December 1974 on page 268 is:
"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 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."
The original quote from 'Structured Programming with go to Statements' Computing Surveys, VOL 6, No. 4, December 1974 on page 268 is:
"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 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."
The quote makes sense in its completeness:
"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil"
The key expression is "small efficiencies" - choosing the right data structures for any reasonable amount of data is not small.
"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil"
The key expression is "small efficiencies" - choosing the right data structures for any reasonable amount of data is not small.
The idea behind not optimizing prematurely is there are some optimizations that come at a cost of decreased maintainability/readability. Not prematurely optimizing means choosing to prioritize your code structure to allow no-unexpected-side-effects changes and easy readability by other people, but it is not an excuse to use a O(n^2) algorithm when an O(n) algorithm can be used without cost. You should always be aware of the ballpark O(n) of your code, but in the initial stages of a project you might choose to prioritize other things.
I suspect the idea is more that people keep obsessing (and wasting time) about bullshit like whether iterating though a for loop forwards or backwards is faster, or whether they should have public fields to avoid the method overhead from accessors - stuff that is truely, utterly irrelevant except possibly in the most extreme hot spots.
Bentley's Programming Pearls soundly differentiates solving a problem by taking into consideration all known information (including limitations such as the presence of duplicate values when sorting a massive list of numbers, for example), using the most appropriate data structures and algorithms, etc. from code-tuning.
I mention this because it seems that when people talk about premature optimization, they are generally referring specifically to code-tuning. Thinking about a problem holistically and making smart choices about data structures and algorithms is never premature optimization—those steps are absolutely definitive, while code-tuning can and should be reserved for later in the development process, because it is does not define the solution.
I mention this because it seems that when people talk about premature optimization, they are generally referring specifically to code-tuning. Thinking about a problem holistically and making smart choices about data structures and algorithms is never premature optimization—those steps are absolutely definitive, while code-tuning can and should be reserved for later in the development process, because it is does not define the solution.
Everything in moderation. Iterating over a giant array when a hash lookup is the correct approach is not avoiding premature optimization, it is incompetence.
I disagree completely with this.
I have been a paid software engineer for 15 years, and have been writing code since I was 8 years old.
Numerous projects (I would say even the majority) had spots that could be optimized. Don't believe me? Ok, on the video pipeline I have been working on the last few years: When we finally got around to profiling we found that a large chunk of time was spent scanning for H264 start codes... And we immediately saw that if we simply scanned through the buffer the other way, we cut down it's run time dramatically. Or how about the time that the profiling revealed a "hash table" that was, due to a bug, actually a linked list!
Finally, I am tired of working on projects that "optimize" the whole time. The code bases are CRAP. Full of "optimizations" that usually are actually slower, and a nightmare to maintain. Do you know what works better: Concentrate on solving the problem at hand and writing high quality simple code, and don't do anything else.
I have been a paid software engineer for 15 years, and have been writing code since I was 8 years old.
Numerous projects (I would say even the majority) had spots that could be optimized. Don't believe me? Ok, on the video pipeline I have been working on the last few years: When we finally got around to profiling we found that a large chunk of time was spent scanning for H264 start codes... And we immediately saw that if we simply scanned through the buffer the other way, we cut down it's run time dramatically. Or how about the time that the profiling revealed a "hash table" that was, due to a bug, actually a linked list!
Finally, I am tired of working on projects that "optimize" the whole time. The code bases are CRAP. Full of "optimizations" that usually are actually slower, and a nightmare to maintain. Do you know what works better: Concentrate on solving the problem at hand and writing high quality simple code, and don't do anything else.
In my experience — and this does require experience — you can avoid big problems by simply factoring well. For me, the best proxy for “well-factored” is the least amount of code necessary for a defined task.
If the code is clear, then it’s unlikely that performance problems will be expensive to fix. Caching is a good example — most of my methods will allow an “if cache exists” block to be inserted near the beginning in about 5 minutes, when the need arises.
But experience does matter. I’ve learned that LINQ can be expensive unless you understand a few key behaviors. Knowing the platform very well allows you to not make huge mistakes on a first-pass.
If the code is clear, then it’s unlikely that performance problems will be expensive to fix. Caching is a good example — most of my methods will allow an “if cache exists” block to be inserted near the beginning in about 5 minutes, when the need arises.
But experience does matter. I’ve learned that LINQ can be expensive unless you understand a few key behaviors. Knowing the platform very well allows you to not make huge mistakes on a first-pass.
How would you know the difference between the first chart and the third chart a-priori. Say you saw the third chart and mistook it for the first chart?
Having looked at 10's of profiles using frameworks and seeing the exact same profiles across the applications, can we ignore the framework part of it?
Recently we spent a week profiling an application trying to find a very bad, but very hard to reproduce bug. After a week of profiling, debugging, pouring over logs, etc. It turns out the problem might have been a defective controller on the storage appliance the database was using. How can you know a-priori what you are looking at?
Having looked at 10's of profiles using frameworks and seeing the exact same profiles across the applications, can we ignore the framework part of it?
Recently we spent a week profiling an application trying to find a very bad, but very hard to reproduce bug. After a week of profiling, debugging, pouring over logs, etc. It turns out the problem might have been a defective controller on the storage appliance the database was using. How can you know a-priori what you are looking at?
One really has to think of the WHY behind such idioms. The reason for not beginning to early are that you might not know what the real bottlenecks will be and therefor sacrifice readability and time for finishing an early version, which would actually allow you to have a look on how things work in practice. Usually you want to have some kind of small prototype/proof of concept to follow other idioms, like "release soon, release often" or "small is beautiful".
Also it depends on what you actually do. If you want to create something where you mostly care about performance it's not like you'd start when everything is already finished. Another thing is that such idioms are important to make you a good programmer writing good software which isn't always what you want to do in real life. Often you just care about making money or pleasing your customer/boss.
Think about Sun Tzu. A lot of people in the military read his books. He was very experienced and had a lot of knowledge, still it may be impractical to follow his idioms, even if they are one hundred percent correct in every situation.
I guess the world would be better, if everyone would listen and _always_ follow guidelines, as the UNIX philosophy, but the current situation real word sadly adds a lot of variables which cause you to ignore them.
Or in other words: It all depends.
Or to quote Einstein: All things are relative.
Also it depends on what you actually do. If you want to create something where you mostly care about performance it's not like you'd start when everything is already finished. Another thing is that such idioms are important to make you a good programmer writing good software which isn't always what you want to do in real life. Often you just care about making money or pleasing your customer/boss.
Think about Sun Tzu. A lot of people in the military read his books. He was very experienced and had a lot of knowledge, still it may be impractical to follow his idioms, even if they are one hundred percent correct in every situation.
I guess the world would be better, if everyone would listen and _always_ follow guidelines, as the UNIX philosophy, but the current situation real word sadly adds a lot of variables which cause you to ignore them.
Or in other words: It all depends.
Or to quote Einstein: All things are relative.
It seems to me, that this article is based on wrongly understood idea.
"Premature optimization" should be rather considered as an idea to consider the whole picture first. It's scary sometimes, but engineers are usually paid because of creating something and that creation is usually more than a set of highly optimized code lines.
Consider the fact, that even when analyzing algorithms, you should consider whether your point of focus are allocations or comparisons. You have to remember about cpu time, memory, I/O, cache, data fragmentation and sometimes even power outages.
Thus, there is ABSOLUTELY NO EXCUSE TO CODE WITHOUT UNDERSTANDING WHAT GIVEN CODE IS SUPPOSED TO DO, but killing yourself over few extra miliseconds of cpu time, or even few extra megabytes of storage usually is SENSLESS.
What's more premature optimization can easily lead to mentall exhaustion (because "well, I spent 8 hours writing a function in assembly, so I'm tired") and eventually, decrease of quality of the rest of the code. And even if not, you have good chance of writing code, that is beyond reusability.
Summing up, pretty please, everyone, stop confusing 'code desing' and 'optimization'.
"Premature optimization" should be rather considered as an idea to consider the whole picture first. It's scary sometimes, but engineers are usually paid because of creating something and that creation is usually more than a set of highly optimized code lines.
Consider the fact, that even when analyzing algorithms, you should consider whether your point of focus are allocations or comparisons. You have to remember about cpu time, memory, I/O, cache, data fragmentation and sometimes even power outages.
Thus, there is ABSOLUTELY NO EXCUSE TO CODE WITHOUT UNDERSTANDING WHAT GIVEN CODE IS SUPPOSED TO DO, but killing yourself over few extra miliseconds of cpu time, or even few extra megabytes of storage usually is SENSLESS.
What's more premature optimization can easily lead to mentall exhaustion (because "well, I spent 8 hours writing a function in assembly, so I'm tired") and eventually, decrease of quality of the rest of the code. And even if not, you have good chance of writing code, that is beyond reusability.
Summing up, pretty please, everyone, stop confusing 'code desing' and 'optimization'.
The problem is: in a fast-moving startup we rarely have the time/luxury to spend time on optimizing after the fact. IMO your choice will depend on how isolated the optimization task is and how long it will take.
E.g., we're building a healthcare app with Google Web Toolkit on the front and Google App Engine at the back. On the front, I'm creating single instances of each page (e.g., one patient widget instance per patient) right now because changing that model from regular (new instance every time) to singletons after release is prohibitively expensive and risky.
On the other hand, I've postponed server memcache implementations to cache query results on the app server because the APIs are fluid/changing (so it's wasteful to do now), and I can take up all the memcache setups together comfortably after the release. I.e., that task unlike the widget instances is isolated and relatively safe to do.
E.g., we're building a healthcare app with Google Web Toolkit on the front and Google App Engine at the back. On the front, I'm creating single instances of each page (e.g., one patient widget instance per patient) right now because changing that model from regular (new instance every time) to singletons after release is prohibitively expensive and risky.
On the other hand, I've postponed server memcache implementations to cache query results on the app server because the APIs are fluid/changing (so it's wasteful to do now), and I can take up all the memcache setups together comfortably after the release. I.e., that task unlike the widget instances is isolated and relatively safe to do.
The problem with postponing optimization is that getting really good performance out of a system sometimes depends on picking a particular underlying model, which may subject your system to some unexpected constraints.
For example, who remembers DOOM? The distinctive 2-1/2 D level designs were done that way to simplify rendering, as an optimization. That's how the rendering engine could run at a remarkable framerate on the hardware of the time. If ID had started off with a full 3D rendering system and said "well, it runs at 2 FPS, lets go design some levels, we'll optimize the rendering engine later" ... well, the game would have worked out quite differently.
For example, who remembers DOOM? The distinctive 2-1/2 D level designs were done that way to simplify rendering, as an optimization. That's how the rendering engine could run at a remarkable framerate on the hardware of the time. If ID had started off with a full 3D rendering system and said "well, it runs at 2 FPS, lets go design some levels, we'll optimize the rendering engine later" ... well, the game would have worked out quite differently.
Sure. Thats picking the right algorithm though, so rendering is O(n) say not O(n^2). But yes these things do make a huge difference.
There is a certain kind of project where you're not sure, at the outset, if what you want to do is even possible due to performance issues. Obviously, that question needs to be answered as early as possible, and so the project is about "optimization" from day one.
A good example is id games -- Quake, Doom, et al. They design games around technology. They need to figure out exactly what the engine can do before anything else.
Phones and tablets are making this sort of project common again as people push the limits of those platforms.
A good example is id games -- Quake, Doom, et al. They design games around technology. They need to figure out exactly what the engine can do before anything else.
Phones and tablets are making this sort of project common again as people push the limits of those platforms.
"Just as you can't add quality to your code just before shipping, seldom can you significantly improve performance without dramatic rewriting"
That's total bullshit. I've seen massive improvements from just a few key optimisations on very large code bases.
Q: "When is it a mature time to start to consider performance, however?"
A: When you have problems due to slow performance.
The "premature optimisation is the root of all evil" catchcry is basically the same as "don't solve problems you don't have".
That's total bullshit. I've seen massive improvements from just a few key optimisations on very large code bases.
Q: "When is it a mature time to start to consider performance, however?"
A: When you have problems due to slow performance.
The "premature optimisation is the root of all evil" catchcry is basically the same as "don't solve problems you don't have".
"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?"
There's not prematurely optimizing and there's criminal neglect.
Sure, if you take the First Year Student™ approach to problem solving then a simple database query and processing might be O(scary) and fail to perform.
Generally speaking though, a few milliseconds away from that clever bitwise operators hack would be fine.
There's not prematurely optimizing and there's criminal neglect.
Sure, if you take the First Year Student™ approach to problem solving then a simple database query and processing might be O(scary) and fail to perform.
Generally speaking though, a few milliseconds away from that clever bitwise operators hack would be fine.
I use a simple rule, treat all new code as production code, don't assume you'll have time to go back and optimise it, because you won't, ever.
> Most will say the time to optimize is once you're fairly well along in development.
I call BS. But, if most do say that they are stunningly wrong. The time to optimize is after it is determined that some portion of code is too slow to meet a (non)functional or business requirement.
I call BS. But, if most do say that they are stunningly wrong. The time to optimize is after it is determined that some portion of code is too slow to meet a (non)functional or business requirement.
Always avoid premature optimization and every optimization before you can run benchmark is premature.
But, hey, don't do anything stupid. Like pulling whole dataset over the net from database just to calculate some sum or average or do a join or iterate to find something.
But, hey, don't do anything stupid. Like pulling whole dataset over the net from database just to calculate some sum or average or do a join or iterate to find something.
Unrelated comment, but the sidebar on that page sort of looks like a premature optimization...what's the purpose of making it hard to see? I didn't notice it was there until I accidentally moused over it. Can anyone explain the efficacy of that in design terms?
The point is that you're not supposed to see it until you are done with the article, and start mousing around. Just the fact that you couldn't see it means that it did its job.
Now whether that's a good idea is another debate - it's a design decision to "hide" the sidebar.
But do this - compare the page with and without the sidebar - you'll notice that you focus on the actual article much better without the visual clutter of the sidebar in the way.
Now whether that's a good idea is another debate - it's a design decision to "hide" the sidebar.
But do this - compare the page with and without the sidebar - you'll notice that you focus on the actual article much better without the visual clutter of the sidebar in the way.
I read this article then came back to read the comments. I hadn't even noticed there was a sidebar. So yes, I'd agree with you, I focused much better on the actual article with a hidden sidebar.
The trouble is that once you know the sidebar is there, it is much more annoying and intrusive than it would be if it was standardly visible.
i've never seen that before, but it's an interesting concept. Maybe the idea is to not distract the reader from reading the primary content, but offering an easy way to get more data on the writer should the reader choose.
It worked great for me, I didn't even notice the sidebar and read the article beginning to end happily. It's hard to say if it would work for everyone w/o some testing of course.
It worked great for me, I didn't even notice the sidebar and read the article beginning to end happily. It's hard to say if it would work for everyone w/o some testing of course.
An experienced developer can in many cases be explicit about when he is sacrificing performance for the sake of getting things ready. Usually ends up writing code whose performance can be fixed with relative ease. Those places will be the low-hanging fruits.
Finally someone who can get some attention voices the truth!
It has been frustrating to see how people avoid doing a `bit of thinking` in the name of the gold words 'Premature Optimization is the root of all evil'.
It has been frustrating to see how people avoid doing a `bit of thinking` in the name of the gold words 'Premature Optimization is the root of all evil'.
I suppose, that's what you call ’uniformly slow code’. http://c2.com/cgi/wiki?UniformlySlowCode
I like the observation. It is a corollary of Amdahl's law: if every step is slow there is no point optimizing any of them until you can optimize all of them.
Premature optimization is a skill. That is, you know how to write good code and never waste your time on neither premature nor postmature optimization.
I imagine Knuth's first version of Tex was pretty darn fast even without 'optimizing'.
As they say there is more than one way to mouth a cliche.
My opinion is that an optimization that costs less than a couple of hours of development time, if it doesn't harm code quality, is invariably worth doing. Even if there's no evidence (because the code is being constructed at the time) that this matters from a performance perspective, you should spend the hour or two and get that low-hanging fruit and not worry about it being "premature". If you don't do this when you're in-context, it'll cost an order of magnitude more time later on if the problem is discovered in profiling and needs to be addressed in the future.
When premature optimization is evil is when it damages code aesthetics and maintainability. There is a limit, in performance, to what can be achieved with aesthetically clean code. What awful programmers (who think they're being clever) tend to do is write the ugly, dirty code because it's super-fast, but no one can maintain it and even they don't understand it.
What good programmers do is write clean code on sound fundamentals first, so that people can understand what's going on. Then, if a performance problem's discovered and a certain module needs to be optimized, they put the critical region behind a clean interface and allow the dirtiness (which they document heavily) to be in the implementation.
TL;DR: spend time to make your code performant if it doesn't damage code health; be very cautious about replacing clean code with faster, dirty code.
When premature optimization is evil is when it damages code aesthetics and maintainability. There is a limit, in performance, to what can be achieved with aesthetically clean code. What awful programmers (who think they're being clever) tend to do is write the ugly, dirty code because it's super-fast, but no one can maintain it and even they don't understand it.
What good programmers do is write clean code on sound fundamentals first, so that people can understand what's going on. Then, if a performance problem's discovered and a certain module needs to be optimized, they put the critical region behind a clean interface and allow the dirtiness (which they document heavily) to be in the implementation.
TL;DR: spend time to make your code performant if it doesn't damage code health; be very cautious about replacing clean code with faster, dirty code.
These days, with the test suites we have and the highly decoupled architectures we have created, we can profile nearly instantaneously. Put ten million records (or more, depending on your expected volume) in a database and test your code against it. If your test begs for mercy, it isn't premature optimization to fix it.
From a startup's perspective, I understand the idea of failing fast, but getting some buzz and seeing your servers melt down is a good way to fail fast as well.