8 ms·

The Sad Reality of Post-Mature Optimization

192 points by p4bl0 15y ago

amcintyre 15y ago
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?"
- taway990 15y ago
  Yes, the classic 'It is easier to optimize correct code than to correct optimized code' quote comes to mind :)
jwingy 15y ago
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?
- barkingcat 15y ago
  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.
  - MaysonL 15y ago
    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.
  - ryduh 15y ago
    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.
- robertpateii 15y ago
  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.
_delirium 15y ago
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.
zzzeek 15y ago
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.
ebiester 15y ago
I think something is lost in translation. Once upon a time, premature optimization was writing a subroutine in assembly because you "knew it would be slow." Now, people are using ill-fitted data structures and optimizing for developer time in the name of avoiding premature optimization. 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.
- iamwil 15y ago
  http://the-witness.net/news/2011/06/how-to-program-independent-games/ 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
  - watmough 15y ago
    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.
mmelin 15y ago
Everything in moderation. Iterating over a giant array when a hash lookup is the correct approach is not avoiding premature optimization, it is incompetence.
cpt1138 15y ago
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?
xedarius 15y ago
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.
SoftwareMaven 15y ago
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.
icebraining 15y ago
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.
joe_the_user 15y ago
"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.
- chanux 15y ago
  `it is never too early to write good code` Can't word it any better!
- CJefferson 15y ago
  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.
  - corysama 15y ago
    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...
- psykotic 15y ago
  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.
jkyro 15y ago
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.
dm_mongodb 15y ago
I imagine Knuth's first version of Tex was pretty darn fast even without 'optimizing'.
chanux 15y ago
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'.
jarrett 15y ago
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.
- jhchen 15y ago
  "'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%."
scotty79 15y ago
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.
mdomans 15y ago
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'.
cstavish 15y ago
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.
dusklight 15y ago
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.
- brazzy 15y ago
  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.
mojuba 15y ago
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.
deathflute 15y ago
As they say there is more than one way to mouth a cliche.
mwsherman 15y ago
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.
dools 15y ago
"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".
njharman 15y ago
> 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.
extension 15y ago
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.
nickzoic 15y ago
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.
- justincormack 15y ago
  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.
TrentS 15y ago
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."
goblin89 15y ago
I suppose, that's what you call ’uniformly slow code’. http://c2.com/cgi/wiki?UniformlySlowCode http://c2.com/cgi/wiki?UniformlySlowCode
tete 15y ago
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.
maayank 15y ago
"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.
michaelochurch 15y ago
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.
herdcall 15y ago
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.
dicroce 15y ago
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.
patio11 15y ago
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.
jmount 15y ago
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.

192 points by p4bl0 15y ago

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?"

taway990 15y ago
Yes, the classic 'It is easier to optimize correct code than to correct optimized code' quote comes to mind :)

jwingy 15y ago

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?

barkingcat 15y ago
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.
- MaysonL 15y ago
  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.
- ryduh 15y ago
  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.
robertpateii 15y ago
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.

_delirium 15y ago

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.

zzzeek 15y ago

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.

ebiester 15y ago

I think something is lost in translation. Once upon a time, premature optimization was writing a subroutine in assembly because you "knew it would be slow." Now, people are using ill-fitted data structures and optimizing for developer time in the name of avoiding premature optimization. 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.

iamwil 15y ago
http://the-witness.net/news/2011/06/how-to-program-independent-games/ 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
- watmough 15y ago
  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.

mmelin 15y ago

Everything in moderation. Iterating over a giant array when a hash lookup is the correct approach is not avoiding premature optimization, it is incompetence.

cpt1138 15y ago

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?

xedarius 15y ago

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.

SoftwareMaven 15y ago

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.

icebraining 15y ago

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.

joe_the_user 15y ago

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

chanux 15y ago
`it is never too early to write good code` Can't word it any better!
CJefferson 15y ago
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.
- corysama 15y ago
  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...
psykotic 15y ago
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.

jkyro 15y ago

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.

dm_mongodb 15y ago

I imagine Knuth's first version of Tex was pretty darn fast even without 'optimizing'.

chanux 15y ago

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

jarrett 15y ago

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.

jhchen 15y ago
"'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%."

scotty79 15y ago

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.

mdomans 15y ago

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

cstavish 15y ago

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.

dusklight 15y ago

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.

brazzy 15y ago
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.

mojuba 15y ago

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.

deathflute 15y ago

As they say there is more than one way to mouth a cliche.

mwsherman 15y ago

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.

dools 15y ago

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

njharman 15y ago

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

extension 15y ago

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.

nickzoic 15y ago

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.

justincormack 15y ago
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.

TrentS 15y ago

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

goblin89 15y ago

I suppose, that's what you call ’uniformly slow code’. http://c2.com/cgi/wiki?UniformlySlowCode http://c2.com/cgi/wiki?UniformlySlowCode

tete 15y ago

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.

maayank 15y ago

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

michaelochurch 15y ago

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.

herdcall 15y ago

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.

dicroce 15y ago

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.

patio11 15y ago

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.

jmount 15y ago

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.