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

Re:The author..

[Anonymous Coward]

Where did you copy'n'paste this information from? Have your heard of plagiarism? You shouldn't try to pass that paragraph as your own. People like make me sick, it just encourages entities like Disney to lobby for their extensions of their copyrights because people LIKE YOU, will abuse it.

Get a clue.

Sounds cool

[photon317]

Sounds like he knows his stuff. The world needs more asm-aware programmers. High level languages and all the trickery that is "keep the source simple, waste the abundant cycles" and all are important things. The problem IMHO is that these are techniques to be applied by a fully-fledged programmer, who is capable of doing it the hard way in C or even asm - but too many modern programmers have only ever know the world of OO languages. The Leaky Abstractions paper applies here too.

Re:Sounds cool

[johnnyb]

You should check out the book I'm writing - Programming from the Ground Up - http://savannah.nongnu.org/projects/pgubook/

Definitions, Titles, and Categorization

[_Sprocket_]

I noticed this book at the local Barnes and Noble. Unfortuately, it was (and still is) mis-catagorized and firmly stuck in the "Security" area of the technical / computer section.

Now I know that I'm toying with the usual hacker/cracker jihad. None the less, it seems the definition of "hacker" associated with secuirty is so engrained in to society that it manages to overcome even the content of the book itself. I would have thought the B&N folks, being in the book profession, would manage to catch this. Judging a book by its cover and all that (makes me wonder where a book called 'Pinky Fuzzy Bunnies' that studies furry erotica would land).

Of course, B&N are not the definitive measure of language. Where they stick a book doesn't go much beyond acknowledging one use of our much-flamed word. It doesn't negate the history of the word nor offer final proof of its popular definition. But it does show the power of that popular definition despite the obvious intent of the book's author.

Be it for good or not - there it is.

oh please

[tps12]

For 99% of people, these kinds of unreadable but "neat" optimizations are going to have no impact on execution time whatsoever. Good algorithm design and efficient architecture -- and yes, optimization, once you've profiled and located a bottleneck -- are worth far more than stupid bit shifting tricks, and your code will actually end up maintainable. If you follow the advice in this book, you're liable to produce code that looks like the Linux kernel.

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.

Re:Hard to understand?

[miu]

But those distinctive shortcuts that everyone recognizes can cause you to "label" the code and move on while reviewing code that is due for maintenance.

Everyone recognizes what:

while (*dst++ = *src++) ;

is supposed to be doing, but I recently cleared a mystery bug in a very old routine that used such code. The problem had been missed for years because people "recognized" the code and moved on - despite the fact that there were several problems with it.

Redundant and proud of it

[Chocolate Teapot]

In principal, I like the sound of this book. However, I have a shelf full of so-called 'secrets of the masters' books, each weighing in at around half a ton, containing 800 pages all stating the obvious. I look forward to hearing comments from those who have actually bought the thing.

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.

Time for me to state the obvious... I have worked on many applications that run uneccessarily slowly as a result of an accumulation of inefficient code. Sure, it is often better to sacrifice raw performance for portability, maintainabilty and plain readability, but code does not need to be obcure to be efficient. Optimisers take much of the hard work out of achieving this, but taking the time to examine compiler output once in a while will help you write high-level code in such a way as to give the optimiser room to strut it's stuff. If anything, there is often more to be gained by programs written in high-level languages (VB, perl, python, etc) if the coder takes time to examine the structure of his code and attempts to eliminate bottlenecks. Inefficiency is not a function of the development tools, it's a function of laziness.

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

Re:HACKMEM

[cperciva]

If you have a minute, then, how does that work?

All prime factors of 2^p-1 are of the form 2kp+1 for some k. If we're looking for a factor, the obvious place to start is with k=1, which tells us that we should look at 2*239+1 = 479.

Now, 2^7 = 128, so
2^14 mod 479 = 98,
2^29 mod 479 = 2*98^2 = 48
2^59 mod 479 = 2*48^2 = 297
2^119 mod 479 = 2*297^2 = 146
2^239 mod 479 = 2*146^2 = 1

so 2^239-1 is a multiple of 479.

Premature optimisation is the root of all evil

[Ella the Cat]

I've not read the book yet, but I do have a general worry, that optimisation isn't always done in the right context or for the right reasons. Code that runs faster in a small test program can break when part of a larger program (by thrashing the cache for example). What's the point of optimising something that's seldom invoked, in other words, always ask an enthusiastic optimiser to show you their profiling results.

My favourite hacks are Jim Blinn's floating point tricks - 10% accurate square roots and reciprocals that blow away a floating point unit and are just what you need in graphics and games.