When to Worry About Performance

I spent the day wrestling with slow code. Most of it was very easy to spot where the slowness was. I like using the poor man's profiler to spot these. What's the poor man's profiler you ask? Basically it boils down to using the debugger to break already executing code. The theory is that in all probability it will break in or near the code that is taking a lot of time. It's quick and should work with nearly any debugger. The assumption, of course, is that you can make something slow enough to start it and then cause it to break before it gets past the slow code.

In any case that isn't the point of this post. The real question is when should you worry about performance. One developer I worked with many years ago said this. "Make work, make it work right, make it work fast." I like this quote but I add to it, when you are working on an algorithm take 5 minutes and pick a fast one.

Most of the time I encounter slowness when there is an O(n^2), O(n log(n)) or O(n) algorithm in use when an O(n) or O(log(n)) algorithm is easy to choose at development time. The problem is that often that slower algorithm is excessively difficult to replace. Often, the slow algorithm isn't discovered until the customer pushes the limits of the program.

I lost count many, many years ago of the number of times where the engineer came to the conclusion that no one would ever need more than n of these things. Then the customer comes up with a case that the engineer didn't think about where 10 * n is a small number.

Rule of thumb. Think of the largest number of items that you can imagine that a customer would ever need then multiply it by 100 or 1000. Then do your design based on that assumption.

Another idea that makes my blood boil is the whole Moore's Law thing. We have effectively seen the end of this about 4 years ago. That was when memory speed stopped keeping up with CPU speed. The words I hear are just buy a faster computer. Or in a year or two it won't matter.

The problem with this is that if computers double in speed every 18 months or so, you are talking about an algorithm that is O(n log(n)). If you are throwing O(n^2) algorithms at this they will swamp any CPU speed gains you get. Couple this with Moore's Law not keeping up with expectations and ever more efficient ways of increasing n and performance suddenly becomes a huge issue.

The current trend in multi-core processors is also interesting. However, if an algorithm is O(n) or worse on memory access with only 1 path to memory, no amount of additional cores will help.

So the bottom line is that if you write any code that is essentially unbounded on n, spend a few minutes coming up with an algorithm that is optimal for large n.

I leave you with one caution. If n is only very rarely large and is very frequently on the order of magnitude of 10, then that better algorithm may in fact be slow if you are working with a large number of items.