source/blog/posts/2008/08/algorithms-summary.rst

   1 Title: Basic algorithms summary
   2 Tags: en, d, dgc, intro, rc, tracing, copying, mark-sweep, non-moving, moving, mark-compact
   3
   4 Let's make a little summary about the **big** categories of `garbage
   5 collection algorithms`__:
   6
   7 __ http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)
   8
   9 .. image:: ##POST_URL##/algorithms-summary.png
  10     :alt: Basic algorithms summary
  11     :class: center
  12
  13 The first branch is `reference counting`__ vs. `tracing`__ garbage collectors.
  14 For D, reference counting is a **really** complicated choice, because to be
  15 (seriously) considered, the compilar/language have to change pretty much.
  16 However, one can make some manual bookkeeping to evaluate if this method has
  17 considerable advantages over the other to see if that extra work worth the
  18 effort.
  19
  20 __ http://en.wikipedia.org/wiki/Reference_counting
  21 __ http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Tracing_garbage_collectors
  22
  23 Tracing garbage collectors is the easy way to go in D. Tracing comes in two
  24 flavors: moving and non-moving. Again, moving is hard in D, because all
  25 sort of nasty stuff can be done, but a lot more doable than reference counting.
  26 In the non-moving field, the major option is the good ol' `mark & sweep`__ (the
  27 algorithm used by the actual D garbage collector).
  28
  29 __ http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Basic_algorithm
  30
  31 Going back to the moving ones, there are two big groups: `copying`__ and
  32 `mark-compact`__. I don't like copying too much because it need at least double
  33 the residency of a program (remember, we are trying **not to** waste memory =).
  34 Mark-compact have some of the advantages of copying without this requirement.
  35
  36 __ http://en.wikipedia.org/wiki/Cheney's_algorithm
  37 __ http://en.wikipedia.org/wiki/Mark-compact_algorithm
  38
  39 .. note::
  40     This is just **one** arbitrary categorization. There are a lot of other
  41     categories based on different topis, like: pauses (`stop-the-world,
  42     incremental, concurrent`__, real-time), partitioning (`generational`__,
  43     connectivity-based), pointer-awareness (`precise, conservative`__) and
  44     probably a lot more that I don't even know.
  45
  46 __ http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Stop-the-world_vs._incremental_vs._concurrent
  47 __ http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Generational_GC_.28aka_Ephemeral_GC.29
  48 __ http://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Precise_vs._conservative_and_internal_pointers
  49
  50 .. vim: set et sw=4 sts=4 :