Slashdot Mirror
Hacker's Delight
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.
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.
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.
I got this a couple of months ago and found it rather good -- If you are looking to shave a couple of cycles off you implementation of integer logarithms then have a look at it. I'd agree with the reviewer that it is rather dense, and you'll need to be numerate (graduate maths or C/S) to understand the algorithms, but not to find it useful. There are also quite a few amusing anecdotes from the author's time at IBM. Worth the cover price.
Jim Green
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
Carpe Diem
The reviewer speaks truth about this book. It is quite dense and, in many cases, violates the "Code should be easily decoded by future programmers" rule.
I got this book for Christmas because I specifically asked for it. My mom was a bit put off by the title, though. The title refers to the original definition of "hacker," so don't get excited if you're all about computer security. There's nothing in there for you.
One of my favorite concepts in this book is the author's use of non-breaking code. As many of you know, the mechanism for sending instructions to the CPU requires a bit of quasi-premonition. Riddle your code with many if-, while-, and (the hideous) goto-statements, and you will end up with slow code due to the seemingly random jumps inside memory. Use some of the methods in this book, however, and you will end up with more efficient code in the longrun. Need I remind you of the speedup generated when you use non-breaking code within a lengthy while loop?
IWARS.
People, in general, disappoint me. Politicians even more so.
Do the math. As a first approximation, optimization of software running on a desktop machine has to save the users as much or more time than it takes the developer to produce and support the optimization. This means that if the statements you are optimizing will not be executed hundreds of millions of times, it's not worth worrying about. OTOH, if MS could shave one second off the start-up time for Word or IE, that would be worth tens of millions of dollars annually in additional productivity for the US economy overall.
Im no math wizard, but bc is a nice tool...
4 6946771846748599451815207469 92649396248644355553.000000
scale=6
((2^239)-1)/479
184430800081250973860
seems to be without a remainder, but this does not equal a proof.
The PowerPC Compiler Writer's Guide
ISBN 0-9649654-0-2
edited by Steve Hoxey, Faraydon Karim, Bill Hay and Hank Warren.
That book obviously had no qualms about targeting a narrow audience and it served its purpose well.
When Sun was awarded patent #6,073,150 it had a familiar ring. Sure enough: figure 3-25 on page 50 of "PowerPC Compiler Writer's Guide". Only the patent was awarded in 2000 and the Guide was published in 1996. That was about where I lost respect for the patent process.
I have come to despise the whole hacker culture based on the use of the sort of tricks the review illustrated. I comment my code like crazy, avoid confusing booleans, put null on the lhs of code, etc.
But unfortunately, the other people on my team do none of that, and it would only be more painful if they were trying the sort of stunts this book focuses on.
Believe with me, my saplings.