Richard Jones

with a chapter on Distributed Garbage Collection by Rafael Lins

John Wiley & Sons, Ltd, ISBN 0-471-94148-4
403 pages, hardback

Table of Contents

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

Top of page the GC page Richard Jones' homepage
[ book ] [ GC page ] [ home ]

Copyright ©1996, Richard Jones