Premature optimization in deciding how to optimize?

Question

We have a class that has been properly identified for optimization. We've done the profiling and testing, and it's a problem.

Now we have two possible approaches for optimizing this class:

1. There is some very low-hanging fruit. We can rewrite this in a few days in such a way that the interface and results aren't changed, so we don't have to change any code that uses the class. We can see what effect this has on performance and go from there. This seems to me to be a very low risk, low investment approach.

2. Since we're already going to be making changes, we could go all out in our optimization. The suggested approach would implement a third-party engine and require us to change the code that uses this class, as well as transform the existing client data that is sent to the class into a format usable by the third-party engine. This may not take too much longer to code, but there would be much more testing required. This seems like a very high-risk, high-investment change and will require a lot of extra testing to make sure we don't break the calling code and don't break the existing client data.

I of course can't test ahead of time, but the second approach will probably execute more quickly and be more memory-efficient. However, I'm not sure how much faster, and I'm not sure if the extra effort will even be worth it. I'm not sure that once we made the low-risk changes, we would still consider the the code to be a valid target for optimization.

You can probably guess which approach I would rather take. I'm at odds with a coworker on this one.

So here's my question: Is the second option premature optimization despite the fact that we've already identified this code for optimization? What's the approach that should be taken in this situation?

Answer 1

In layman's words:

I consider that option 2 would be premature optimization.

Some of the things that make me think is that the justification if vague:

1. You don't explain why you need to use the third party engine you mention.

2. You mention that "without testing it, the second approach will probably be faster". Be careful not to under-estimating the effort and the complexity of the change. Be sure to have a battery of unit tests.

3. "Since we're already going to be making changes". You just don't make an optimization because you might as well do it.

Answer 2

"The second approach will probably execute more quickly" is a good sign of premature optimization.

Any optimization should be based on a guess followed by evidence (the guess may be replaced by hard data, if any). Example:

1. Guess: if we merge those two loops into one, it will run faster.

2. Evidence: the profiling shows that the merge allowed to optimize this piece of code by 27.4%.

   Conclusion: we should merge two loops.

In your case, guess-evidence pattern would be something like:

1. Guess: the second solution would be faster than the first alternative.

2. Evidence: this benchmark, as well as this one and that one, show that the second solution would be indeed faster by a factor of 1.15 to 1.70.

   Conclusion: given the current requirements, the difference between the effort needed to accomplish the second solution by comparison to the first one and the expected negative consequences of each of those alternatives on the quality of code, the second solution should be chosen only if the speed factor is superior to 1.45. Do we take the risk?

You, on the other hand, are imagining that the second solution will probably be faster, without any hard data as a proof. It means that it can be faster by a factor of 5.0. Or a factor of 1.005. Or a factor of 0.6, i.e. be actually slower.

Basing your optimization decision on an assumption rather than on hard data is premature optimization.

Note that you don't have to implement both solutions and compare them: it would be too expensive. But you still have to gather at least some data about a potential optimization in a context of the programming language and compiler you use before optimizing your code.

Answer 3

• I think it's fine to include low-hanging fruit outright. That is, if it takes a comparable effort and number of code lines to implement an O(n²) solution and an O(n) solution, there's no reason not to pick the better of the two.

• I don't think that plunging into a massive rewrite without some profiling / evaluation is a good idea. What evidence do you have that the new approach will be faster? Do you have a testing prototype, or someone else's experience with the 3rd party engine you mention? Can you spend a day or two to make this clear, and get some hard numbers?

• Is there any hard evidence that the piece you're going to optimize is an actual bottleneck? Usually ~10% of code spends ~90% of cycles; if the rest ~90% of code became twice as slow, nobody would notice. Make sure you're optimizing an actual hotspot.

Answer 4

Without details it is hard to know for sure, but from my occasional experience of maintaining third party components, I would much rather have control of in-house code than be reliant on others. 3rd-party software adds a new layer of administrative complexity to a project that needs a better justification than that it is probably faster. I recommend against integrating third party software unless you really have no practical alternative.

It sounds to me that the case for that is unproven, so stick with option 1.

Answer 5

This is what so many people do - the "ready, fire, aim" approach. They fix a problem before knowing if it is a problem. Then if a little time was saved they say "See, it worked! Can we move on now?", or if it doesn't save much they say "Well, we need to try another guess".

Don't invest any time in fixing stuff unless you know it will save significant time, and here's how I find out. Keep an open mind and let it tell you what to fix. It will probably be different from what you would have guessed.

Then rinse, and repeat. That's how you do serious performance tuning.