The Garbage Collection Handbook

The Garbage Collection Handbook

by Richard Jones, Antony Hosking, Eliot Moss
Released September 2016
Publisher(s): Chapman and Hall/CRC
ISBN: 9781315388007

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

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

Table of contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright Page
  5. Dedication
  6. Table of Contents
  7. List of Algorithms
  8. List of Figures
  9. List of Tables
  10. Preface
  11. Acknowledgements
  12. Authors
  13. 1 Introduction
    1. 1.1 Explicit deallocation
    2. 1.2 Automatic dynamic memory management
    3. 1.3 Comparing garbage collection algorithms
      1. Safety
      2. Throughput
      3. Completeness and promptness
      4. Pause time
      5. Space overhead
      6. Optimisations for specific languages
      7. Scalability and portability
    4. 1.4 A performance disadvantage?
    5. 1.5 Experimental methodology
    6. 1.6 Terminology and notation
      1. The heap
      2. The mutator and the collector
      3. The mutator roots
      4. References, fields and addresses
      5. Liveness, correctness and reachability
      6. Pseudo-code
      7. The allocator
      8. Mutator read and write operations
      9. Atomic operations
      10. Sets, multisets, sequences and tuples
  14. 2 Mark-sweep garbage collection
    1. 2.1 The mark-sweep algorithm
    2. 2.2 The tricolour abstraction
    3. 2.3 Improving mark-sweep
    4. 2.4 Bitmap marking
    5. 2.5 Lazy sweeping
    6. 2.6 Cache misses in the marking loop
    7. 2.7 Issues to consider
      1. Mutator overhead
      2. Throughput
      3. Space usage
      4. To move or not to move?
  15. 3 Mark-compact garbage collection
    1. 3.1 Two-finger compaction
    2. 3.2 The Lisp 2 algorithm
    3. 3.3 Threaded compaction
    4. 3.4 One-pass algorithms
    5. 3.5 Issues to consider
      1. Is compaction necessary?
      2. Throughput costs of compaction
      3. Long-lived data
      4. Locality
      5. Limitations of mark-compact algorithms
  16. 4 Copying garbage collection
    1. 4.1 Semispace copying collection
      1. Work list implementations
      2. An example
    2. 4.2 Traversal order and locality
    3. 4.3 Issues to consider
      1. Allocation
      2. Space and locality
      3. Moving objects
  17. 5 Reference counting
    1. 5.1 Advantages and disadvantages of reference counting
    2. 5.2 Improving efficiency
    3. 5.3 Deferred reference counting
    4. 5.4 Coalesced reference counting
    5. 5.5 Cyclic reference counting
    6. 5.6 Limited-field reference counting
    7. 5.7 Issues to consider
      1. The environment
      2. Advanced solutions
  18. 6 Comparing garbage collectors
    1. 6.1 Throughput
    2. 6.2 Pause time
    3. 6.3 Space
    4. 6.4 Implementation
    5. 6.5 Adaptive systems
    6. 6.6 A unified theory of garbage collection
      1. Abstract garbage collection
      2. Tracing garbage collection
      3. Reference counting garbage collection
  19. 7 Allocation
    1. 7.1 Sequential allocation
    2. 7.2 Free-list allocation
      1. First-fit allocation
      2. Next-fit allocation
      3. Best-fit allocation
      4. Speeding free-list allocation
    3. 7.3 Fragmentation
    4. 7.4 Segregated-fits allocation
      1. Fragmentation
      2. Populating size classes
    5. 7.5 Combining segregated-fits with first-, best- and next-fit
    6. 7.6 Additional considerations
      1. Alignment
      2. Size constraints
      3. Boundary tags
      4. Heap parsability
      5. Locality
      6. Wilderness preservation
      7. Crossing maps
    7. 7.7 Allocation in concurrent systems
    8. 7.8 Issues to consider
  20. 8 Partitioning the heap
    1. 8.1 Terminology
    2. 8.2 Why to partition
      1. Partitioning by mobility
      2. Partitioning by size
      3. Partitioning for space
      4. Partitioning by kind
      5. Partitioning for yield
      6. Partitioning for responsiveness
      7. Partitioning for locality
      8. Partitioning by thread
      9. Partitioning by availability
      10. Partitioning by mutability
    3. 8.3 How to partition
    4. 8.4 When to partition
  21. 9 Generational garbage collection
    1. 9.1 Example
    2. 9.2 Measuring time
    3. 9.3 Generational hypotheses
    4. 9.4 Generations and heap layout
    5. 9.5 Multiple generations
    6. 9.6 Age recording
      1. En masse promotion
      2. Aging semispaces
      3. Survivor spaces and flexibility
    7. 9.7 Adapting to program behaviour
      1. Appel-style garbage collection
      2. Feedback controlled promotion
    8. 9.8 Inter-generational pointers
      1. Remembered sets
      2. Pointer direction
    9. 9.9 Space management
    10. 9.10 Older-first garbage collection
    11. 9.11 Beltway
    12. 9.12 Analytic support for generational collection
    13. 9.13 Issues to consider
    14. 9.14 Abstract generational garbage collection
  22. 10 Other partitioned schemes
    1. 10.1 Large object spaces
      1. The Treadmill garbage collector
      2. Moving objects with operating system support
      3. Pointer-free objects
    2. 10.2 Topological collectors
      1. Mature object space garbage collection
      2. Connectivity-based garbage collection
      3. Thread-local garbage collection
      4. Stack allocation
      5. Region inferencing
    3. 10.3 Hybrid mark-sweep, copying collectors
      1. Garbage-First
      2. Immix and others
      3. Copying collection in a constrained memory space
    4. 10.4 Bookmarking garbage collection
    5. 10.5 Ulterior reference counting
    6. 10.6 Issues to consider
  23. 11 Run-time interface
    1. 11.1 Interface to allocation
      1. Speeding allocation
      2. Zeroing
    2. 11.2 Finding pointers
      1. Conservative pointer finding
      2. Accurate pointer finding using tagged values
      3. Accurate pointer finding in objects
      4. Accurate pointer finding in global roots
      5. Accurate pointer finding in stacks and registers
      6. Accurate pointer finding in code
      7. Handling interior pointers
      8. Handling derived pointers
    3. 11.3 Object tables
    4. 11.4 References from external code
    5. 11.5 Stack barriers
    6. 11.6 GC-safe points and mutator suspension
    7. 11.7 Garbage collecting code
    8. 11.8 Read and write barriers
      1. Engineering
      2. Precision of write barriers
      3. Hash tables
      4. Sequential store buffers
      5. Overflow action
      6. Card tables
      7. Crossing maps
      8. Summarising cards
      9. Hardware and virtual memory techniques
      10. Write barrier mechanisms: in summary
      11. Chunked lists
    9. 11.9 Managing address space
    10. 11.10 Applications of virtual memory page protection
      1. Double mapping
      2. Applications of no-access pages
    11. 11.11 Choosing heap size
    12. 11.12 Issues to consider
  24. 12 Language-specific concerns
    1. 12.1 Finalisation
      1. When do finalisers run?
      2. Which thread runs a finaliser?
      3. Can finalisers run concurrently with each other?
      4. Can finalisers access the object that became unreachable?
      5. When are finalised objects reclaimed?
      6. What happens if there is an error in a finaliser?
      7. Is there any guaranteed order to finalisation?
      8. The finalisation race problem
      9. Finalisers and locks
      10. Finalisation in particular languages
      11. For further study
    2. 12.2 Weak references
      1. Additional motivations
      2. Supporting multiple pointer strengths
      3. Using Phantom objects to control finalisation order
      4. Race in weak pointer clearing
      5. Notification of weak pointer clearing
      6. Weak pointers in other languages
    3. 12.3 Issues to consider
  25. 13 Concurrency preliminaries
    1. 13.1 Hardware
      1. Processors and threads
      2. Interconnect
      3. Memory
      4. Caches
      5. Coherence
      6. Cache coherence performance example: spin locks
    2. 13.2 Hardware memory consistency
      1. Fences and happens-before
      2. Consistency models
    3. 13.3 Hardware primitives
      1. Compare-and-swap
      2. Load-linked/store-conditionally
      3. Atomic arithmetic primitives
      4. Test then test-and-set
      5. More powerful primitives
      6. Overheads of atomic primitives
    4. 13.4 Progress guarantees
      1. Progress guarantees and concurrent collection
    5. 13.5 Notation used for concurrent algorithms
    6. 13.6 Mutual exclusion
    7. 13.7 Work sharing and termination detection
      1. Rendezvous barriers
    8. 13.8 Concurrent data structures
      1. Concurrent stacks
      2. Concurrent queue implemented with singly linked list
      3. Concurrent queue implemented with array
      4. A concurrent deque for work stealing
    9. 13.9 Transactional memory
      1. What is transactional memory?
      2. Using transactional memory to help implement collection
      3. Supporting transactional memory in the presence of garbage collection
    10. 13.10 Issues to consider
  26. 14 Parallel garbage collection
    1. 14.1 Is there sufficient work to parallelise?
    2. 14.2 Load balancing
    3. 14.3 Synchronisation
    4. 14.4 Taxonomy
    5. 14.5 Parallel marking
      1. Processor-centric techniques
    6. 14.6 Parallel copying
      1. Processor-centric techniques
      2. Memory-centric techniques
    7. 14.7 Parallel sweeping
    8. 14.8 Parallel compaction
    9. 14.9 Issues to consider
      1. Terminology
      2. Is parallel collection worthwhile?
      3. Strategies for balancing loads
      4. Managing tracing
      5. Low-level synchronisation
      6. Sweeping and compaction
      7. Termination
  27. 15 Concurrent garbage collection
    1. 15.1 Correctness of concurrent collection
      1. The tricolour abstraction, revisited
      2. The lost object problem
      3. The strong and weak tricolour invariants
      4. Precision
      5. Mutator colour
      6. Allocation colour
      7. Incremental update solutions
      8. Snapshot-at-the-beginning solutions
    2. 15.2 Barrier techniques for concurrent collection
      1. Grey mutator techniques
      2. Black mutator techniques
      3. Completeness of barrier techniques
      4. Concurrent write barrier mechanisms
      5. One-level card tables
      6. Two-level card tables
      7. Reducing work
    3. 15.3 Issues to consider
  28. 16 Concurrent mark-sweep
    1. 16.1 Initialisation
    2. 16.2 Termination
    3. 16.3 Allocation
    4. 16.4 Concurrent marking and sweeping
    5. 16.5 On-the-fly marking
      1. Write barriers for on-the-fly collection
      2. Doligez-Leroy-Gonthier
      3. Doligez-Leroy-Gonthier for Java
      4. Sliding views
    6. 16.6 Abstract concurrent collection
      1. The collector wavefront
      2. Adding origins
      3. Mutator barriers
      4. Precision
      5. Instantiating collectors
    7. 16.7 Issues to consider
  29. 17 Concurrent copying & compaction
    1. 17.1 Mostly-concurrent copying: Baker’s algorithm
      1. Mostly-concurrent, mostly-copying collection
    2. 17.2 Brooks’s indirection barrier
    3. 17.3 Self-erasing read barriers
    4. 17.4 Replication copying
    5. 17.5 Multi-version copying
      1. Extensions to avoid copy-on-write
    6. 17.6 Sapphire
      1. Collector phases
      2. Merging phases
      3. Volatile fields
    7. 17.7 Concurrent compaction
      1. Compressor
      2. Pauseless
    8. 17.8 Issues to consider
  30. 18 Concurrent reference counting
    1. 18.1 Simple reference counting revisited
    2. 18.2 Buffered reference counting
    3. 18.3 Concurrent, cyclic reference counting
    4. 18.4 Taking a snapshot of the heap
    5. 18.5 Sliding views reference counting
      1. Age-oriented collection
      2. The algorithm
      3. Sliding views cycle reclamation
      4. Memory consistency
    6. 18.6 Issues to consider
  31. 19 Real-time garbage collection
    1. 19.1 Real-time systems
    2. 19.2 Scheduling real-time collection
    3. 19.3 Work-based real-time collection
      1. Parallel, concurrent replication
      2. Uneven work and its impact on work-based scheduling
    4. 19.4 Slack-based real-time collection
      1. Scheduling the collector work
      2. Execution overheads
      3. Programmer input
    5. 19.5 Time-based real-time collection: Metronome
      1. Mutator utilisation
      2. Supporting predictability
      3. Analysis
      4. Robustness
    6. 19.6 Combining scheduling approaches: Tax-and-Spend
      1. Tax-and-Spend scheduling
      2. Tax-and-Spend prerequisites
    7. 19.7 Controlling fragmentation
      1. Incremental compaction in Metronome
      2. Incremental replication on uniprocessors
      3. Stopless: lock-free garbage collection
      4. Staccato: best-effort compaction with mutator wait-freedom
      5. Chicken: best-effort compaction with mutator wait-freedom for x86
      6. Clover: guaranteed compaction with probabilistic mutator lock-freedom
      7. Stopless versus Chicken versus Clover
      8. Fragmented allocation
    8. 19.8 Issues to consider
  32. Glossary
  33. Bibliography
  34. Index

Product information

  • Title: The Garbage Collection Handbook
  • Author(s): Richard Jones, Antony Hosking, Eliot Moss
  • Release date: September 2016
  • Publisher(s): Chapman and Hall/CRC
  • ISBN: 9781315388007