Re: Best Ref-counting algorithms?

=?ISO-8859-1?Q?Christoffer_Lern=F6?= <lerno@dragonascendant.com>
Wed, 15 Jul 2009 00:05:12 -0700 (PDT)

          From comp.compilers

Related articles
[5 earlier articles]
Re: Best Ref-counting algorithms? lerno@dragonascendant.com (=?ISO-8859-1?Q?Christoffer_Lern=F6?=) (2009-07-14)
Re: Best Ref-counting algorithms? haberg_20080406@math.su.se (Hans Aberg) (2009-07-14)
Re: Best Ref-counting algorithms? georgeps@xmission.com (GPS) (2009-07-14)
Re: Best Ref-counting algorithms? gneuner2@comcast.net (George Neuner) (2009-07-14)
Re: Best Ref-counting algorithms? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2009-07-15)
Re: Best Ref-counting algorithms? lerno@dragonascendant.com (=?ISO-8859-1?Q?Christoffer_Lern=F6?=) (2009-07-14)
Re: Best Ref-counting algorithms? lerno@dragonascendant.com (=?ISO-8859-1?Q?Christoffer_Lern=F6?=) (2009-07-15)
Re: Best Ref-counting algorithms? torbenm@pc-003.diku.dk (2009-07-15)
Re: Best Ref-counting algorithms? cr88192@hotmail.com (BGB / cr88192) (2009-07-15)
Re: Best Ref-counting algorithms? cr88192@hotmail.com (BGB / cr88192) (2009-07-15)
Re: Best Ref-counting algorithms? cr88192@hotmail.com (BGB / cr88192) (2009-07-15)
Re: Best Ref-counting algorithms? cr88192@hotmail.com (BGB / cr88192) (2009-07-15)
Re: Best Ref-counting algorithms? gene.ressler@gmail.com (Gene) (2009-07-15)
[22 later articles]
| List of all articles for this month |

From: =?ISO-8859-1?Q?Christoffer_Lern=F6?= <lerno@dragonascendant.com>
Newsgroups: comp.compilers
Date: Wed, 15 Jul 2009 00:05:12 -0700 (PDT)
Organization: Compilers Central
References: 09-07-018 09-07-039
Keywords: GC
Posted-Date: 15 Jul 2009 19:23:33 EDT

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



Post a followup to this message

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