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

Sounds like an interesting read...

[Gortbusters.org]

Almost as interesting as those lovely discrete math textbooks were. This sounds more like 'Optimizer's Delight.'

To be honest, 'Hacker's Delight' sounded more like a cookbook title.

Dubious value?

[SuperMario666]

Furthermore, there are many tricks which, while interesting, would be difficult to apply to real-world applications.

Maybe you should break open the old CS textbook instead. IMO, learning general principles would be a much better use of your time.

Re:Dubious value?

[KDan]

Seriously depends what you're doing. If you're writing the next entreprise application, sure, optimization tricks are not really your main concern... If you're writing a game engine, though...

I remember back when I was younger and had much more free time (*longing sigh*) I spent most of a term and a summer writing a 3D wolfenstein-like engine, mostly under the careful instruction of a book: Tricks of the game programming gurus. The book was great, and though it gave some optimizing ideas here and there the resulting engine was very slow (esp. compared to the wolf3d engine, which was so perfectly smooth... and the engine I made didn't even do monsters and doors and items). So then I turned to another book I had, called "PC Interdit", which was written in french and oriented towards Pascal rather than C which I was using, but explained a number of optimization tricks which made all the difference (examples: page flipping in mode X instead of double-buffering in mode 13h, basics of coding fast assembler functions to optimize C functions, etc). Before using that book's advice, my engine would run at something like 10 fps or so on my 486DX4 100Mhz in turbo mode, and 1fps more or less without turbo mode... After the optimizations, it ran very smoothly in turbo mode and at least 5-6fps in non-turbo.

So if you're programming a game engine, those books are really really useful. Or in fact if you're programming anything where squeezing every tiny bit of performance is critical. If you're programming a J2EE servlet engine, though, then for sure, it's a waste of your time.

Daniel

The author..

[J x]

I know the author well. Here's some background for you slashdotters who may doubt his expertise:

Henry S. Warren, Jr., has had a forty-year career with IBM, spanning from the IBM 704 to the PowerPC. He has worked on various military command and control systems and on the SETL project under Jack Schwartz at New York University. Since 1973 he has been with IBM's Research Division, focusing on compilers and computer architectures. Hank currently works on the Blue Gene petaflop computer project. He received his Ph.D. in computer science from the Courant Institute at New York University.

Sugar Hill Gang, anyone?

[dasmegabyte]

I said a hip, hop, hippy, hippy to the hip hop hacking you don't stop a hacking until the bang bin boogie said backslash the boogie to the rhythm of the boogity beat..

What you hear is not a test, I'm hacking to the beat. And me, the compiler, and my code are gonna start to move your screen.

See, I am das MB and I'd like to say hello
To the linux loners and the mac fairys and the losers on windows.

But first I gotta..bang slash bin slash P E R L said hack kernel yes hack hack the kernel until the whole machine runs like hell.

Proper.

If you like this idea..

[stevey]

If you like this topic you may well appreciate this Assembly Language Gems Page

It's a little biased towards x86 assembly, but there are some neat tricks there, and some stunningly lovely code.

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:Base 2

[KDan]

Well, I remember when I was reading a book about assembler they expressed it beautifully by saying that if school taught kids binary numbers instead of the decimal system, the entire mathematics syllabus could be taught in a couple of months with time to spare.

Binary maths make many integer operations ridiculously simple, and while the fact that it's cheaper and more feasible to detect 2 states than 10 is true, there's also a certain simplicity that you can get to by coding everything with binary logical gates which wouldn't quite be there if you used some sort of decimal logical gates...

Basically, binary arithmetic is really simple so can be optimized really well and is much more universal, in the wider philosophical sense, than decimal arithmetic. Everything in the universe seems to revolve around a binary concept, rather than a decimal one... matter/antimatter, existence/non-existence, quantum spin states, etc.

Daniel

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