source/blog/posts/2008/09/partial-mark-sweep-cycle-reclamation.rst

   1 Title: Partial mark and sweep cycle reclamation
   2 Tags: en, d, dgc, rc, cycles, partial, mark-sweep
   3
   4 This is a more polished version of the last idea about adding a backup tracing
   5 GC to collect cycles. We just trace the areas of the heap that can potentially
   6 store cycles (instead of tracing **all** the heap).
   7
   8 So, how do we know which areas may have cycles? When a reference counter is
   9 decremented, if it becomes zero, it can't possibly part of a cycle, but when
  10 the counter is decremented 1 or more, you never know. So the basics for the
  11 algorithm is to store cells which counters have been decremented to 1 or more,
  12 and then make a local (partial) mark and sweep to the cell accessible from it.
  13
  14 The trick is to use the reference counters. In the marking phase, the reference
  15 counters are decremented as the connectivity graph is traversed. When the
  16 marking phase is done, any cell with counter higher than zero is reference from
  17 outside the partial graph analyzed, so it must survive (as well as all the
  18 cells reachable from it).
  19
  20 .. note::
  21
  22     The worst case for a *partial* scan, is to scan the **whole** heap. But
  23     this should be extremely rare.
  24
  25 There are a lot of flavors of this algorithm, but all are based on the same
  26 principle, and most of the could be suitable for D.
  27
  28 .. vim: set et sw=4 sts=4 :