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.
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.
--------
Free your mind.
i said a hip hop a hippie the hippie
to the hip hip hop, a you dont stop
a rock to the bang bang boogy say upchuck the boogy,
to the rhythm of the boogity beat.
now what you hear is not a test, i'm hacking to the motherfuckin beat
and me, rob malda, and the rest are gonna try and move your feet
see i am timothy and i'd like to say hello
to the ACs, freaks, and logged-in kooks, and all the goatse trolls
but first i gotta bang bang the boogie to the boogie
say up jump the boogie to the bang bang boogie
let's rock, you dont stop
rock the rhythm that will make your body rock
well so far youve heard my voice but i brought two friends along
and next on the mike's my man hemos
come on, hem, sing that song
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.
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.
...is the exact oposite of afternoon delight, I would imagine.
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.
Hey freaks: now you're ju
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.
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.
11*43+456^2
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
Why is that? I always figgered it had something to do with it being easier/cheaper to build hardware that only needs to store and detect 2 states (on/off) than multiple intermediate states.
I am pleased to see the correct use of the term "hacker". Now if we could just work on the folks at CNN...
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.
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! :-)
manipulate computers into doing more work on their part with less work on yours
To paraphrase the great Terry Pratchet: "Beware labour saving devices which are smaller than their manuals".
You douche, the switch is either on or off. It's not a dimmer switch!
But in your case, maybe it is a dimmer switch.
Ingrate! If it weren't for me, it'd be running gene sequences all day and night. Computers have no sense of perspective.
will it teach me how to hack Windows ME??? It's so hard -- I can't figure it out!
There's an important lesson here: Don't leave your computer on overnight.
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.
Karma: Good (despite my invention of the Karma: sig)
I always thought that ternary computers were theoretically more efficient, from a mathmatical point of view.
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
Since when has the C operator been advanced programming techniques ?
cc65 is an ANSI C compiler for 6502 machines. It's sweet.
READY.
#
In some cases, this may be true, but not always. If you want to increment a multiple-precision value, the textbook method is while the "cute trick" method is
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.
Tarsnap: Online backups for the truly paranoid
Modest doubt is called the beacon of the wise. - William Shakespeare
I said a hick, hack, the hacker, the hacker To the hick hick hack, a you don't stop! The hack it to the bang bang hacker say up hacked the hacker The the ryhthm of the hacker, the hack! Old school!
3313 bytes in body
I almost thought that was 31337 or something!
What you hear is not a test, I'm hacking to the beat.
Where does the school board find them and why do they keep sending them to ME?
I thought that hacking was how to cleverly manipulate computers into doing more work on their part with way too much work on yours. Just get out of the house and fricken buy a skillet... no need to hack one up.
You quitting proves that the karma kap worked. The most annoying of the whores shut up. --CmdrTaco
So, who are you? Rosie or Mike Blaszczak?
1 914654/
http://www.amazon.com/exec/obidos/tg/detail/-/020
Left shift multiplies by a power of two - it doesn't round anything.
Modest doubt is called the beacon of the wise. - William Shakespeare
Hi, you gotta remember the author is a long time IBM'er. IBM started creating mainframes at the dawn of the computer age. My first IBM was a 1401. It used BASE 10 and you had to write your own bootstrap to power up and load your application. BASE 2 came along later when it became clear that on/off pairs of core memory might as well be binary arithmetic. (If I remember right you had to write your own subtract, multiply, and divide routines for the 1401)
Install Access on it. I cant think of a worse punishment.
Here's a sample:
HACKMEMI'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.
You say your karma is excellent and even claim to have invented the Karma sig? Oh please. I see that your comments have averaged a score of less than 1 recently. I seriously doubt with all those -1's you've racked up that your Karma is Excellent.
Yeah, I just passed the Excellent -> Good threshold. I'll update the sig. Thx.
If you actually have read this book, why are you plagiarizing Mike Blaszczak's Amazon review in a fairly unsubtle manner?
;-).
OK, it's good Slashdot Karma, but think what this is doing to your *real* karma -- much more of this and you're heading for reincarnation as a nematode worm
Being a one armed, Taiwanese child myself, yes.
If you compare two bits, the sum is zero if they're the same (both zero or both one). If they are different, the sum is one. This simple comparison (which is also an addition) can be performed by a single XOR gate, which is like, four transistors.
Yes, you also have to include carry-out and carry-in, but that just amounts to a few more gates. A 1-bit full-adder circuit uses only about ten or so transistors.
That's why silicon computers use base-2: the simple math can be implemented in simple logic gates.
Rick.C
You were 80% angel, 10% demon. The rest was hard to explain. - Over The Rhine
"Math in a song is good."-Linford
there's already a portable way to do it which is probably more efficient.
Nitpick: Duff's device is portable
To go back to the Duff's Device example, almost all compilers will implement loop unrolling already
Even where the number of iterations is not known until runtime, as in Duff's Device?
I read Hacker's Delight a few months ago over a few good cigars and found it fascinating in its thoroughness, a la Knuth. I may not use ever use it daily, but it added to my knowledge, and I so recommend it at $40 US.
One interesting theorem on p.12 is "A function mapping words to words can be implemented with word-parallel add, subtract, and, or and not instructions if and only if each bit of the result depends only on bits at and to the right of each input operand."
This tells you, for instance, that there is no magic bit masking trick which will turn off the leftmost 1-bit in a word. If that interests you, you'll probably enjoy the book.
~Matt
"Tastes like poo!"
Vivian, from _The Young Ones_
Aww, c'mon! The moderators are smoking that $5 crack.
Try creating or renaming any file or your system to con.* * could be anything like .html .jpg .txt. The OS won't let you, it'll give an error. NT and 2K give different error mesasages. Under NT it just says the name is used already. Under 2K it says it's a reserved device name.
I found some copies here. I might get one.
Easy guys, I put my pants on one leg at a time. The difference is after I put on my pants I make gold records!
Technically, I believe base "e" (2.718...etc.) is the most efficent encoding scheme for numbers...... in terms of the overall tradeoffs between number-of-states-per-digit, vs. number-of-digits-required-to-encode. Good luck implementing this ;)
Converting decimal to binary and back again was relatively expensive so many commercial computers could work in decimal mode. The computer kept working in binary, it was just the numeric representation used. All that it meant was that the bytes were divided into two BCD nibbles, and numbers were represented as strings of 4-bit BCD digits.
See my journal, I write things there
Please explain in what sense non-existence is something "in the universe."
Shop as usual. And avoid panic buying.
Shouldn't all software be built with performance in mind? Personally, I think that many developers have taken a love to today's high speed CPUs as it allows them to practically ignore performance issues. While it is true that in some areas performance tweaking is still vital, such as server software and high-end gaming, it seems that most mundane software, such as office tools and other nominal is over bloated and slow. Granted, it isn't as important, perhaps, but its still annoying when on my Dual Athlon machine I have speed issues, like when moving my media player causes the movie to stall and skip. I still chuckle at the popularity of Phoenix, an apparently slimmed down and tweaked browser. Even with fewer features then Mozilla, it stands on its own just because its fast. Does anyone else feel that programming in general today has been sloppy and aimed more at getting more features then having a fast, stable program?
"A coward dies a thousand deaths, the brave but one."
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.
Whoever you are, you sure get around.
"Lawyers are for sucks."
- Doug McKenzie
That page is old, and not kept up to date. Try this one for some more exotic, well explained and up to date stuff.
Yep, that's what the book points out (that e is the most efficient base). However, he goes on to analyze the difference in efficiency between base 2 and bases 3 and e, and concludes that base 2 is more costly only by a factor of 1.062. (Yes, I have the book open in front of me as I type :-)
It's a nice book... most of the information only of practical use to people doing serious code tweaking, but of interest to anyone who codes.
Just you watch, as soon as he gets - he will start sucking the asses of eveyone to get back up.
I say keep the troll where they belong.
Truthfully - in today's world of cheap computing where there is more unused memory and idle CPU cycles than most users know what to do with, this book is much more a novelty than a practical guide. After all, how many programmers do bit-tweaking in Java these days? There may be the odd tidbit scattered throughout the book that may be truly useful but mostly one should savor the book for the mathematical insights and "tricks of the trade" the author lays out, undoubtedly accumulated from his many decades working with computers (From the days of "Real programmers" no doubt - and I don't mean the Pascal users ...)
I actually saw a recipe, and some of the young ladies where I work baked it, of a confection called Hacker's Delight. Twinkies with marshmallows, caramel, & chocolate melted together in a microwave. So sweet it made you gag.
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.
It is not polite to undermine the opinion of one that is so passionate about plagiarism. If dismiss it so easily it must be because you deep inside nurture some feelings of promoting piracy of copyrighted works.
And stop typing your messages from your VIC20. In the modern world we have at least 80 chars per line.
And just to show you, I will quote a random block of text that has nothing to do with him/it:
"The team will comprise of a range of inexperts taken from former staff at Jensen, Strathcarron and Marcos. Their collective expertise in the field of failure will be co-ordinated by beardy inventionator Sir Clive Sinclair. We rang Sir Clive for further comment but he had invented a new phone system for his house based around washing machine motors and squelchy rubber keys and it didn't seem to work properly. "
I may be missing the point here... but, in todays software world, shouldn't I be worried about coding reliable, and easily read code?
And then let my compiler read through my code and determine the most efficient way to turn it into assembly? I mean, I would rather be multiplying by 2 rather than bitshifting; and then let my compiler turn it into whatever it needs to in order to run the fastest.
In fact, I really wouldn't be surprised if many of the better compilers already do most of these tricks for us, and we don't even know it.
But then again, I can't say for sure, since I have not read the book