Re: [boost] Accurate, pauseless & deterministic GC for C++

From: Larry Evans (cppljevans_at_[hidden])
Date: 2007-11-20 15:03:35

On 11/20/07 07:21, Mingnan Guo wrote:
 >
 >   The HnxGC Library for C++ is released at
 >
 >   http://hnxgc.harnixworld.com

 >   This garbage collector provides accurate, pause-less (lock-free,
 >   block-free) concurrent garbage collection with deterministic
 >   reclamation for C++ application. Efficient, portable, no need
 >   registeration of root set pointers, no scanning of root set area,
 >   and more.
[snip]
Hi Mingnan,

This sounds interesting. I've looked briefly at:

http://hnxgc.harnixworld.com/algo_overview.htm

which contains:

   More specifically, we use reference counting technique to count the
   number of references from outside of the managed heap. When the
   count is not zero, it means that the object is marked-out and
   belongs to root objects of tracing collection. Therefore, by
   dynamically marking out root objects in application program
   execution, tracing collector can treat the managed heap boundary as
   the consideration boundary of tracing garbage collection, it need
   not to know about the outside of the managed heap and avoids
   analyzing complicated outside environments, such as program's stack
   and processors' registers.

suggests a similarity to the three-phase cyclic refcounting garbage
collectors mentioned on p. 62 of the 1996 edition of:

http://www.cs.kent.ac.uk/people/staff/rej/gcbook/gcbook.html

The following is from that page:

   Their general idea is to perform three partial traversals of the
   data structure, in the first place removing the contribution of
   pointers internal to the sub-graph being traversed from cell
   reference counts.  At the end of the first traversal, the reference
   counts will only reflect external pointers to nodes in the
   sub-graph.

The first phase sounds like its similar to the "count the number of
references from outside of the managed heap" part of
algo_overview.htm. Is that about right?

Also, I see on:

   http://hnxgc.harnixworld.com/algo_rootobj.htm

there's:

   References inside managed heap, such as pointer fields of managed
   objects, can be easily described by a "traverse" method.

and also:

   Normally, each class should have its own traverse routine defined.

However, IIRC, Peter Dimov provided an accurate GC with this same
requirement for a traverse routine, called sp_enumerate here:

   http://www.pdimov.com/cpp/shared_ptr_0x.html#cycles

and a similar method, AFAICT, for determining the external pointers to
an object.  However, after briefly looking at the code:

   http://www.pdimov.com/cpp/enable_sp_collect.cpp

I can't tell where the trial decrements for each external reference  is
done, which is what both [Chritopher,1984] and [Lins,1992a] methods
do, at least according to:

   In both cases, trial decrements are made to the reference coungs of
   the descendants of cells encountered.

from p. 71 of the aforementioned gcbook; however, I do remember going
over that code (or an earlier version of it) where it was doing
essentially the same thing to determine the number of external
counts. Maybe Peter could clarify.

So, the question now is:

   How is the HnxGC method for precisely collecting cycles better than
   the enable_sp_collect.cpp method?

-regards,
Larry