The Garbage Collection Handbook: The Art of Automatic Memory Management (Hardback) book cover

The Garbage Collection Handbook

The Art of Automatic Memory Management

By Richard Jones, Antony Hosking, Eliot Moss

© 2011 – Chapman and Hall/CRC (Professional (DRM-Free))

511 pages | 79 B/W Illus.

Request Inspection Copy
Purchasing Options:$ = USD
Hardback: 9781420082791
pub: 2011-08-17
SAVE ~$19.79
$98.95
$79.16
x


FREE Standard Shipping!

Description

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 Resource

The 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-book

This 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.

Reviews

The Garbage Collection Handbook is the most up-to-date, detailed, and exhaustive collation and description of the current state of the art of Garbage Collection and Automatic Memory Management available today. It is an imperative reference book for anyone working in the field, and I would consider it the textbook of reference covering GC 101 thru GC 530 course levels, if such courses were given at universities worldwide. As CTO of Azul Systems and co-creator of multiple modern concurrent collectors, Richard Jones’ previous Garbage Collection book was indispensable to my work over the years. The Garbage Collection Handbook has immediately taken its place. Each of our GC engineers has a copy on their desk.

—Gil Tene, Chief Technical Officer and co-founder of Azul Systems

In a field replete with ephemera, this book, just like its predecessor, stands as a monumental work that will last for decades.

—Dr. Mario Wolczko, Research Director, Oracle Labs

Table of Contents

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 collection

Traversal 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

Allocation

Sequential allocation

Free-list allocation

Fragmentation

Segregated-fits allocation

Combining segregated-fits with first-, best-, and next-fit

Additional considerations

Allocation in concurrent systems

Issues to consider

Partitioning the Heap

Terminology

Why to partition

How to partition

When to partition

Generational Garbage Collection

Example

Measuring time

Generational hypotheses

Generations and heap layout

Multiple generations

Age recording

Adapting to program behavior

Inter-generational pointers

Space 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 Interface

Interface to allocation

Finding pointers

Object tables

References from external code

Stack barriers

GC safe points and mutator suspension

Garbage collecting code

Read- and write-barriers

Managing address space

Applications of virtual memory page protection

Choosing heap size

Issues to consider

Language-Specific Concerns

Finalization

Weak references

Issues to consider

Concurrency Preliminaries

Hardware

Hardware memory consistency models

Hardware primitives

Progress guarantees

Notation used for concurrent algorithms

Mutual exclusion

Work sharing and termination detection

Concurrent data structures

Transactional memory

Issues 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 Collection

Correctness of concurrent collection

Barrier techniques for concurrent collection

Issues to consider

Concurrent Mark-Sweep

Initialization

Termination

Allocation

Concurrent marking and sweeping

On-the-fly marking

Abstract 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 compaction

Issues 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 counting

Issues to consider

Real-Time Garbage Collection

Real-time systems

Scheduling real-time collection

Work-based real-time collection

Slack-based real-time collection

Time-based real-time collection: Metronome

Combining scheduling approaches: Tax-and-Spend

Controlling fragmentation

Issues to consider

Glossary

Bibliography

Index

About the Authors

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.

About the Series

Chapman & Hall/CRC Applied Algorithms and Data Structures series

Learn more…

Subject Categories

BISAC Subject Codes/Headings:
COM051010
COMPUTERS / Programming Languages / General
COM051300
COMPUTERS / Programming / Algorithms
MAT000000
MATHEMATICS / General