Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
The garbage collection handbook : the art of automatic memory management
Jones R., Hosking A., Moss E., Chapman & Hall/CRC, Boca Raton, FL, 2011. 511 pp. Type: Book (978-1-420082-79-1)
Date Reviewed: Feb 21 2012

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.

Reviewer:  J. H. Davenport Review #: CR139891 (1207-0664)
1) Tofte, M.; Birkedahl, L.; Elsman, M.; Hallenberg, N. A retrospective on region-based memory management. Higher-Order and Symbolic Computation 17, (2004), 245–265.
2) Jones, R.; Lins, R. Garbage collection: algorithms for automatic dynamic memory management. John Wiley & Sons Ltd., Chichester, UK, 1996.
3) Fitzgerald, R.; Tarditi, D. The case for profile-directed selection of garbage collectors. SIGPLAN Notices 36, 1(2000), 111–120.
4) Dijkstra, E. W.; Lamport, L.; Martin, A. J.; Scholten, C. S.; Steffens, E. F. H. On-the-fly garbage collection: an exercise in cooperation. Comm. ACM 21, (1978), 965–975.
Bookmark and Share
  Reviewer Selected
Featured Reviewer
Memory Management (Garbage Collection) (D.3.4 ... )
Reference (A.2 )
Would you recommend this review?
Other reviews under "Memory Management (Garbage Collection)": Date
Hardware support for real-time embedded multiprocessor system-on-a-chip memory management
Shalan M., Vincent J I.  Hardware/software codesign (Proceedings of the tenth international symposium, Estes Park, Colorado, May 6-8, 2002)79-84, 2002. Type: Proceedings
Jan 30 2004
Memory as a programming concept in C and C++
Franek F., Cambridge University Press, New York, NY, 2003.  250, Type: Book (9780521520430)
Apr 30 2004
Interprocedural pointer alias analysis
Hind M., Burke M., Carini P., Choi J. ACM Transactions on Programming Languages and Systems 21(4): 848-894, 1999. Type: Article
Mar 1 2000

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy