Re: Best Ref-counting algorithms?

On Sun, 12 Jul 2009 13:41:59 -0700 (PDT), Christoffer Lernv
<lerno@dragonascendant.com> wrote:


>I'm looking into GC using ref-counting.
>
>Does anyone know what passes for state-of-the-art when it comes to ref-
>counting algorithms?


You've already found it.


>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.


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.


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.


George

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