The Garbage Collection Handbook: The Art of Automatic Memory Management

Front Cover......Page 1
Front Matter......Page 2
Dedication......Page 6
Contents......Page 8
List Of Algorithms......Page 16
List Of Figures......Page 20
List Of Tables......Page 22
Preface......Page 24
Acknowledgements......Page 28
Authors......Page 30
Chapter 1: Introduction......Page 32
1.1 Explicit Deallocation......Page 33
1.2 Automatic Dynamic Memory Management......Page 34
1.3 Comparing Garbage Collection Algorithms......Page 36
Completeness And Promptness......Page 37
Optimisations For Specific Languages......Page 39
1.4 A Performance Disadvantage?......Page 40
1.5 Experimental Methodology......Page 41
The Heap......Page 42
The Mutator Roots......Page 43
Liveness, Correctness, And Reachability......Page 44
Mutator Read And Write Operations......Page 45
Sets, Multisets, Sequences, And Tuples......Page 46
Chapter 2: Mark-Sweep Garbage Collection......Page 48
2.1 The Mark-Sweep Algorithm......Page 49
2.2 The Tricolour Abstraction......Page 51
2.3 Improving Mark-Sweep......Page 52
2.4 Bitmap Marking......Page 53
2.5 Lazy Sweeping......Page 55
2.6 Cache Misses In The Marking Loop......Page 58
Space Usage......Page 60
To Move Or Not To Move?......Page 61
Chapter 3: Mark-Compact Garbage Collection......Page 62
3.1 Two-Finger Compaction......Page 63
3.2 The Lisp 2 Algorithm......Page 65
3.3 Threaded Compaction......Page 67
3.4 One-Pass Algorithms......Page 69
Is Compaction Necessary?......Page 71
Locality......Page 72
Limitations Of Mark-Compact Algorithms......Page 73
4.1 Semispace Copying Collection......Page 74
Work List Implementations......Page 75
4.2 Traversal Order And Locality......Page 77
Allocation......Page 84
Space And Locality......Page 85
Moving Objects......Page 86
Chapter 5: Reference Counting......Page 88
5.1 Advantages And Disadvantages Of Reference Counting......Page 89
5.2 Improving Efficiency......Page 91
5.3 Deferred Reference Counting......Page 92
5.4 Coalesced Reference Counting......Page 94
5.5 Cyclic Reference Counting......Page 97
5.6 Limited-Field Reference Counting......Page 103
The Environment......Page 104
Advanced Solutions......Page 105
6.1 Throughput......Page 108
6.3 Space......Page 109
6.4 Implementation......Page 110
6.6 A Unified Theory Of Garbage Collection......Page 111
Tracing Garbage Collection......Page 112
Reference Counting Garbage Collection......Page 113
7.1 Sequential Allocation......Page 118
7.2 Free-List Allocation......Page 119
First-Fit Allocation......Page 120
Best-Fit Allocation......Page 121
Speeding Free-List Allocation......Page 123
7.4 Segregated-Fits Allocation......Page 124
Populating Size Classes......Page 126
7.5 Combining Segregated-Fits With First-, Best-, And Next-Fit......Page 127
Alignment......Page 128
Heap Parsability......Page 129
Wilderness Preservation......Page 131
7.7 Allocation In Concurrent Systems......Page 132
7.8 Issues To Consider......Page 133
8.2 Why To Partition......Page 134
Partitioning For Space......Page 135
Partitioning For Yield......Page 136
Partitioning For Locality......Page 137
Partitioning By Availability......Page 138
8.3 How To Partition......Page 139
8.4 When To Partition......Page 140
Chapter 9: Generational Garbage Collection......Page 142
9.1 Example......Page 143
9.3 Generational Hypothesis......Page 144
9.4 Generations And Heap Layout......Page 145
9.5 Multiple Generations......Page 146
Aging Semispaces......Page 147
Survivor Spaces And Flexibility......Page 150
Appel-Style Garbage Collection......Page 152
9.8 Inter-Generational Pointers......Page 154
Remembered Sets......Page 155
Pointer Direction......Page 156
9.9 Space Management......Page 157
9.10 Older-First Garbage Collection......Page 158
9.11 Beltway......Page 161
9.12 Analytic Support For Generational Collection......Page 163
9.13 Issues To Consider......Page 164
9.14 Abstract Generational Garbage Collection......Page 165
10.1 Large Object Spaces......Page 168
The Treadmill Garbage Collector......Page 169
Moving Objects With Operating System Support......Page 170
Mature Object Space Garbage Collection......Page 171
Connectivity-Based Garbage Collection......Page 174
Thread-Local Garbage Collection......Page 175
Stack Allocation......Page 178
Region Inferencing......Page 179
10.3 Hybrid Mark-Sweep, Copying Collectors......Page 180
Garbage-First......Page 181
Immix And Others......Page 182
Copying Collection In A Constrained Memory Space......Page 185
10.4 Bookmarking Garbage Collection......Page 187
10.5 Ulterior Reference Counting......Page 188
10.6 Issues To Consider......Page 189
11.1 Interface To Allocation......Page 192
Speeding Allocation......Page 195
Zeroing......Page 196
Conservative Pointer Finding......Page 197
Accurate Pointer Finding Using Tagged Values......Page 199
Accurate Pointer Finding In Objects......Page 200
Accurate Pointer Finding In Stacks And Registers......Page 202
Accurate Pointer Finding In Code......Page 212
Handling Interior Pointers......Page 213
Handling Derived Pointers......Page 214
11.3 Object Tables......Page 215
11.4 Reference From External Code......Page 216
11.5 Stack Barriers......Page 217
11.6 GC-Safe Points And Mutator Suspension......Page 218
11.7 Garbage Collection Code......Page 221
Engineering......Page 222
Precision Of Write Barriers......Page 223
Hash Tables......Page 225
Sequential Store Buffers......Page 226
Overflow Action......Page 227
Card Tables......Page 228
Crossing Maps......Page 230
Summarising Cards......Page 232
Write Barrier Mechanisms: In Summary......Page 233
11.9 Managing Address Space......Page 234
11.10 Applications Of Virtual Memory Page Protection......Page 236
Applications Of No-Access Pages......Page 237
11.11 Choosing Heap Size......Page 239
11.12 Issues To Consider......Page 241
12.1 Finalisation......Page 244
When Do Finalisers Run?......Page 245
Which Thread Runs A Finaliser?......Page 246
When Are Finalised Objects Reclaimed?......Page 247
Is There Any Guaranteed Order To Finalisation?......Page 248
The Finalisation Race Problem......Page 249
Finalisation In Particular Languages......Page 250
12.2 Weak References......Page 252
Additional Motivations......Page 253
Supporting Multiple Pointer Strengths......Page 254
Using Phantom Objects To Control Finalisation Order......Page 256
Weak Pointers In Other Languages......Page 257
12.3 Issues To Consider......Page 259
Processors And Threads......Page 260
Interconnect......Page 261
Caches......Page 262
Cache Coherence Performance Example: Spin Locks......Page 263
13.2 Hardware Memory Consistency......Page 265
Consistency Models......Page 267
Compare-And-Swap......Page 268
Load-Linked/Store-Conditionally......Page 269
More Powerful Primitives......Page 271
Overheads Of Atomic Primitives......Page 273
13.4 Progress Guarantees......Page 274
Progress Guarantees And Concurrent Collection......Page 275
13.5 Notation Used For Concurrent Algorithms......Page 276
13.6 Mutual Exclusion......Page 277
13.7 Work Sharing And Termination Detection......Page 279
Rendezvous Barriers......Page 282
13.8 Concurrent Data Structures......Page 284
Concurrent Queue Implemented With Singly Linked List......Page 287
Concurrent Queue Implemented With Array......Page 292
What Is Transactional Memory?......Page 298
Using Transactional Memory To Help Implement Collection......Page 301
Supporting Transactional Memory In The Presence Of Garbage Collection......Page 303
13.10 Issues To Consider......Page 304
Chapter 14: Parallel Garbage Collection......Page 306
14.1 Is There Sufficient Work To Parallelise?......Page 307
14.2 Load Balancing......Page 308
14.3 Synchronisation......Page 309
14.5 Parallel Marking......Page 310
Processor-Centric Techniques......Page 311
Processor-Centric Techniques......Page 320
Memory-Centric Techniques......Page 325
14.8 Parallel Compaction......Page 330
Terminology......Page 333
Managing Tracing......Page 334
Sweeping And Compaction......Page 336
Termination......Page 337
Chapter 15: Concurrent Garbage Collection......Page 338
The Tricolour Abstraction, Revisited......Page 340
The Lost Object Problem......Page 341
The Strong And Weak Tricolour Invariants......Page 343
Mutator Colour......Page 344
Snapshot-At-The-Beginning Solutions......Page 345
Grey Mutator Techniques......Page 346
Completeness Of Barrier Techniques......Page 348
Concurrent Write Barrier Mechanisms......Page 349
Two-Level Card Tables......Page 350
Reducing Work......Page 351
15.3 Issues To Consider......Page 352
16.1 Initialisation......Page 354
16.2 Termination......Page 355
16.3 Allocation......Page 356
16.4 Concurrent Marking And Sweeping......Page 357
Write Barriers For On-The-Fly Collection......Page 359
Doligez-Leroy-Gonthier......Page 360
Doligez-Leroy-Gonthier For Java......Page 361
16.6 Abstract Concurrent Collection......Page 362
Precision......Page 365
16.7 Issues To Consider......Page 366
17.1 Mostly-Concurrent Copying: Baker\'s Algorithm......Page 368
Mostly-Concurrent, Mostly-Copying Collection......Page 369
17.3 Self-Erasing Read Barriers......Page 371
17.4 Replication Copying......Page 372
17.5 Multi-Version Copying......Page 373
Extensions To Avoid Copy-On-Write......Page 375
17.6 Sapphire......Page 376
Collector Phases......Page 377
17.7 Concurrent Compaction......Page 382
Compressor......Page 383
Pauseless......Page 386
17.8 Issues To Consider......Page 392
18.1 Simple Reference Counting Revisited......Page 394
18.3 Concurrent, Cyclic Reference Counting......Page 397
18.4 Taking A Snapshot Of The Heap......Page 399
18.5 Sliding Views Reference Counting......Page 400
The Algorithm......Page 401
Sliding Views Cycle Reclamation......Page 403
Memory Consistency......Page 404
18.6 Issues To Consider......Page 405
19.1 Real-Time Systems......Page 406
19.2 Scheduling Real-Time Collection......Page 407
Parallel, Concurrent Replication......Page 408
Uneven Work And Its Impact On Work-Based Scheduling......Page 415
19.4 Slack-Based Real-Time Collection......Page 417
Scheduling The Collector Work......Page 420
Execution Overheads......Page 421
Mutator Utilisation......Page 422
Supporting Predictability......Page 424
Analysis......Page 426
19.6 Combining Scheduling Approaches: Tax-And-Spend......Page 430
Tax-And-Spend Scheduling......Page 431
Tax-And-Spend Prerequisites......Page 432
19.7 Controlling Fragmentation......Page 434
Incremental Compaction In Metronome......Page 435
Incremental Replication On Uniprocessors......Page 436
Stopless: Lock-Free Garbage Collection......Page 437
Staccato: Best-Effort Compaction With Mutator Wait-Freedom......Page 438
Clover: Guaranteed Compaction With Probabilistic Mutator Lock-Freedom......Page 441
Fragmented Allocation......Page 443
19.8 Issues To Consider......Page 446
Glossary......Page 448
Bibliography......Page 460
Index......Page 494
Colophon......Page 513
Back Cover......Page 514