Are You a Hacker?

Back in the old days, "hacker" defined people who delighted in getting right down into the bits and making software work well. Henry S. Warren's Hacker's Delight captures some of the algorithms and feeling of classical hacking.

• By Mike Gunderloy
• 01/01/2003

Back in the good old days, "hacker" was not a dirty word. Hackers were the people who delighted in getting right down into the bits and making software work well. Henry S. Warren's Hacker's Delight (Addison-Wesley, 2002) captures some of the algorithms and feeling of classical hacking. Does it still have relevance for today's developers?

Twiddling the Bits
Let me give you one short exhibit to capture some of the flavor of Warren's book. Here's a pseudocode algorithm to reverse the bits in a four-byte register:

Unsigned rev(unsigned x {
x = (x & 0x55555555) < 1="" |="" (x="">> 1) & 0x55555555;
x = (x & 0x33333333) < 2="" |="" (x="">> 2) & 0x33333333;
x = (x & 0x0F0F0F0F) < 4="" |="" (x="">> 4) & 0x0F0F0F0F;
x = (x < 24)="" |="" ((x="" &="" 0xff00)="">< 8)="">
((x >> 8) & 0xFF00 | (x >> 24);
return x;
}

Never mind how it works; isn't it a thing of beauty?

Of such things are this book made. It's full of formulas and algorithms for things like finding 0 bits, long division of various sorts, square and cube roots, base conversions, Gray codes, and so on. These are the underpinnings of our art, the results of man years of work by those who first soldered together vacuum tube computing circuits, the pioneers whose names are largely forgotten. And yes, they're still relevant to developers today.

No, Really
OK, admit it. By now most of you are thinking that I've lost my mind. Or perhaps a few of you remember that I was pursuing a degree in the history of computing before I was run out of grad school on a rail, and figure I'm just nostalgic for those good old days of all-nighters. Well, not quite. (Besides, I still pull all-nighters from time to time, so there). Let me explain.

When I say that this book is relevant to today's developers, I don't mean that in a strict literal sense. Oh, sure, there are some microcode developers and embedded-systems folks who will probably benefit from the collected knowledge and clever tricks here. But even those of us who drive the latest Windows IDEs on monsters with a gigabyte or more of RAM can benefit from developing at least a bit of the hacker mindset, as exemplified in this book.

I believe the underlying lesson here is profound: Elegance and beauty can come from the simple act of minimizing the consumption of expensive resources. Let me address those two things in turn beginning with the latter.

Scarcity and Computing
If all computing resources were plentiful, writing code wouldn't be half so fun as it is. Think about it for a moment. Imagine a world in which every computer had an infinite amount of ram and a knob on the CPU that could turn up its speed as fast as you like. Displays would have as many pixels as you care to name, and disk space would magically appear as it was needed. What would be the point of tricky programming in such a world? Want to search for a value in a database table? Start with the first row, read each row in turn, stop when you find the value you want. For that matter, you might as well use a text file as a database; they're easier to write, and speed is infinite. Want to calculate the nth digit of pi? Use the simple formula pi = 4 * (1 - 1/3 + 1/5 - 1/7…). Never mind that it converges ever so slowly; just crank up the CPU speed a bit more. Who needs database indexes and fancy algorithms?

I don't know about you, but that doesn't sound like much fun to me. More to the point, of course, this scenario doesn't bear much relationship to the real world. Although the scarce resources change, there are always scarce resources in computing. Many of the results in Hacker's Delight date back to a time when memory was fiendishly expensive and clock speeds were so slow that cycles had to be hoarded. The pioneers were always keenly aware of the tradeoffs between speed and size, and in many cases you'll find multiple ways to do things depending on whether speed or size was more important on a given machine. Perhaps my favorite story in this regard is of the old IBM 1620 CADET, whose name was a supposed acronym of "Can't Add, Doesn't Even Try". It had no fancy algorithms for arithmetic; thanks to a relatively commodious (for the time) memory of up to 60,000 decimal digits, it did addition by table lookup. This made perfect sense for a machine where memory was cheap and CPU cycles were dear.

Fast-forward 40 years from the IBM 1620 and you get to one of today's interesting ideas, object prevalence (see http://www.advogato.org/article/398.html and http://bbooprevalence.sourceforge.net/). In a system using prevalence, you hold all of your business objects in RAM, and serialize their transactions to disk. It makes perfect sense in a world where memory is cheap and CPU cycles are dear. Hey, wait-did anything change in 40 years?

Experienced engineers know about the 80/20 rule: Twenty percent of the engineers drink 80 percent of the beer. Well, that's one formulation, anyhow. Extended to the domain of optimizing software, 80 percent of your performance bottlenecks typically come from 20 percent of your code. The key to making software is to find that 20 percent where you're overusing scarce resources, and then figure out how to cut it out.

Elegance and Beauty
Most software developers have a pragmatic approach towards identifying elegance and beauty in source code: we don't know how to define it, but we know it when we see it. I must admit that I don't have a good definition for elegance in code either; but for one approximation elegant code is code that, when I look at it, makes me wish I had thought of it myself. Elegance comes in any language and any problem domain.

Thinking about elegance and hacking, it seems to me that there's something else going on here. Elegant code is largely code that makes good use of scarce resources. Take that bit-swapping algorithm that I quoted at the start of this column. One reason to appreciate it is that it can be executed in relatively few instructions. (Another is that it's just pretty, with those patterns of 5's and 3's and 0F's). Of course, not every resource constraint generates beautiful code. Sometimes you have to do ugly things like overlap program and data segments when resources get really scarce. But that's another story.

The Unique Resource
And do you know why we like code that makes good use of scarce resources? Because there's one resource that we can never buy any more of, and that Moore's law isn't helping at all: our own time. For all the improvements in RAM and CPU and hard drives, our minds are the same as they ever were. When we optimize our code, when we write something clever, elegant, and yes, even beautiful, we're not just making good use of machine resources. We're making good use of our own resources. Part of what drives us towards better coding is the notion that some day, somewhere, somehow, a few developers are going to get time to relax. And why shouldn't we be those few?

So, whether you're into bit-twiddling or not, I urge you to adopt a hacker's attitude towards your development work. Don't, for heaven's sake, tell the boss, but: programming is supposed to be fun. Sure, it's nice to charge a good hourly rate, but really, the good developers are the ones who enjoy the challenge, the ones who want to know how things work, the ones who constantly challenge themselves to do more with less. And you can be one of those developers too.

Am I making any sense at all? Should I stop this philosophizing, install Eclipse, and learn to write Java instead? Write and let me know. I'll use the most interesting comments in a future issue of Developer Central.