Epilog to The Second Edition

Some traditions are continued for their inherent quality. Others persist anyway.

Q: Welcome back; it’s been a long time.

A: Fourteen years.

Q: Let’s start where we did before. Why a new edition of the book?

A: I like the book, a lot. It was fun to write, and the readers have been very kind over the years. The principles in the book have stood the test of time, but many examples in the first edition were woefully out of date. Modern readers can’t relate to a “huge” computer that has a half-megabyte of main memory.

Q: So what did you change in this edition?

A: Pretty much what I said I changed in the preface. Don’t you guys prepare before these interviews?

Q: Oops — sorry. I see that you talk there about how the code for this book is available at the web site.

A: Writing that code was the most fun that I had in working on this edition. I implemented most of the programs in the first edition, but mine were the only eyes to see the real code. For this edition I wrote about 2500 lines of C and C++, to be shown to the whole world.

Q: You call that code ready for public view? I’ve read some of it; what dreadful style! Microscopic variable names, weird function definitions, global variables that should be parameters, and the list goes on. Aren’t you embarrassed to let real software engineers see the code?

A: The style I used can indeed prove fatal in large software projects. This book, however, is not a large software project. It’s not even a large book. Solution 5.1 describes the terse coding style and why I chose it. Had I wanted to write a thousand-page book, I would have adopted a lengthier coding style.

Q: Speaking of long code, your sort, cpp program measures the C Standard Library qsort, the C++ Standard Template Library sort, and several hand-made Quicksorts. Can’t you make up your mind? Should a programmer use library functions or build code from scratch?

A: Tom Duff gave the best answer to that question: “Whenever possible, steal code.” Libraries are great; use them whenever they do the job. Start with your system library, then search other libraries for appropriate functions. In any engineering activity, though, not all artifacts can be all things to all customers. When the library functions don’t measure up, you may have to build your own. I hope that the pseudocode fragments in the book (and the real code on the web site) will prove a useful starting point for programmers who have to write their own functions. I think that the scaffolding and the experimental approach of this book will help those programmers to evaluate a variety of algorithms and choose the best one for their application.

Q: Apart from the public code and updating some stories, what is really new in this edition?

A: I’ve tried to confront code tuning in the presence of caches and instruction-level parallelism. At a larger level, the three new columns reflect three major changes that pervade this edition: Column 5 describes real code and scaffolding, Column 13 gives details on data structures, and Column 15 derives advanced algorithms. Most of the ideas in the book have appeared in print before, but the cost model for space in Appendix 3 and the Markov-text algorithm in Section 15.3 are presented here for the first time. The new Markov-text algorithm compares quite favorably to the classic algorithm described by Kernighan and Pike.

Q: There you go with more Bell Labs people. The last time we talked, you were enthusiastic about the place, but you had only been there a few years. Lots has changed at the Labs in the last 14 years; what do you now think about the place and the changes?

A: When I wrote the first columns in the book, Bell Labs was part of the Bell System. When the first edition was published, we were part of AT&T; now we are part of Lucent Technologies. The companies, the telecommunications industry, and the field of computing have all changed dramatically in that period. Bell Labs has kept up with those changes, and has often led the way. I came to the Labs because I enjoy balancing the theoretical and the applied, because I want to build products and write books. The pendulum has swung back and forth during my years at the Labs, but my management has always encouraged a wide range of activities.

A reviewer of the first edition of this book wrote “Bentley’s everyday working environment is a programming nirvana. He is a Member of Technical Staff at Bell Labs in Murray Hill, New Jersey, has immediate access to cutting-edge hardware and software technology, and stands in line at the cafeteria with some of the most brilliant software developers in the world.” Bell Labs is still that kind of place.

Q: Nirvana every single day of the week?

A: Nirvana many days, and pretty darn nice the others.