Re: Daily gclist MIME digest V5 #52

yes, one of the differences in rajan and my algorithm (uni- and
multi-processor) is that the "tentative decrement" phase is done once for
all candidate objects, and then the "undecrement" and the "reap" phases.
that makes the algorithm linear rather than quadratic.

http://www.research.ibm.com/people/d/dfb/publications.html#Bacon01Concurrent

david
----- Original Message ----- 
From: "Larry Evans" <[email protected]>
To: <[email protected]>
Sent: Friday, January 13, 2006 5:00 PM
Subject: Re: [gclist] Daily gclist MIME digest V5 #52


> On 01/12/2006 12:41 PM, Jesus Cea wrote:
>
> (NOTE_TO_MOD:  I sent this earlier before
> subscribing.  Hopefully it won't appear
> twice.
> )
> [snip]
>
> >
> >>[1] LINS,R.D.Cyclic reference counting with lazy
> >>mark-scan.Inf.Process.Lett.44,4 (Dec.
> >>1992),215?220.
> >
> >
> > http://www.cs.kent.ac.uk/pubs/1992/120/
> >
> > I've not read it yet, but his approach seems similar to my current work:
> > If the ref count is zero, I delete the object. If the refcount is not
> > zero, I add the object to a lazy mark&sweep structure. From time to
> > time, I scan the structure. For each object there, I get its ref count
> > and keep it in a variable. Then I follow the graph references from
> > there. Each time I reach the initial object, I decrease the variable
> > that maintains the running reference count of the object. If that
> > variable is zero, then this object lives in a cyclic structure and the
> > only pointers to it comes from that structure. If all other objects in
> > the structure only have internal pointers also, we can recicle it
> entirely.
>
> Another difference, IIRC, is that the Lins method decrements the count
> as the local graph is traversed.  It then has to increment the same
> counts during another traversal if no cycle was found.  One difference
> w.r.t. a uniprocessor version Bacon's method is the method of
> traversing the graph. I *think* Bacon doesn't mix the "phases" when
> doing graph traversal.  IOW Lins, during graph traversal, switches
> between phases, whereas Bacon traverses the whole graph while only
> doing phase(i), then traverses the whole graph doing phase(i+1).  I
> *think* this makes Bacon's a bit faster, IIRC.
>
> As noted by the GC-book[1996], p. 67, when the "control set" in Lins'
> lazy method is the entire heap, then Lins method is *almost* the same
> as Christopher's.  There's currently an implementation of
> Christopher's method in the Boost sandbox in a policy_ptr directory:
>
>    http://tinyurl.com/derxd
>
> The above test driver tests both a conservative collector
> (std_shared_graph_tagged) and a precise collector
> (std_shared_graph_accepting).  The precise one is implemented
> using the fields_visitor library:
>
>    http://tinyurl.com/93lt5
>
> A draft of the fields_visitor user's guide is in the boost vault:
>
>     http://boost-consulting.com/vault/index.php
>
> under the 'Memory' directory.
>
>
> [snip]
> >>[3] MART?INEZ,A.D.,WACHENCHAUZER,R.,AND LINS,R.D.Cyclic reference
> counting
> >>with local mark-scan.Inf.Process.Lett.34,1 (1990),31?35.
> >
> >
> > This paper is "superseded" by [1] :-) .
>
> One advantage of this one over [1] is that there's no delay in the
> garbage collection.  IOW, as soon as the a node becomes garbage, it's
> collected (after, of course, the 3 traversals of the local graph are
> done).  This may be useful for scarce resources (e.g. open file or
> database connection) held by some object on the heap.
>
> There is a c++ implementation at:
>
>    http://tinyurl.com/c3pml
>
> it's based on an earlier version of the policy_ptr code mentioned
> earlier.  In a still earlier version of some code, I'd parameterized
> a garbaged collected object (used as argument to an intrusive smart
> pointer), with flags indicating whether eager [3] or lazy [1]
> collection was desired:
>
> enum crc_zeal
> { crc_eager
> , crc_lazy
> };
>
> Each gc'ed object would be derived from subjtop_crc<crc_zeal>,
> which would be collected either eagerly or lazily, depending
> on the crc_zeal template argument.
>
> Eventually, I'm hoping to get these different policies, as well as
> some more, into the boost policy_ptr library.
> [snip]
>
>
>