source/blog/posts/2008/08/avoiding-pointer-updates.rst

   1 Title: Avoiding counter updates
   2 Tags: en, d, dgc, 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 pointers 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 __ http://www.amazon.com/Garbage-Collection-Algorithms-Automatic-Management/dp/0471941484
  51 __ http://en.wikipedia.org/wiki/Lisp_(programming_language)
  52 __ http://en.wikipedia.org/wiki/ML_programming_language
  53
  54 .. admonition:: Mental note
  55
  56     Gather some statistics about the number of local pointers update
  57     vs. heap pointers update in D
  58
  59 Fortunately Deutsch and Bobrow created an algorithm to completely ignore local
  60 pointers update, at the cost of relaying on some kind of tracing collector, but
  61 that only have to trace the stack (which should be pretty small compared to the
  62 heap).
  63
  64 What the algorithm proposes is to use simple assignment when updating local
  65 pointers. Pointers living in the heap manipulates rc as usual, but when the
  66 count drops to 0, the object is added to a *zero count table* (ZCT) (and
  67 removed if some pointer update increments the counter again).
  68
  69 Finally, at some point (usually when you run out of memory), the ZCT has to be
  70 *reconciled*, doing some simple steps: trace the stack looking for pointers and
  71 incrementing their counters and remove any object with rc = 0. Finally,
  72 decrement all the counters of the objects pointer to by the stack pointers.
  73
  74 This technique seems to be a good mix of both reference counting and tracing
  75 collectors: small pauses (the stack is usually small), low overhead for counter
  76 manipulation. The only missing point is cycles. At first sight, if we need a
  77 tracing collector for cycles, this algorithm seems pretty useless because you
  78 have to trace **all** the heap and stack to free cycles, so the *optimization*
  79 is lost. Big pauses are here again.
  80
  81 I have the feeling I'm missing something and the ZCT could be useful when comes
  82 to reclaim cycles, but I have to think a little more about that.
  83
  84 .. vim: set et sw=4 sts=4 :