The Garbage Collection Handbook, 2nd Edition

The Garbage Collection Handbook, 2nd Edition

by Richard Jones, Antony Hosking, Eliot Moss
Released June 2023
Publisher(s): Chapman and Hall/CRC
ISBN: 9781000883688

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

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

Table of contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright Page
  5. Dedication
  6. Contents (1/2)
  7. Contents (2/2)
  8. List of Algorithms
  9. List of Figures
  10. List of Tables
  11. Preface (1/2)
  12. Preface (2/2)
  13. Acknowledgements
  14. Authors
  15. 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 and cycles consumed
      3. Completeness and promptness
      4. Pause time and latency
      5. Space overhead
      6. Energy use
      7. Optimisations for specific languages
      8. 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. Pseudocode
      7. The allocator
      8. Mutator read and write operations
      9. Atomic operations
      10. Sets, multisets, sequences and tuples
  16. 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?
  17. 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
  18. 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
  19. 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 (1/2)
    6. 5.5. Cyclic reference counting (2/2)
    7. 5.6. Limited-field reference counting
    8. 5.7. Issues to consider
      1. The environment
      2. Advanced solutions
  20. 6. Comparing garbage collectors
    1. 6.1. Throughput
    2. 6.2. Pause time and latency
    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
  21. 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
  22. 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
  23. 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
  24. 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
    4. 10.4. Garbage-First: collecting young regions
    5. 10.5. Trading space and time
    6. 10.6. Mark-region collection: immix
    7. 10.7. Copying collection in a constrained memory space
    8. 10.8. Bookmarking garbage collection
    9. 10.9. Ulterior reference counting
    10. 10.10. Issues to consider
  25. 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 (1/2)
      6. Accurate pointer finding in stacks and registers (2/2)
      7. Accurate pointer finding in code
      8. Handling interior pointers
      9. 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. Cards and 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
  26. 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 and weak references
      11. Finalisation in particular languages
      12. For further study
    2. 12.2. Weak references
      1. Additional motivations
      2. Weak references in Java: the short story
      3. Weak references in Java: the full story
      4. Race in weak pointer clearing
      5. Weak pointers in other languages
    3. 12.3. Changing object layout
    4. 12.4. Issues to consider
  27. 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. Concurrent deque for work stealing
    9. 13.9. Transactional memory
      1. Using transactional memory to help implement collection
      2. Supporting transactional memory in the presence of garbage collection
    10. 13.10. Issues to consider
  28. 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
    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. Garbage collection on the GPU?
      1. GPU background
      2. Heap reference graphs
      3. Marking on the GPU
      4. A problem not yet solved
    10. 14.10. 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
  29. 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. Pointer tagging
      8. Incremental update solutions
      9. 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. Load barriers
      5. Concurrent write barrier mechanisms
      6. One-level card tables
      7. Two-level card tables
      8. Reducing work
      9. Eliminating read barriers
    3. 15.3. Ragged phase changes
    4. 15.4. Issues to consider
  30. 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. Garbage-First: collecting young and old regions
    6. 16.6. 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
    7. 16.7. Abstract concurrent collection
      1. The collector wavefront
      2. Adding origins
      3. Mutator barriers
      4. Precision
      5. Instantiating collectors
    8. 16.8. Issues to consider
  31. 17. Concurrent copying and compaction
    1. 17.1. Mostly-concurrent copying
      1. Baker’s algorithm
      2. Mostly-concurrent, mostly-copying collection
    2. 17.2. Brooks’s indirection barrier
    3. 17.3. Self-erasing read barriers
    4. 17.4. Replication copying
      1. Multi-version copying
      2. Extensions to avoid copy-on-write
      3. Sapphire
      4. Transactional Sapphire
      5. Platinum
    5. 17.5. Concurrent compaction
      1. Compressor
      2. Pauseless and C4 (1/2)
      3. Pauseless and C4 (2/2)
      4. Collie
      5. ZGC
      6. Shenandoah
      7. Reducing stop-the-world time in Shenandoah and ZGC
    6. 17.6. Issues to consider
  32. 18. Concurrent reference counting
    1. 18.1. LXR: Latency-critical ImmiX with Reference counting
    2. 18.2. Simple reference counting revisited
    3. 18.3. Biased reference counting
    4. 18.4. Buffered reference counting
    5. 18.5. Concurrent, cyclic reference counting
    6. 18.6. Taking a snapshot of the heap
    7. 18.7. Sliding views reference counting
      1. Age-oriented collection
      2. Sliding views cycle reclamation
      3. Memory consistency
    8. 18.8. Issues to consider
      1. Safe memory reclamation
  33. 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
  34. 20. Energy-aware garbage collection
    1. 20.1. Issues to consider
  35. 21. Persistence and garbage collection
    1. 21.1. Persistence: concepts, issues and implementation
      1. Providing durability
      2. Issues raised by persistence
    2. 21.2. Impacts of persistence on garbage collection
    3. 21.3. Barriers in support of persistence
      1. Software barriers
      2. Hardware barriers
      3. Software versus hardware barriers
    4. 21.4. Implemented collectors for persistent heaps
      1. Persistent reference counting
      2. Persistent mark-sweep and mark-compact
      3. Persistent copying
    5. 21.5. Issues to consider
  36. Glossary (1/4)
  37. Glossary (2/4)
  38. Glossary (3/4)
  39. Glossary (4/4)
  40. Bibliography (1/10)
  41. Bibliography (2/10)
  42. Bibliography (3/10)
  43. Bibliography (4/10)
  44. Bibliography (5/10)
  45. Bibliography (6/10)
  46. Bibliography (7/10)
  47. Bibliography (8/10)
  48. Bibliography (9/10)
  49. Bibliography (10/10)
  50. Index (1/5)
  51. Index (2/5)
  52. Index (3/5)
  53. Index (4/5)
  54. Index (5/5)

Product information

  • Title: The Garbage Collection Handbook, 2nd Edition
  • Author(s): Richard Jones, Antony Hosking, Eliot Moss
  • Release date: June 2023
  • Publisher(s): Chapman and Hall/CRC
  • ISBN: 9781000883688