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