Hacker's Delight

Ben Olmstead writes with the review below of Henry S. Warren's Hacker's Delight, which is not about tricking folks into providing sensitive information, but rather about how to cleverly manipulate computers into doing more work on their part with less work on yours. Read on for his brief review. Hacker's Delight author Henry S. Warren Jr. pages 320 publisher Addison Wesley Professional rating Excellent reviewer Ben Olmstead ISBN 0201914654 summary Collected Tips & Tricks for Programmers

Hacker's Delight is an impressive compendium of clever tricks for programmers. Warren concentrates on micro-optimizations -- few of the tricks in this book operate on more than 3 or 4 words of memory -- and he displays an impressive knowledge of diverse computer systems in the process.

Who Should Read This Book

Hacker's Delight is hardcore in its presentation and subject matter. I would not recommend this for a beginning programmer -- to fully understand the material requires at least some knowledge of concepts such as Assembly and Machine languages. However, anyone who writes performance-critical software should read this book, even if they do not plan to write Assembly code, both to learn the tricks given, and to learn the concepts behind them.

What's Good

The book is organized into chapters where Warren presents related tricks. In each chapter, he presents a few tricks which perform related tasks -- for example, in Chapter 3, he presents tricks for rounding (up or down) to the next power of 2, rounding to a multiple of a known power of 2, and detecting power-of-2 boundary crossings (i.e., checking for page faults). For each trick, he discusses why it works, whether the technique is generally applicable, related tricks which might be better in specific situations, and where a trick might be used in the real world.

Warren keeps his discussion architecture-neutral, while noting optimizations and problems for specific architectures for specific tricks -- in the process, he displays a vast array of knowledge about specific processors, from 1960's mainframes to x86, MIPS, PPC, Alpha, and others. He also skims the surface of hardware-design issues in a few places -- for example, he devotes a page or two to explaining why computers use base 2 for arithmetic, and why this is the most efficient choice.

What's Bad

This is an extremely dense book, and there are sections which are difficult to understand. Furthermore, there are many tricks which, while interesting, would be difficult to apply to real-world applications, and use of these tricks does violate the Keep It Simple, Clock Cycles Are Cheap And Someone May Have To Understand Your Code philosophy which is harped upon so heavily (not without reason) in modern software design. However, someone writing a compiler or high-performance code may feel that the benefit outweighs the potential risk.

The Summary

If you want a better understanding of the hardware on which your code runs, or you need to squeeze clock cycles, or you just enjoy seeing clever tricks, this is an excellent book. If you primarily use high-level languages such as VB, perl, python, etc., this may not be the right book for you. Be prepared for very dense material.

You can purchase Hacker's Delight from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.

Comments

Hard to understand?

[cperciva]

use of these tricks does violate the Keep It Simple, Clock Cycles Are Cheap And Someone May Have To Understand Your Code philosophy

In some cases, this may be true, but not always. If you want to increment a multiple-precision value, the textbook method is

int i, carry=1;
for(i=0;icarry+=x[i];
x[i]=carry;
carr y/=radix;
};

while the "cute trick" method is

int i=0;
while(++x[i]==0) i++;

The textbook method takes a while to recognize, just because it's very similar to many other loops; but the second is distinctive and can be recognized immediately. If I'm maintaining someon else's code, I'd much prefer to see the second.

HACKMEM

[ctrimble]

HACKMEM is a document from the Elder Days at the MIT AI lab. It's not about optimisation, like Hacker's Delight, but it's full of lots of cool math/comp sci tidbits. I first discovered it back in the 80s when I was a script kiddie looking for cracking info (I hadn't understood the distinction between hacking and cracking at the time) and discarded it as lame. I revisited it about five years later after spending some time in the CS department and realised what a gem it really is.

Here's a sample:

ITEM 63 (Schroeppel, etc.):
The joys of 239 are as follows:

* pi = 16 arctan (1/5) - 4 arctan(1/239),
* which is related to the fact that 2 * 13^4 - 1 = 239^2,
* which is why 239/169 is an approximant (the 7th) of sqrt(2).
* arctan(1/239) = arctan(1/70) - arctan(1/99) = arctan(1/408) + arctan(1/577)
* 239 needs 4 squares (the maximum) to express it.
* 239 needs 9 cubes (the maximum, shared only with 23) to express it.
* 239 needs 19 fourth powers (the maximum) to express it.
* (Although 239 doesn't need the maximum number of fifth powers.)
* 1/239 = .00418410041841..., which is related to the fact that
* 1,111,111 = 239 * 4,649.
* The 239th Mersenne number, 2^239 - 1, is known composite, but no factors are known.
* 239 = 11101111 base 2.
* 239 = 22212 base 3.
* 239 = 3233 base 4.
* There are 239 primes < 1500.
* K239 is Mozart's only work for 2 orchestras.
* Guess what memo this is.
* And 239 is prime, of course.

HACKMEM