Garbage collection is “the automatic reclamation of heap allocated storage after its last use by a program.” Garbage collection is a unique topic within computer science, since it is a well-known problem that is closely related to the architecture of computer systems, the virtual memory management of operating systems, the design of programming languages, and the algorithms and data structures of software systems. It has a rich history, having been addressed by Edsger Dijkstra, Donald Knuth, and Marvin Minsky, among many others.
Functional, logic, and pure object-oriented programming languages have traditionally used garbage collection to manage heap storage automatically. On the other hand, imperative programming languages have traditionally left it to the programmer to manage heap storage explicitly. One of the issues that makes garbage collection particularly relevant today is that C++ does not provide garbage collection. One of the late chapters of this book examines techniques for incorporating a garbage collector into a C++ programming environment.
The book is a comprehensive survey and evaluation of algorithms for, and implementations of, garbage collection. Early chapters address three classical approaches to garbage collection, which provide the foundation for algorithms currently in use: reference counting, mark-sweep, and copying. Another chapter examines mark-compact algorithms, which compact the heap. Further chapters cover the two general approaches to garbage collection that provide the bases for much of the current research: generational garbage collection and incremental (concurrent) garbage collection. Two chapters are devoted to the particular issues that must be addressed by garbage collection for C and C++ and to algorithms designed for these languages. The final two chapters deal with the effects of garbage collection on cache performance and with distributed garbage collection.
Each chapter provides proper motivation for the class of algorithms and techniques addressed. The algorithms and their variations are carefully described using extensive illustrations and pseudocode. Each chapter has a section entitled “Issues to Consider,” which evaluates the algorithms introduced in terms of, for example, the handling of cyclic data structures, the processing cost, the space overhead, and the extent of interruption of the client’s program. The authors compare the performance of various algorithms, highlighting the applications and programming languages for which they are well suited. They also address the performance of the algorithms in terms of their effects on virtual memory and cache management.
Each chapter closes with a section entitled “Notes,” in which the authors point to the primary sources for the algorithms and performance evaluations. An extensive bibliography lists more than 500 items. Furthermore, Jones maintains a comprehensive database of references to garbage collection on the Internet.
I found several minor, but annoying, grammatical errors in the text, but the book is generally well organized and the exposition is clear. Although the authors repeat observations and evaluations of algorithms in different contexts, they do so appropriately and usually refer to other sections of the book where they are repeated.
The book will serve as an excellent tutorial on garbage collection and as a starting point for research on new techniques or variations on existing techniques. Garbage collection will continue to be an important problem in the building of software systems. The techniques used must be reexamined in the light of every advance in hardware, operating systems, and programming languages.
