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

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

Refreshingly different for the CS bookshelves

[Anonymous Coward]

This is a great book for those looking to expand thier minds beyond the usual low-level-phobic computer science pulp. I do not employ any of the book's teqniques in my code, but I'm glad to know of them.

Definition of "Hacker"

[RT Alec]

I am pleased to see the correct use of the term "hacker". Now if we could just work on the folks at CNN...

Efficiency != Portability (or overall goodness)

[shoppa]

This sort of subject has been around for years, and gets rediscovered every so often, by a "new" generation of hackers. (Look, for instance, at the big deal made about Duff's Device when C came along.) The problem is, that implementations of these ideas are often non-portable. (To other architectures, languages, or even the next version of the compiler.)

That's not to say that I don't enjoy reading about these clever things; there is a lot to be learned by studying this stuff. But implementing them is usually a mistake these days, if for no other reason than because there's already a portable way to do it which is probably more efficient. To go back to the Duff's Device example, almost all compilers will implement loop unrolling already. And that's a C-language trick, supposedly already a high-level language. Note I said supposedly! :-)

Re:Hard to understand?

[stratjakt]

Many times the 'tricks' method is less readable, and nothing more.

A good compiler will recognize produce the same optimized byte code for different code blocks. It should unroll shorter fixed lenth loops and automatically inline function calls when it determines that it's not worth the overhead of popping the caller onto the stack.

In the end it's the design as a whole that will determine efficiency. For instance, recursion. As soon as it's learned, a coder has a tendency to use the 'cute trick' of recursion everywhere, and doesn't realize that it's rarely the optimal solution to a problem.

Personally, I loathe the 'cute-ass cryptic trick' coding philosophy. I constantly battle with all the bad habits I picked up having been born and raised on the Commodore 64. Unconditional branches (goto), cramming all the code you can onto one line, one or two letter variable names, functions longer than a chapter of the bible. Blech.

Re:Performance Critical

[Servants]

aimed more at getting more features then having a fast, stable program

As I understand it, "stable" is kind of in opposition to both "fast" and "features". The reviewer's point is that super-optimized code tends to have strange tricks in it that are difficult to read and understand. That makes the code hard to maintain and increases the likelihood of bugs, so performance tweaking isn't a great idea unless speed is really important to an application.

Re:oh please

[Pseudonym]

For 99% of people, these kinds of unreadable but "neat" optimizations are going to have no impact on execution time whatsoever.

So? Most technical books are useless for 99% of people. I personally have no use for The Black Art of C# in 21 Days For Idiots. For my part, I used to write compilers. This book would have been invaluable for me. I guess I was in the 1%.

The only danger in this kind of book is that people will use the techniques in it blindly, in which case they arguably shouldn't be writing software anyway (or at the very least should have it thorougly reviewed before committing).

If you follow the advice in this book, you're liable to produce code that looks like the Linux kernel.

So if you have to produce code like the Linux kernel, it sounds like the book for you.

Incidentally, the Linux kernel is that way for several reasons, some of which are valid (e.g. profiling or back-of-the-envelope calculations showed that something was going to be a bottleneck) and some of which made sense at the time. For an example fo the latter, see do_pipe() in fs/pipe.c. If starting the kernel again today, it would make a lot more sense to use C++ which would make all those gotos unnecessary, but it's a bit late now.