The Garbage Collection Handbook The Art of Automatic Memory Management

Published in 1996, Richard Jones’s Garbage Collection was a milestone in the area of automatic memory management. The field has grown considerably since then, sparking a need for an updated look at the latest state-of-the-art developments. The Garbage Collection Handbook: The Art of Automatic Memory Management brings together a wealth of knowledge gathered by automatic memory management researchers and developers over the past fifty years. The authors compare the most important approaches and state-of-the-art techniques in a single, accessible framework. The book addresses new challenges to garbage collection made by recent advances in hardware and software. It explores the consequences of these changes for designers and implementers of high performance garbage collectors. Along with simple and traditional algorithms, the book covers parallel, incremental, concurrent, and real-time garbage collection. Algorithms and concepts are often described with pseudocode and illustrations. The nearly universal adoption of garbage collection by modern programming languages makes a thorough understanding of this topic essential for any programmer. This authoritative handbook gives expert insight on how different collectors work as well as the various issues currently facing garbage collectors. Armed with this knowledge, programmers can confidently select and configure the many choices of garbage collectors. Web ResourceThe book’s online bibliographic database at www.gchandbook.org includes over 2,500 garbage collection-related publications. Continually updated, it contains abstracts for some entries and URLs or DOIs for most of the electronically available ones. The database can be searched online or downloaded as BibTeX, PostScript, or PDF. E-bookThis edition enhances the print version with copious clickable links to algorithms, figures, original papers and definitions of technical terms. In addition, each index entry links back to where it was mentioned in the text, and each entry in the bibliography includes links back to where it was cited.

Introduction Explicit deallocation Automatic dynamic memory management Comparing garbage collection algorithms A performance disadvantage? Experimental methodology Terminology and notation Mark-Sweep Garbage Collection The mark-sweep algorithm The tricolor abstraction Improving mark-sweep Bitmap marking Lazy sweeping Cache misses in the marking loop Issues to consider Mark-Compact Garbage Collection Two-finger compaction The Lisp 2 algorithm Threaded compaction One-pass algorithms Issues to consider Copying Garbage Collection Semispace copying collectionTraversal order and locality Issues to consider Reference Counting Advantages and disadvantages of reference counting Improving efficiency Deferred reference counting Coalesced reference counting Cyclic reference counting Limited-field reference counting Issues to consider Comparing Garbage Collectors Throughput Pause time Space Implementation Adaptive systems A unified theory of garbage collection AllocationSequential allocation Free-list allocationFragmentation Segregated-fits allocationCombining segregated-fits with first-, best-, and next-fitAdditional considerationsAllocation in concurrent systems Issues to consider Partitioning the Heap Terminology Why to partitionHow to partition When to partition Generational Garbage Collection Example Measuring time Generational hypotheses Generations and heap layout Multiple generations Age recordingAdapting to program behaviorInter-generational pointersSpace management Older-first garbage collection Beltway Analytic support for generational collection Issues to consider Abstract generational garbage collection Other Partitioned Schemes Large object spaces Topological collectors Hybrid mark-sweep, copying collectors Bookmarking garbage collection Ulterior reference counting Issues to consider Run-Time InterfaceInterface to allocation Finding pointersObject tables References from external code Stack barriers GC safe points and mutator suspension Garbage collecting code Read- and write-barriersManaging address space Applications of virtual memory page protectionChoosing heap size Issues to consider Language-Specific Concerns FinalizationWeak referencesIssues to consider Concurrency PreliminariesHardwareHardware memory consistency models Hardware primitives Progress guarantees Notation used for concurrent algorithmsMutual exclusion Work sharing and termination detectionConcurrent data structuresTransactional memoryIssues to consider Parallel Garbage Collection Is there sufficient work to parallelize? Load balancing Synchronization Taxonomy Parallel marking Parallel copying Parallel sweeping Parallel compaction Issues to consider Concurrent Garbage CollectionCorrectness of concurrent collectionBarrier techniques for concurrent collectionIssues to consider Concurrent Mark-Sweep Initialization Termination Allocation Concurrent marking and sweeping On-the-fly markingAbstract concurrent collection Issues to consider Concurrent Copying and Compaction Mostly concurrent copying: Baker’s algorithm Brooks’ indirection barrier Self-erasing read barriers Replication copying Multi-version copying Sapphire Concurrent compactionIssues to consider Concurrent Reference Counting Simple reference counting revisited Buffered reference counting Concurrent, cyclic reference counting Taking a snapshot of the heap Sliding views reference countingIssues to consider Real-Time Garbage CollectionReal-time systems Scheduling real-time collection Work-based real-time collectionSlack-based real-time collectionTime-based real-time collection: MetronomeCombining scheduling approaches: Tax-and-SpendControlling fragmentationIssues to consider Glossary Bibliography Index

Richard Jones is a professor of computer systems in the School of Computing at the University of Kent, Canterbury. He earned a B.A. in mathematics from Oxford University and an M.Sc. in computer science from the University of Kent. He spent a few years teaching at school and college before returning to higher education at the University of Kent. Antony Hosking is an associate professor in the Department of Computer Science at Purdue University. He earned a B.Sc. in mathematical sciences from the University of Adelaide, Australia, an M.Sc. in computer science from the University of Waikato, New Zealand, and a Ph.D. in computer science from the University of Massachusetts. His work is in the area of programming language design and implementation, with specific interests in database and persistent programming languages, object-oriented database systems, dynamic memory management, compiler optimizations, and architectural support for programming languages and applications. Eliot Moss is a professor in the Department of Computer Science at the University of Massachusetts Amherst. He earned a B.S.E.E., an M.S.E.E., and a Ph.D. in computer science from the Massachusetts Institute of Technology. After four years of military service, Dr. Moss joined the faculty at the University of Massachusetts Amherst. He works in the area of programming languages and their implementation and has built garbage collectors since 1978. In addition to his research on automatic memory management, he is known for his work on persistent programming languages, virtual machine implementation, and transactional memory. He worked with IBM researchers to license the Jikes RVM Java virtual machine for academic research, which eventually led to its release as an open source project.