| 1 | Preface | xxiii | |
| 1 | Introduction | 1 | |
| 1.1 | History of storage allocation | 2 | |
| 1.1 | State, liveness and pointer reachability | 4 | |
| 1.1 | Explicit allocation on the heap | 5 | |
| 1.1 | Why garbage collect? | 8 | |
| 1.1 | How costly is garbage collection? | 12 | |
| 1.1 | Comparing garbage collection algorithms | 13 | |
| 1.1 | Notation | 16 | |
| 1.1 | Notes | 18 | |
| 2 | The Classical Algorithms | 19 | |
| 2.1 | The Reference Counting Algorithm | 19 | |
| 2.1 | The Mark-Sweep Algorithm | 25 | |
| 2.1 | The Copying Algorithm | 28 | |
| 2.1 | Comparing mark-sweep and copying collection | 33 | |
| 2.1 | Issues to consider | 36 | |
| 2.1 | Notes | 39 | |
| 3 | Reference Counting | 43 | |
| 3.1 | Non-recursive freeing | 44 | |
| 3.1 | Deferred reference counting | 45 | |
| 3.1 | Limited-field reference counts | 50 | |
| 3.1 | Hardware reference counting | 55 | |
| 3.1 | Cyclic reference counting | 56 | |
| 3.1 | Issues to consider | 69 | |
| 3.1 | Notes | 72 | |
| 4 | Mark-Sweep Garbage Collection | 75 | |
| 4.1 | Comparisons with reference counting | 75 | |
| 4.1 | Using a marking stack | 77 | |
| 4.1 | Pointer reversal | 82 | |
| 4.1 | Bitmap marking | 87 | |
| 4.1 | Lazy sweeping | 88 | |
| 4.1 | Issues to consider | 93 | |
| 4.1 | Notes | 95 | |
| 5 | Mark-Compact Garbage Collection | 97 | |
| 5.1 | Fragmentation | 97 | |
| 5.1 | Styles of compaction | 99 | |
| 5.1 | The Two-Finger Algorithm | 101 | |
| 5.1 | The Lisp 2 Algorithm | 103 | |
| 5.1 | Table-based methods | 105 | |
| 5.1 | Threaded methods | 107 | |
| 5.1 | Issues to consider | 112 | |
| 5.1 | Notes | 114 | |
| 6 | Copying Garbage Collection | 117 | |
| 6.1 | Cheney's copying collector | 118 | |
| 6.1 | Cheap allocation | 124 | |
| 6.1 | Multiple-area collection | 126 | |
| 6.1 | Garbage collector efficiency | 128 | |
| 6.1 | Locality issues | 129 | |
| 6.1 | Regrouping strategies | 131 | |
| 6.1 | Issues to consider | 137 | |
| 6.1 | Notes | 140 | |
| 7 | Generational Garbage Collection | 143 | |
| 7.1 | The generational hypothesis | 143 | |
| 7.1 | Generational garbage collection | 146 | |
| 7.1 | Promotion policies | 152 | |
| 7.1 | Generation organisation and age recording | 159 | |
| 7.1 | Inter-generational pointers | 165 | |
| 7.1 | Non-copying generational garbage collection | 174 | |
| 7.1 | Scheduling garbage collections | 175 | |
| 7.1 | Issues to consider | 179 | |
| 7.1 | Notes | 180 | |
| 8 | Incremental and Concurrent Garbage Collection | 183 | |
| 8.1 | Synchronisation | 185 | |
| 8.1 | Barrier methods | 187 | |
| 8.1 | Mark-Sweep collectors | 188 | |
| 8.1 | Concurrent Reference Counting | 200 | |
| 8.1 | Baker's Algorithm | 202 | |
| 8.1 | The Appel--Ellis--Li collector | 209 | |
| 8.1 | Replication Copying Collectors | 213 | |
| 8.1 | Baker's Treadmill collector | 218 | |
| 8.1 | Hardware support for real-time garbage collection | 220 | |
| 8.1 | Issues to consider | 222 | |
| 8.1 | Notes | 223 | |
| 9 | Garbage Collection for C | 227 | |
| 9.1 | A taxonomy of ambiguous roots collection | 228 | |
| 9.1 | Conservative garbage collection | 230 | |
| 9.1 | Mostly Copying collection | 241 | |
| 9.1 | The optimising compiler devil | 247 | |
| 9.1 | Issues to consider | 249 | |
| 9.1 | Notes | 251 | |
| 10 | Garbage Collection for C++ | 253 | |
| 10.1 | Garbage collection for object-oriented languages | 254 | |
| 10.1 | Requirements for a C++ garbage collector | 256 | |
| 10.1 | In the compiler or in a library? | 257 | |
| 10.1 | Conservative garbage collection | 258 | |
| 10.1 | Mostly Copying collection | 258 | |
| 10.1 | Smart pointers | 261 | |
| 10.1 | Changes to C++ to support garbage collection | 269 | |
| 10.1 | The Ellis--Detlefs proposal | 270 | |
| 10.1 | Finalisation | 271 | |
| 10.1 | Issues to consider | 273 | |
| 10.1 | Notes | 274 | |
| 11 | Cache-Conscious Garbage Collection | 277 | |
| 11.1 | Modern processor architectures | 277 | |
| 11.1 | Cache architectures | 279 | |
| 11.1 | Patterns of memory access | 284 | |
| 11.1 | Standard ways to improve cache performance | 287 | |
| 11.1 | Miss rate and overall cache performance | 294 | |
| 11.1 | Special purpose hardware | 296 | |
| 11.1 | Issues to consider | 297 | |
| 11.1 | Notes | 298 | |
| 12 | Distributed Garbage Collection | 299 | |
| 12.1 | Requirements | 300 | |
| 12.1 | Virtually shared memory | 301 | |
| 12.1 | Distributed garbage collection issues | 304 | |
| 12.1 | Distributed mark-sweep | 307 | |
| 12.1 | Distributed copying | 312 | |
| 12.1 | Distributed reference counting | 313 | |
| 12.1 | Garbage collecting actors | 317 | |
| 12.1 | Notes | 318 | |
| Glossary | 321 | ||
| Bibliography | 329 | ||
| Index | 365 | ||
Copyright © 1999 · Richard Jones