Garbage Collection - Algorithms for Automatic Dynamic Memory Management

gc

Garbage Collection: Algorithms for Automatic Dynamic Memory Management

Garbage Collection: Algorithms for Automatic Dynamic Memory Management

AADMMが届いたので読もうかなーというところ。 ??? のところが良くわからんくて面白そーなので集中予定です。

古典的アルゴリズムの紹介

  1. Classical Algorithms Overview
    1. Reference Counting, Mark-Sweep, Copying

.... and Compare those

  1. Issues to consider: Cyclic data structures, Roots and pointer finding, Processing cost, Space overhead, Heap occupancy and collector degradation

リファレンスカウンタの章

  1. Reference Counting
    1. Non-recursive freeing
    2. Costs and benefits of lazy deletion
  2. Deferred reference counting
    1. The Deutsch-Bobrow algorithm ???
    2. ZCT overflow ???
    3. The efficiency of deferred reference counting
  3. Limited-field reference counts
    1. Sticky reference counts, Tracing collection restores reference counts
    2. One-bit reference counts,
    3. Restoring uniqueness information ???
    4. The 'Ought to be Two' cache ???
  4. Hardware reference counting !!!!
  5. Cyclic reference counting
    1. Functional programming languages (read only だから、とかいう話かな？)
    2. Bobrow's technique ???
    3. Weak-pointer algorithms, Partial Mark-Sweep Algorithms
  6. Issues to consider: Ease of implementation, Control, optimization and correctness, Garbage collection delay , Space overhead, Recursive freeing, Mutator overhead, Space for reference counts, Locality of reference, Cyclic data structures...

マークスイープ

  1. Mark-Sweep Garbage Collection
    1. Comparisons with ref count
  2. Using a marking stack
    1. Making the recursion explicit, Minimizing the depth of the stack , Stack overflow
  3. Pointer reversal
    1. Deutsch-Schorr-Waite algorithm, Pointer-reversal for variable-sized nodes
    2. Costs of pointer-reversal !
  4. Bitmap marking
  5. Lazy sweeping
    1. Hughes's lazy sweep algorithm
    2. Boehm-Demers-Weiser sweeper ???
    3. Zorn's lazy sweeper ???
    4. Issues to consider: Space and locality, Time complexity, Object mobility

マークコンパクト

  1. Fragmentation
    1. Two-level allocation
  2. Styles of compaction
  3. The Two-Finger Algorithm ???
    1. Analysis, Variable-sized cells
  4. The Lisp 2 Algorithm
      1. おおぉぉぉぉぉぉ
  5. Table-based methods
    1. The break table, updating pointers
  6. Threaded methods
    1. Threading pointers, Jonker's compaction algorithm???
    2. Forward pointers, Backward pointers, Analysis of threaded algorithms
  7. Issues to consider: Smaller address space, Repeated copying Handling abnormal residencies, Locality, Choosing between compacting collectors

コピーGC

  1. Cheney's copying collector
    1. The tricolour abstraction, The algorithm, example
  2. Cheap allocation
  3. Multiple-area collection
    1. Static areas, Large object areas, Incremental incrementally compacting garbage collection

世代別GC

  1. The generational hypothesis
    1. Object lifetimes
  2. Generational garbage collection
    1. Pause time, The root set for minor collections, Performance
  3. Promotion policies
    1. Multiple generations, Promotion threshold, The Standard ML of New Jersey collector,
    2. Adaptive tenuring ??? (tenure は保持/保有する、とか)
  4. Generation organisation and age recording
    1. One semi-space per generation, Creation space, Age recording, Large object areas
  5. Inter-generational pointers( お、おっかない）
    1. The write-barrier, Entry tables, Remembered sets, Sequential Store Buffers
    2. Page marking with hardware support !!!
    3. Page marking with virtual memory support
    4. Card marking, Remembered sets or cards?
  6. Non-copying generational garbage collection
  7. Scheduling garbage collections
    1. key objects, Mature object spaces

インクリメンタル　＆ 平行GC

  1. Synchronization
    1. Tricolour marking (またか)
  2. Barrier methods
  3. Mark-Sweep collectors
    1. The write-barrier, New cells, Initialization and termination, Virtual memory techniques
  4. Concurrent Reference Counting
  5. Baker's Algorithm
    1. The algorithm, Bounds on the latency of Baker's algorithm, Limitations of Baker's algorithm, Variations on Baker, Dynamic regrouping
  6. The Appel-Ellis-Li collector ???
    1. Improvements, Large objects, Generations, Performance
  7. Replication Copying Collectors
    1. Nettles's replicating collectors, The Huelsbergen and Larus collector, The Doligez--Leroy-Gonthier collectors ????
  8. Baker's Treadmill collector
  9. Hardware support for real-time garbage collection !!!

CのためのGC

  1. A taxonomy of ambiguous roots collection
  2. Conservative garbage collection
    1. Allocation, Root and pointer finding, Interior pointers, Problems of conservative garbage collection, Misidentification, Efficiency, Incremental/generational garbage collection
  3. Mostly Copying collection
    1. Heap layout, Allocation, Garbage collection, Generational garbage collection, Ambiguous data structures, The efficiency of Mostly Copying
  4. The optimizing compiler devil

C++のためのGC

  1. Garbage collection for object-oriented languages
  2. Requirements for a C++ garbage collector
  3. In the compiler or in a library?
  4. Conservative garbage collection
  5. Mostly Copying collection
    1. Generating pointer finding methods automatically
  6. Smart pointers
    1. Conversions without a smart pointer hierarchy, Multiple inheritance, Incorrect conversions, Some pointers cannot be smartened, Const and volatile pointers, Smart pointer leaks, Smart pointers and reference counting, A simple reference counting pointer, Smart pointers for flexible garbage collection, Smart pointers for tracing garbage collection
  7. Changes to C++ to support garbage collection
  8. The Ellis-Detlefs proposal ???
  9. Finalization
    1. Support for finalization

キャッシュ思慮のGC

  1. Modern processor architectures
    1. The effect of cache misses on CPU time
  2. Cache architectures
    1. Cache size, Placement policy, Write strategy, Special cache instructions.
  3. Patterns of memory access
    1. Mark-sweep with bitmap and lazy sweep, Copying garbage collection, Incremental garbage collection, Avoiding fetches
  4. Standard way to improve cache performance
    1. Cache size, Block size, Associativity, Special instructions, Prefetching

とにかくそそる本である

  1. Miss rate and overall cache performance
  2. Special purpose hardware...!!!

分散GC

  1. Network restrictions
  2. Virtually shared memory
    1. Shared virtual memory , Shared data-object model, Garbage collection over distributed shared memory
  3. Distributed garbage collection issues
    1. Taxonomy, Synchronization, Robustness
  4. Distributed amark-sweep
    1. Hudak and Keller ???
    2. Ali's algorithm ???
    3. Hughes's algorithm ???
    4. The Liskov-Ladin algorithm ???
    5. Augusteijn's algorithm ???
    6. Vestal's algorithm ???
    7. The Schelvis-Bledoeg algorithm ???
    8. The Emerald collector ???
    9. The IK collector ???

ロイヤルストレートフラッシュ！！！

  1. Distributed copying
  2. Distributed reference counting
    1. The Lermem-Maurer protocol ???
    2. Indirect reference counting
    3. The Mancini-Shrivastava algorithm ???
    4. The SPG protocol ???
    5. 'Garbage collecting the world'
    6. Network objects
    7. Wieghted reference counting
    8. Generational reference counting
  3. Garbage collecting actors
    1. Halstead's algorithm ???
    2. Marking algorithms ??
    3. Logically centralized collectors

そそりまくる本です。
はよう読みたいです。時間を下さい。