Wed, 15 Jul 2009 00:05:12 -0700 (PDT)

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

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.