Steve's Tech Talk

Why Software Has Bugs

I’ve been thinking about the causes of bugs in software in the past week.  I reflect on this a lot and as I get older, I try to put habits into place that eliminate bugs before they happen.  As an example, in doing string manipulation in C, I had a nasty habit of writing the null terminator in the wrong place – always off by one on the generous side.  I put into place a habit that eliminated this by effectively proving my code correct through induction as I wrote it.

But these kinds of bugs are the microscopic bugs.  I’m thinking of the more granular and endemic.

The main three causes of larger bugs are:

1. Finite memory
2. Finite storage
3. Finite processing time

I say this because when the straightforward solution for a problem is not so good, it requires us to be clever instead.  And this quote from Brian Kernighan is a pretty good illustration of why that’s not always the best thing:

Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.

Take, for example, color quantization.  This is the task of selecting a good, finite palette of colors to be used in rendering a continuously colored image.  I can describe a straight forward algorithm very concisely:

foreach (pixel in image)
    add the color to a histogram
while size of histogram > desired number of colors
    merge least frequent colors into nearest greater frequencied colors

There we go.  Color quantization in 4 lines of code.  The problem is that in a 24 bit image, there could be up to 16,777,216 (2²⁴) possible colors, and the main chunk of a straightforward histogram will require 67,108,864 bytes, but since we have to merge, we can’t just store the frequency – we’ll need the color too, so that’s 134,217,728 bytes.  So scanning the histogram on the first pass alone will take something on the order of 33M operations (16M reads and 16M compares) – and you want to do this because you want to eliminate all the empty cells.  Then you need to sort the cells on frequency – there’s an n * log n operation, where n is in the millions.

It’s bad.  Really bad.  You could get away with another approach of limiting your histogram to the size of the image – that’s good – you can’t have any more unique colors than you have pixels, but now each time you record a color, you’re going to either have to hash on the color or insertion sort.  The cleverness required just went up.

There is a fairly good way to do quantization called Octree Quantization  (Michael Gervautz, Werner Purgathofer), which uses a sparse tree where each node has up to 8 children and the greatest depth of the tree is 8.  In this case, r, g, and b components are used to navigate a path through the tree by using most to least significant bits in r, g, and b to select a child from a given node.  When the load on the tree gets too high, it gets reduced.  This is all very, very clever and to make it perfomant requires even more cleverness.

I say this because in implementing the algorithm on my test image, which had 16M pixels in it, I found that one particular routine – a very simple one – was getting called 75M times.  This is bane of image processing.  Simple routines that get called an insane number of times.  With some refactoring, I eliminated 2/3 of the cost of that routine.  Ultimately, the running time of the quantization in managed code on a 2.4G machine was 3.3 seconds.  Compare this with the cost of simply scanning the image, which is .374 seconds. 

But each of these refactorings adds complexity and complexity adds bugs.  And the ultimate cause of those bugs is limited resources, because each change in algorithm and each refactoring was necessitated by the problem scope.   Roughly 10% of the cost of quantization is scanning the image and 90% is cleverness.  You shouldn’t be surprised now about why I think that cleverness causes bugs.

So what can we do to avoid the cost of cleverness?

1. Don’t assume you need to be clever a priori
2. Use a language appropriate to the problem domain
3. Use well-debugged, well-tested libraries to do common data structuring
4. Strive to keep your code as clean¹ and as readable as possible
5. Optimize based on measurements not instinct
6. Unit test before and after refactoring

¹by clean, I mean something similar to the adage of always wearing clean underwear because you might have to go to the hospital – if you just refactored and someone else had to pick up you code, would they want to jam spikes into their eyes (or for the clearer thinkers, would they want to jam spikes into your eyes)?