|
A book by Jon Bentley [1], "Writing Efficient Programs", is very good for this area. It is out of print, probably, was written many years ago, but IMO is still likely to be very useful for a _wide_ range (not all) of performance issues. This is because he approaches the problem both somewhat scientifically, as well as gives many rules of optimization that can be applied in various common situations. Lots of code examples in a language similar to (or actually) Pascal (forget which, read it some years ago), but that should not be a problem for any competent programmer. Many real life war stories of performance tuning throughout the book. In some of his examples he manages to improve some initial code (e.g. the travelling salesman problem) by one or more orders of magnitude (1 order being 10X), via repeated application of various performance rules to succeeding versions of the same code, optimized by one rule at a time. One of his war stories is about a team that optimized a quicksort (?) algorithm on a supercomputer by either 100,000 times or 1 million times (for speed) over the initial version, by working at several levels of the stack, including from algorithms through code down to hardware. Great story. At the end of the book he also gives all the rules or techniques again in a summary form (each rule is illustrated with one or more case studies in the body of the book), along with guidelines on when and when not to apply each. You might be able to get a used copy of the book on Amazon even though it is out of print. Code hoisting, common sub-expression elimination, loop unrolling (with a good binary search example from Knuth), trading space for time and vice versa, using interpreters (to save space - he gives an example of someone who wrote an interpreter for an interpreter in a space-constrained old IBM machine environment, resulting in huge saving of space) - those are some of his techniques / war stories that I remember off the top of my head. Really worth reading, IMO. He is also the author of Programming Pearls and More Programming Pearls - also pretty good books. I just looked up his Wikipedia page again: http://en.wikipedia.org/wiki/Jon_Bentley and saw these excerpts (among other stuff): Jon Louis Bentley (born February 20, 1953 in Long Beach, California)[1] is a researcher in the field of computer science. He is credited with the invention of the k-d tree.
...
After receiving his Ph.D., he joined the faculty at Carnegie Mellon University as an assistant professor of computer science and mathematics.
...
At CMU, his students included Brian Reid, John Ousterhout (inventor of Tcl/Tk), Jeff Eppinger, Joshua Bloch, and James Gosling (inventor of Java), and he was one of Charles Leiserson's advisors. Later, Bentley moved to Bell Laboratories.
...
He wrote the Programming Pearls column for the Communications of the ACM magazine, and later collected the articles into two books of the same name.
...
Bentley received the Dr. Dobb's Excellence in Programming award in 2004. |
http://googleresearch.blogspot.in/2006/06/extra-extra-read-a...
In the book Writing Efficient Programs, Bentley talks about teaching a class of experienced programmers (the class was about algorithms), in which he asked all of them to write a binary search algorithm. Then he showed that almost all of them had bugs. The above post is by Joshua Block (of Sun, author of Effective Java, who was one of the students on that class), and the post says that Bentley's own program for the search also had a bug - found later.
Acording to Bloch, Bentley's bug escaped detection for two decades, and further, Bloch's code for the same binary search, written for the JDK (for java.util.Arrays), also had a bug that was detected nine years later.