source/blog/posts/2008/08/lazy-freeing-rc.rst

   1 Title: Lazy freeing RC
   2 Tags: en, d, dgc, rc, lazy, lazy freeing
   3
   4 The first optimization to analyze is a very simple one. What's the idea
   5 behind it lazy freeing? Just transfer some of the work of freeing unused
   6 cells to the allocation, making the collection even more interleaved
   7 with the mutator.
   8
   9 When you delete a cell, if it's counter drops to 0, instead of recursively
  10 free it, just add it to a *free-list*. Then, when a new cell has to be
  11 allocated, take it from the *free-list*, delete all its children (using
  12 the lazy delete, of course), and return that cell.
  13
  14 First drawback of this method: you loose *finalization* support, but as `I
  15 said`__, most people don't care about that. So that's a non-problem. Second,
  16 allocation is not that fast anymore. But it's *almost* bounded. Why *almost*?
  17 Because it's O(N), being N the number of pointers to be deleted in that cell.
  18 This doesn't seems like a huge cost anyways (just decrement a counter and,
  19 maybe, add it to a free-list). Allocation is (usually) not bounded anyways
  20 (except for compacting collectors).
  21
  22 __ http://proj.llucax.com.ar/blog/dgc/blog/post/22688ccb
  23
  24 The big win? Bounded freeing. **Really** small pauses, with no extra costs.
  25
  26 .. note::
  27     If you have a (simple) program that suffers from GC pauses that you
  28     think it could be easily *converted* to be reference counted (i.e. few
  29     pointer updates), please let me know if you want me to try to make it
  30     use lazy freeing RC to analyze the real impact on a real-life program.
  31
  32 .. vim: set et sw=4 sts=4 :