source/blog/posts/2008/08/deferred-rc.rst.bak

   1 Title: Avoiding counter updates
   2 Tags: rc, deferred, deutsch-bobrow
   3
   4 The main drawback of reference counting (leaving cycle aside) probably
   5 is high overhead it imposes into the client program. Every pointer
   6 update has to manipulate the reference counters, for both the *old*
   7 and the *new* objects.
   8
   9 Function calls
  10 ==============
  11
  12 This includes every object passed as argument to a function, which one can
  13 guess it would be a **lot** (every method call for example). However, this
  14 kind of rc updates can be easily optimized away. Let's see an example::
  15
  16   class SomeClass
  17   {
  18         void some_method() {}
  19   }
  20
  21   void some_function(SomeClass o)
  22   {
  23         o.some_method();
  24   }
  25
  26   void main()
  27   {
  28         auto o = new SomeClass;
  29         some_function(o);
  30   }
  31
  32 It's clear that ``o`` should live until the end of ``main()``, and that
  33 there is **no chance** ``o`` could be garbage collected until ``main()``
  34 finishes. To express this, is enough to have ``o``'s rc = 1. There is
  35 no need to increment it when ``some_function()`` is called, nor when
  36 ``some_method()`` is called.
  37
  38 So, *theoretically* (I really didn't prove it =) is not necessary
  39 to update object's rc when used as arguments.
  40
  41
  42 Local pointers update
  43 =====================
  44
  45 What about pointer in the stack? Most of the time, pointers updates are done
  46 in local variables (pointers in the stack, not in the heap). The `GC book`__
  47 talks about 99% of pointers update done in local variables for Lisp__ and ML__.
  48 I don't think D could have that much but I guess it could be pretty high too.
  49
  50 Fortunately Deutsch and Bobrow created an algorithm to completely ignore local
  51 pointers update, at the cost of relaying on some kind of tracing collector, but
  52 that only have to trace the stack (wich should be pretty small compared to the
  53 heap).
  54
  55 What the algorithm proposes is to use simple assignment when updating local
  56 pointers. Pointers living in the heap manipulates rc as usual, but when the
  57 count drops to 0, the object is added to a *zero count table* (ZCT) (and
  58 removed if some pointer update increments the counter again).
  59
  60 Finally, at some point (usually when you run out of memory), the ZCT has to be
  61 *reconciled*, doing some simple steps: trace the stack looking for pointers and
  62 incrementing their counters and remove any object with rc = 0. Finally,
  63 decrement all the counters of the objects pointer to by the stack pointers.
  64
  65 This technique seems to be a good mix of both reference counting and tracing
  66 collectors: small pauses (the stack is usually small), low overhead for counter
  67 manipulation. The only missing point is cycles. At first sight, if we need a
  68 tracing collector for cycles, this algorithm seems pretty useless because you
  69 have to trace **all** the heap and stack to free cycles, so the *optimization*
  70 is lost. Big pauses are here again.
  71
  72 I have the feeling I'm missing something and the ZCT could be useful when comes
  73 to reclaim cycles, but I have to think a little more about that.
  74