Tue, 14 Jul 2009 14:27:20 -0400

Related articles |
---|

[2 earlier articles] |

Re: Best Ref-counting algorithms? lerno@dragonascendant.com (=?ISO-8859-1?Q?Christoffer_Lern=F6?=) (2009-07-13) |

Re: Best Ref-counting algorithms? cr88192@hotmail.com (BGB / cr88192) (2009-07-13) |

Re: Best Ref-counting algorithms? torbenm@pc-003.diku.dk (2009-07-14) |

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

[25 later articles] |

From: | George Neuner <gneuner2@comcast.net> |

Newsgroups: | comp.compilers |

Date: | Tue, 14 Jul 2009 14:27:20 -0400 |

Organization: | A noiseless patient Spider |

References: | 09-07-018 |

Keywords: | GC |

Posted-Date: | 14 Jul 2009 16:45:28 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.