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