source/blog/posts/2008/08/zct-and-cycles.rst

   1 Title: ZCT and cycles
   2 Tags: en, d, dgc, rc, deferred, zct, deutsch, bobrow, cycles
   3
   4 There's not much to think about it (I think ;).
   5
   6 ZCT doesn't help in cycles reclaiming, because ZCT tracks cells with zero
   7 count, and cycles can't possibly have a zero count (even using deferred
   8 reference counting), because they are, by definition, inter-heap pointers.
   9
  10 Let's see a simple example:
  11
  12 .. image:: ##POST_URL##/zct-and-cycles-a.png
  13     :alt: Memory layout before a cycle is lost
  14     :class: center
  15
  16 First, we have 3 heap cells, A pointed **only** by the (thus with rc 0
  17 and added to the ZCT) and B pointed by A and in a cycle with C.
  18
  19 If sometime later, A stop pointing to B, the cycle B-C is not pointed by
  20 anything (the ZCT can't do anything about it either), so we lost track
  21 of the cycle.
  22
  23 .. image:: ##POST_URL##/zct-and-cycles-b.png
  24     :alt: Memory layout after a cycle is lost
  25     :class: center
  26
  27 Does this mean that deferred reference counting is useless? I think
  28 not. It could still be useful to do some kind of incremental garbage
  29 collection, minimizing pauses for a lot of cases. As long as the ZCT
  30 reconciliation can find free cells, the pauses of GC would be as short
  31 as tracing only the stack, which I think it would be pretty short.
  32
  33 .. admonition:: Mental note
  34
  35     See how often cycles are found in tipical D programs.
  36
  37 If the ZCT reconciliation can't find free cells, a **full collection**
  38 should be triggered, using a tracing collector to inspect both the stack
  39 and the heap. Alternatively, one can a *potential cycle table* to store
  40 cells which rc has been decremented to a value higher than zero, and
  41 then just trace those cells to look for cycles, but we will see this
  42 algorithm in more detail in the future.
  43
  44 .. vim: set et sw=4 sts=4 :