Programming Pearls (ACM Press) [ペーパーバック]

What Bentley does in each of these columns is take some part of the field of programming--something that every one of us will have run into at some point in our work--and dig underneath it to reveal the part of the problem that is permanent; that doesn't change from language to language. The first two parts cover problem definition, algorithms, data structures, program verification, and efficiency (performance, code tuning, space tuning); the third part applies the lessons to example pseudocode, looking at sorting, searching, heaps, and an example spellchecker.

Bentley writes clearly and enthusiastically, and the columns are a pleasure to read. But the reason so many people love this book is not for the style, it's for the substance--you can't read this book and not come away a better programmer. Inefficiency, clumsiness, inelegance and obscurity will offend you just a little more after you've read it.

It's hard to pick a favourite piece, but here's one nice example from the algorithm design column that shows how little the speed of your Pentium matters if you don't know what you're doing. Bentley presents a particular problem (the details don't matter) and multiple different ways to solve it, calculating the relationship between problem size and run time for each algorithm. He gives, among others, a cubic algorithm (run time equal to a constant, C, times the cube of the problem size, N--i.e. t ~ CN^3), and a linear algorithm with constant K (t ~ KN). He then implemented them both: the former in fine-tuned FORTRAN on a Cray-1 supercomputer; the latter in BASIC on a Radio Shack TRS-80. The constant factors were as different as they could be, but with increasing problem size the TRS-80 eventually has to catch up--and it does. He gives a table showing the results: for a problem size of 1000, the Cray takes three seconds to the TRS-80's 20 seconds; but for a problem size of 1,000,000, the TRS-80 takes five and a half hours, whereas the Cray would take 95 years.

The book is informative, entertaining, and will painlessly make you a better programmer. What more can you ask?

Suppose, for the sake of argument, that you have a binary search that's holding up your loop. Or your Huffman coding just isn't snappy enough? "How is that possible?", you might say, fresh out of computer-science 201, "Didn't we just prove these algorithms are optimal?" Well yes, asymptotically up to an arbitrary constant multiplier. But this is the real world, and your code needs to go faster. If this sounds like your predicament, pull up a chair and read "Programming Pearls"; if it's not, you might wonder what all the fuss is about.

Next, fire up your favorite hardware (Sparc or x86 or PowerPC), favorite language (Perl, Java, or even C), favorite release of that language, along with your favorite interpreter or compiler (Hotspot or standard? GCC or Visual C++). And you'll need a profiler; might as well treat yourself to a good one if you're serious. Then fire up your code with a representative range realistic test data and observe what happens. Function by function, byte by byte. Then try to be as clever as Bentley in (a) figuring out why, (b) trying a range of alternatives, and (c) making it all go faster with minor tuning. Typically, you'll find a single bottleneck taking an order of magnitude more time than everything else, and work on that. Repeat until fast enough.

As well as this simple, yet surprisingly effective and realistic methodology, Bentley provides a range of concrete tips on making things go faster, from tweaking data structures to unfolding loops (especially precomputing low-order cases) to using accumulators and caching, all with an eye to underlying memory, communication and CPU resources.

Real code that has to run fast, like the code that we write at my current company for signal processing, speech recognition and speech synthesis, typically looks like the end-product of Bentley's refactorings. And it gets that way following exactly the path he lays out: analyze the problem, choose the right algorithm (or the right few to evaluate), and then tune it up using profiling.

"Programming Pearls" is the beginning of the road. You will need to look elsewhere for topics such as compression for memory saving, numerical algorithms, effective concurrency and memory sharing, efficient buffered I/O, garbage collection, and the wide range of dynamic programming and heuristic techniques.