Also his earlier slim Writing Efficient Programs book. What this teaches you is how to think about efficiency from the top down with an emphasis on Algorithm and Language and hence useful to all programmers. Pair it with modern books on efficiency which deal mainly with compiler-level/OS-level/Processor-level performance techniques by Agner Fog, Fedor Pikus etc. and you get a complete picture.
>Also his earlier slim Writing Efficient Programs book.
Yes, that's a really good one. I own a copy of it, bought years ago, and have read it pretty much cover to cover. Have also applied the guidelines in it, some.
the war stories briefly mentioned in the footnotes of the book, are very interesting too.
for example, one of them is about a team that speeded up the run time of a quicksort implementation on a supercomputer by a factor of a thousand times (yes, times, IIRC, not percent), by doing successive optimisations at many layers of the stack, from high level algorithms and data structures, down to the hardware.
Algorithms and Data Structures always go together (like Yin/Yang) and hence i did not spell that out. At the time the book was written Structured Programming techniques and control structures were somewhat new and people wondered whether it was possible to really write efficient programs using these in a high-level language. In the preface/introduction itself Bentley points this out and says he is looking at efficiency at the "Design Level"(various) and thus you have chapters like "Modifying Data Structures" (Time vs. Space) and "Modifying Code" (mainly Loop rules) which show one how to transform code in the same language to a better form (we know this today as helping the compiler generate better object code). As he points out in the book; people forget the constant factors in big-oh and much efficiency can be had by tweaking this.
This is particularly true nowadays since there are so many interpreted/vm-based/jit-compiled/scripting languages where with some "under the hood" knowledge you can get good performance just by source level transformations.
