[gclist] Re: gclist-digest V3 #117

[marc.shapiro@acm.org]

 || Date: Wed, 18 Oct 2000 16:59:46 -0400
 || From: Andrew Shi-hwa Chen <chenandr@cse.msu.edu>
 || Subject: [gclist] Aging based garbage collection?
 || 
 || I remember seeing a while ago, on a web-site that I now can't find, a 
 || description of a GC algorithm as follows:
 || 
 || 1) objects have an associated time-stamp
 || 2) a thread continuously does DFS from the root and updates the 
 || time-stamps
 || 3) all objects are in a priority queue based on their age
 || 4) whenever an allocation request occurs, it can lazily sweep the 
 || oldest
 || 	objects away - that is, those they are so old that it is impossible 
 || that
 || 	they could be reachable because if they were, they would have been
 || 	updated by that thread that updates the time-stamps.

You are describing Hughes' algorithm:

  @InProceedings{gc:rep:685,
    author = 	 "John Hughes",
    title = 	 "A Distributed Garbage Collection Algorithm",
    editor = 	 "Jouannaud, Jean-Pierre",
    number = 	 201,
    series = 	 "Lecture Notes in Computer Science",
    pages = 	 "256--272",
    booktitle = "Functional Languages and Computer Architectures",
    year = 	 1985,
    publisher = "Springer-Verlag",
    address = 	 "Nancy (France)",
    month = 	 sep
  }

It is a beautifully elegant distributed algorithm.  It relies on
a standard mark-and-sweep (no timestamps) at each site.

It sounds like you want to use it as a centralised algorithm.  I don't
see the benefit, since you have to do the mark-and-sweep work anyway.

You could do lazy sweeping with just the single mark bit.