The Sad Reality of Post-Mature Optimization
blog.yafla.com
blog.yafla.com
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.
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
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.
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.
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.
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.
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.
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
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%."
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.
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.
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.
Can't word it any better!
Of course, after a few passes through the profiler, things start getting harder, but that's a seperate issue.
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.
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.
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.
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.
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.
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.
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.
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?"
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."
"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.
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 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.
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.
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?
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.
"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'.
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.
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.
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.
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".
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 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.
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.
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.
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 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'.
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.