Table of Contents

Click chapter to expand sections

List of Algorithmsxvii
List of Figuresxxi
List of Tablesxxv
1.1Explicit deallocation2
1.2Automatic dynamic memory management4
1.3Comparing garbage collection algorithms6
Throughput and cycles consumed6
Completeness and promptness7
Pause time and latency7
Space overhead8
Energy use8
Optimisations for specific languages9
Scalability and portability10
1.4A performance disadvantage?10
1.5Experimental methodology11
1.6Terminology and notation12
The heap13
The mutator and the collector13
The mutator roots14
References, fields and addresses14
Liveness, correctness and reachability15
The allocator15
Mutator read and write operations16
Atomic operations16
Sets, multisets, sequences and tuples17
2Mark-sweep garbage collection19
2.1The mark-sweep algorithm20
2.2The tricolour abstraction23
2.3Improving mark-sweep24
2.4Bitmap marking24
2.5Lazy sweeping27
2.6Cache misses in the marking loop29
2.7Issues to consider31
Mutator overhead31
Space usage32
To move or not to move?32
3Mark-compact garbage collection35
3.1Two-finger compaction36
3.2The Lisp 2 algorithm38
3.3Threaded compaction40
3.4One-pass algorithms42
3.5Issues to consider45
Is compaction necessary?45
Throughput costs of compaction45
Long-lived data45
Limitations of mark-compact algorithms46
4Copying garbage collection47
4.1Semispace copying collection47
Work-list implementations48
An example50
4.2Traversal order and locality50
4.3Issues to consider57
Space and locality58
Moving objects59
5Reference counting61
5.1Advantages and disadvantages of reference counting62
5.2Improving efficiency64
5.3Deferred reference counting65
5.4Coalesced reference counting68
5.5Cyclic reference counting71
5.6Limited-field reference counting77
5.7Issues to consider78
The environment78
Advanced solutions78
6Comparing garbage collectors81
6.2Pause time and latency82
6.5Adaptive systems84
6.6A unified theory of garbage collection85
Abstract garbage collection85
Tracing garbage collection85
Reference counting garbage collection87
7.1Sequential allocation91
7.2Free-list allocation93
First-fit allocation93
Next-fit allocation93
Best-fit allocation94
Speeding free-list allocation95
7.4Segregated-fits allocation98
Populating size classes100
7.5Combining segregated-fits with first-, best- and next-fit101
7.6Additional considerations101
Size constraints102
Boundary tags102
Heap parsability103
Wilderness preservation105
Crossing maps105
7.7Allocation in concurrent systems105
7.8Issues to consider106
8Partitioning the heap109
8.2Why to partition109
Partitioning by mobility110
Partitioning by size110
Partitioning for space110
Partitioning by kind111
Partitioning for yield111
Partitioning for responsiveness112
Partitioning for locality112
Partitioning by thread113
Partitioning by availability113
Partitioning by mutability114
8.3How to partition114
8.4When to partition116
9Generational garbage collection117
9.2Measuring time119
9.3Generational hypotheses119
9.4Generations and heap layout120
9.5Multiple generations121
9.6Age recording122
En masse promotion122
Aging semispaces124
Survivor spaces and flexibility126
9.7Adapting to program behaviour127
Appel-style garbage collection127
Feedback-controlled promotion129
9.8Inter-generational pointers130
Remembered sets130
Pointer direction131
9.9Space management132
9.10Older-first garbage collection133
9.12Analytic support for generational collection138
9.13Issues to consider139
9.14Abstract generational garbage collection141
10Other partitioned schemes143
10.1Large object spaces143
The Treadmill garbage collector144
Moving objects with operating system support145
Pointer-free objects146
10.2Topological collectors146
Mature Object Space garbage collection146
Connectivity-based garbage collection149
Thread-local garbage collection150
Stack allocation155
Region inferencing156
10.3Hybrid mark-sweep, copying collectors157
10.4Garbage-First: collecting young regions158
10.5Trading space and time161
10.6Mark-region collection: immix162
10.7Copying collection in a constrained memory space164
10.8Bookmarking garbage collection166
10.9Ulterior reference counting167
10.10Issues to consider168
11Run-time interface171
11.1Interface to allocation171
Speeding allocation174
11.2Finding pointers176
Conservative pointer finding176
Accurate pointer finding using tagged values179
Accurate pointer finding in objects180
Accurate pointer finding in global roots181
Accurate pointer finding in stacks and registers182
Accurate pointer finding in code192
Handling interior pointers193
Handling derived pointers194
11.3Object tables195
11.4References from external code196
11.5Stack barriers197
11.6GC safe-points and mutator suspension198
11.7Garbage collecting code201
11.8Read and write barriers202
Precision of write barriers203
Hash tables205
Sequential store buffers206
Overflow action208
Cards and card tables208
Crossing maps210
Summarising cards212
Hardware and virtual memory techniques213
Write barrier mechanisms: in summary214
Chunked lists214
11.9Managing address space215
11.10Applications of virtual memory page protection217
Double mapping217
Applications of no-access pages218
11.11Choosing heap size220
11.12Issues to consider222
12Language-specific concerns225
When do finalisers run?226
Which thread runs a finaliser?227
Can finalisers run concurrently with each other?228
Can finalisers access the object that became unreachable?228
When are finalised objects reclaimed?229
What happens if there is an error in a finaliser?229
Is there any guaranteed order to finalisation?229
The finalisation race problem230
Finalisers and locks231
Finalisation and weak references231
Finalisation in particular languages232
For further study233
12.2Weak references233
Additional motivations235
Weak references in Java: the short story235
Weak references in Java: the full story236
Race in weak pointer clearing239
Weak pointers in other languages240
12.3Changing object layout241
12.4Issues to consider243
13Concurrency preliminaries245
Processors and threads245
Cache coherence performance example: spin locks248
13.2Hardware memory consistency250
Fences and happens-before251
Consistency models252
13.3Hardware primitives253
Atomic arithmetic primitives255
Test then test-and-set257
More powerful primitives257
Overheads of atomic primitives258
13.4Progress guarantees259
Progress guarantees and concurrent collection260
13.5Notation used for concurrent algorithms261
13.6Mutual exclusion262
13.7Work sharing and termination detection264
Rendezvous barriers269
13.8Concurrent data structures269
Concurrent stacks272
Concurrent queue implemented with singly linked list272
Concurrent queue implemented with array276
Concurrent deque for work stealing281
13.9Transactional memory282
Using transactional memory to help implement collection286
Supporting transactional memory in the presence of garbage collection288
13.10Issues to consider289
14Parallel garbage collection291
14.1Is there sufficient work to parallelise?292
14.2Load balancing293
14.5Parallel marking295
14.6Parallel copying304
Processor-centric techniques305
Memory-centric techniques310
14.7Parallel sweeping315
14.8Parallel compaction316
14.9Garbage collection on the GPU?319
GPU background319
Heap reference graphs321
Marking on the GPU322
A problem not yet solved324
14.10Issues to consider324
Is parallel collection worthwhile?324
Strategies for balancing loads325
Managing tracing325
Low-level synchronisation327
Sweeping and compaction327
15Concurrent garbage collection329
15.1Correctness of concurrent collection331
The tricolour abstraction, revisited331
The lost object problem332
The strong and weak tricolour invariants334
Mutator colour335
Allocation colour336
Pointer tagging336
Incremental update solutions336
Snapshot-at-the-beginning solutions337
15.2Barrier techniques for concurrent collection337
Grey mutator techniques337
Black mutator techniques339
Completeness of barrier techniques340
Load barriers341
Concurrent write barrier mechanisms342
One-level card tables343
Two-level card tables343
Reducing work343
Eliminating read barriers344
15.3Ragged phase changes344
15.4Issues to consider346
16Concurrent mark-sweep349
16.4Concurrent marking and sweeping353
16.5Garbage-First: collecting young and old regions354
16.6On-the-fly marking357
Write barriers for on-the-fly collection357
Doligez-Leroy-Gonthier for Java359
Sliding views360
16.7Abstract concurrent collection360
The collector wavefront361
Adding origins363
Mutator barriers363
Instantiating collectors364
16.8Issues to consider364
17Concurrent copying and compaction367
17.1Mostly-concurrent copying367
Baker's algorithm368
Mostly-concurrent, mostly-copying collection370
17.2Brooks's indirection barrier370
17.3Self-erasing read barriers371
17.4Replication copying372
Multi-version copying372
Extensions to avoid copy-on-write374
Transactional Sapphire376
17.5Concurrent compaction384
Pauseless and C4386
Reducing stop-the-world time in Shenandoah and ZGC403
17.6Issues to consider404
18Concurrent reference counting405
18.1LXR: Latency-critical ImmiX with Reference counting405
18.2Simple reference counting revisited409
18.3Biased reference counting411
18.4Buffered reference counting412
18.5Concurrent, cyclic reference counting413
18.6Taking a snapshot of the heap414
18.7Sliding views reference counting416
Age-oriented collection416
Sliding views cycle reclamation419
Memory consistency420
18.8Issues to consider420
Safe memory reclamation421
19Real-time garbage collection423
19.1Real-time systems423
19.2Scheduling real-time collection424
19.3Work-based real-time collection425
Parallel, concurrent replication425
Uneven work and its impact on work-based scheduling432
19.4Slack-based real-time collection434
Scheduling the collector work436
Execution overheads438
Programmer input439
19.5Time-based real-time collection: Metronome439
Mutator utilisation439
Supporting predictability441
19.6Combining scheduling approaches: Tax-and-Spend448
Tax-and-Spend scheduling448
Tax-and-Spend prerequisites450
19.7Controlling fragmentation452
Incremental compaction in Metronome452
Incremental replication on uniprocessors453
Stopless: lock-free garbage collection454
Staccato: best-effort compaction with mutator wait-freedom455
Chicken: best-effort compaction with mutator wait-freedom for x86458
Clover: guaranteed compaction with probabilistic mutator lock-freedom458
Stopless versus Chicken versus Clover459
Fragmented allocation461
19.8Issues to consider463
20Energy-aware garbage collection465
20.1Issues to consider469
21Persistence and garbage collection471
21.1Persistence: concepts, issues and implementation471
Providing durability472
Issues raised by persistence473
21.2Impacts of persistence on garbage collection475
21.3Barriers in support of persistence476
Software barriers476
Hardware barriers477
Software versus hardware barriers478
21.4Implemented collectors for persistent heaps478
Persistent reference counting478
Persistent mark-sweep and mark-compact479
Persistent copying480
21.5Issues to consider481