This book is an excellent review of the state of the art in garbage collection, which--in the two decades ending in 2009--has moved from a linguistic oddity to a near-essential component of computer languages. Chapters 2 through 5 discuss basic sequential garbage collection techniques, including a useful discussion on pages 49 through 53 about the interaction of copying and locality of reference. Chapter 6 compares the techniques of the previous four chapters. Chapter 7 discusses allocation and fragmentation, and chapters 8 through 10 discuss generational and partitioned garbage collection. Chapter 11 provides a much-needed discussion on interfacing garbage collection with the runtime system, while chapter 12 deals with the relation between garbage collection and programming languages, including such issues as weak pointers. Chapters 13 through 18 describe parallel and concurrent garbage collection, and chapter 19 describes real-time garbage collection. The book does not cover distributed garbage collection; the authors’ rationale, with which I largely agree, is that there has been little research on this in the last decade. The book also does not cover region allocation and collection [1] as used in, for example, real-time Java (and, I would add, many computer algebra systems); here, the authors’ rationale is that these tend not to be fully automatic.

Though in no sense simply a second edition of Jones and Lins’s excellent book [2], this book follows in its predecessor’s line: it is authoritative without being dictatorial. This is an important point, as there is no “right way” to do garbage collection. As the authors point out on page 5, Fitzgerald and Tarditi [3] show that, for every collector, there is at least one benchmark that would run at least 15 percent faster with a different collector. In addition, garbage collection measurement is difficult, as the authors discuss on page 10. Anyone contemplating measuring their garbage collector(s) or deciding which to use on the basis of measurement should read this section and the referenced papers. The note on page 203 is also relevant: “For each [hardware] platform, a different technique may be best.”

The authors point out that, to avoid becoming a bottleneck, garbage collection has to become as parallel as garbage creation, an important observation as multicore systems become universal (hence, chapter 14 on parallel collection). The discussion on copying, locality, and affinity (objects that are likely to be touched by the same processor should be placed together--a refinement on traditional locality) is not conclusive. This reflects the state of research in the area and, I suspect, the difficulty of getting good experimental data. However, the authors have done the field a service by codifying terminology: “parallel” means that all garbage-creating work stops while the collector runs in parallel on as many threads as practicable.

Beyond parallel garbage collection, there is concurrent garbage collection, in which collection and creation take place at the same time, generally on threads devoted to either creation or collection. Even defining concurrent garbage collection correctness is difficult, though the authors have done an excellent job on pages 20 through 21 of building on formal definitions, notably Dijkstra and others’ tricolor abstraction [4]. The reader who finds formality unnecessary in the sequential case should know that formality is vital in the concurrent case, in which intuition is more fragile. Intuition does not work even for concurrent reference counting, which deserves--and gets--its own chapter (18). As the authors point out (p. 364), “the problem does not [only] lie in Write,” and, furthermore, “single memory location primitives are insufficient to guarantee safety.”

If anything is disappointing about this book, it is the absence of a global conclusion or collected list of research issues. Each chapter has a good list of “issues to consider,” but this is not quite the same thing.