Seven Deadly Sins of Programming – #6

May 31, 2006 at 11:14 am

Seven Deadly Sins of Programming – #6


Way back in my early career, I worked on a graphics program written in FORTRAN that was used to plot engineering data.


It ran on Tektronix 4014 terminals.


Our application – known as E.G.G. (Engineering Graphics Generator, one of a whole series of not-very-creative punny names used by the group) – used a menu-based approach. The user would place the cursor (moved by the thumbwheels on the right) over a menu option, hit the spacebar, and then the code would figure out what to do.


The internal architecture of the app was really pretty good. There were, if I recall correctly, 39 different screens, and each item on the screen had an id associated with it. The code would find the right item on the page, come up with a numerical code (menu number * 100 + item number), find that in an array of function pointers, and then call the appropriate function.


It worked fine, and allowed us to have a batch mode as well.


But after I started playing around with it a bit, I noticed that the command dispatch was a bit slow. After you selected an item on a screen, it took at least a couple of seconds for the screen to erase and redraw (this was running on shared Vaxen, so you didn’t get much CPU time, and what you got was fairly slow).


I did some digging, and found that the original developer (no longer with the group) had written the item lookup code using a Fibonaccian search.  This is a search that is similar to binary search, but doesn’t require complex operations such as divide by two or shift right (that alone should tell you the vintage of this search).


Such a search *may* have made sense on earlier systems, but on Vaxes, both the divide by two or shift right are in the hardware. So, we were using a search method optimized for constraints that we didn’t have that nobody in the group understood, in an attempt to be faster than binary search.


But it was a *clever* algorithm.


At this time, we had about 1200 items in our dispatch table. The first thing I did was build sub-index that stored the starting index of the first item in each menu, which meant the search space for a typical menu item went from 1200 items to about 30 items. The second thing I did was switch to interpolation search, which, given the nearly perfect distribution of items numbers within a menu (most menus had item numbers from 1-n, with very few holes), gave an almost perfect search. And it was code that most people in the group could understand.


So, the dispatch time went from a few seconds to about half a second, and I wrote up a “cost savings” in which I multiplied the number of users we had by the amount of time they used the application by the number of menu picks per hour, and figured out that I had saved the company around $30K per year. For which I got a $100 gift certificate.


So, what’s the point of that story?


Well, it makes me look good, which is the primary goal. It also illustrates that cleverness is an over-rated attribute of developers. How many times have you seen:


for (int i = 0, j =bounds; i < upper; i++, j += JUMP_SIZE)
{
    …
}


That’s somebody who is trying to be clever. They should have written:


int j = bounds;
for (int i = 0; i < upper; i++)
{
    …
    j += JUMP_SIZE
}


Which takes us on a long and tortuous trip to


Sin #6 – Inappropriately clever code


What examples of this have you seen?

Tags: