Re: Best Ref-counting algorithms?

On Jul 14, 8:27 pm, George Neuner <gneun...@comcast.net> wrote:
> On Sun, 12 Jul 2009 13:41:59 -0700 (PDT), Christoffer Lernv
> >I've read papers by Lins 2003 "Lazy Cyclic Reference Counting",
> >Bacon / Rajan 2001 "Concurrent Cycle Collection in Reference Counted
> >Systems" and a few others.
>
> >If one would like to implement a fast GC using refcounting, should I
> >implement something like in those papers, or are there better
> >algorithms out there?
>
> Reference counting is really primitive GC technology and you're better
> off not starting down that path unless your intent is to provide a
> library module that can't make assumptions about its environment.
>
> I haven't read Bacon's paper, but you'll note that Lins uses a marking
> scan as a backup to identify and break data cycles for the reference
> counter. Although the marking scan need not be run unless memory is
> tight, it significantly complicates the overall implementation.


I implemented the simple non-concurrent version of the algorithm as
described in Bacon's paper and I did not find it all that complex, the
concurrent version is naturally more involved though.


> In fact, the marking scanner is nearly half the implementation of a
> more capable mark-sweep or mark-compact collector ... neither of which
> will have the reference counter's problems with circular data
> structures.


Yes, but what I find interesting is that the scanning in the case of
ref-counting is on a small subset of all objects. For more advanced
tracing collectors, this is also the case. There is a nice paper on
the duality between ref-counting and tracing collectors by Bacon,
Cheng and Rajan.


Bacon also claims that their collector got really good results when it
comes to GC cost, quite competitive with tracing collectors.


> If you're dead set on reference counting, you should investigate 1-bit
> reference counting. I don't have URL's to give you but they should be
> easy to find. The programming language is designed so that most data
> are not shared and then you only need a simple flag to say whether the
> item is shared and so needs special handling.


Yes, I think I remember reading a bit on that last year.


I guess I simply have to implement a few different collectors (tracing
and ref-counted) and see which type I like best.


/C

Return to the comp.compilers page.
Search the comp.compilers archives again.