The Garbage Collection Handbook

内容简介：

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.

目录：

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