[boost] Cyclic pointers - a comparison of known Boost efforts

From: Chuck Messenger (chuckm_at_[hidden])
Date: 2003-05-30 12:56:23

Gregory Colvin wrote:
> On Friday, May 30, 2003, at 09:56 America/Denver, Chuck Messenger wrote:
> 
>> ...
>> What I'm trying to develop (or even better, find) is a workable C++ 
>> library which supports cyclic structures, handling garbage collection 
>> for you, without resorting to a systemic (and non-portable) approach 
>> like the Boehm collector.  I want to build regular-old, C++ standard 
>> libraries upon this cyclic library -- I don't want to require users of 
>> my libraries to use my garbage collection system.  It needs to be 
>> perfectly invisible to the user (and ideally, as invisible as possible 
>> to the library writer).
> 
> 
> There are a few attempts laying around various places in Boost, but
> I've lost track of where they all are, how they all work, and what
> their relative advantages and disadvantages are.  If someone could
> pull this information together it might help to get this discussion
> out of the cycle it seems caught in ;->

Let's do it!  I've been working (slowly!) toward just that.

Very briefly, here's what I've found so far -- please tear it apart at will:

1.  Systemic approaches like the Boehm collector (no Boost libs).  These
     aren't, and can't be, anything close to Standard C++, so they're out
     of the realm of what I think we on Boost are interested in (for
     inclusion in a Boost library, that is -- we're still interested in
     them...)

2.  sp_collector - by Peter Dimov.  In Boost distro -- see
     boost/libs/smart_ptr/src/sp_collector.cpp.  This is an experimental
     extension to shared_ptr.  It makes the assumption that all
     shared_ptr's are contained within objects owned by other
     shared_ptr's.  It uses the "Boehm-like" trick of scanning raw memory
     to find the shared_ptr's (I believe this is called "conservative
     collection"), so it isn't 100.000% foolproof (but is close).  More
     importantly, it doesn't work with the STL containers, which makes it
     nothing more than an experimental toy (but an interesting one).

3.  cyclic_ptr - by Greg Colvin (i.e. yours).  See
     http://groups.yahoo.com/group/boost/files/smart_pointers/cyclic_ptr.
     I haven't studied it yet, but based on what I've read in recent
     threads, I believe it works by tracking the locations of all
     cyclic_ptr objects, in a global map. This means it *is* 100.000%
     foolproof (unlike sp_collector).  However, it also means there is a
     severe overhead to copying cyclic_ptr's.  In order to "discover"
     the object dependency graph of an object, it makes a copy of it.
     During the copy operation, cyclic_ptr's are put in a special mode,
     so that during their operator=(), they tally the dependency graph.
     One problem with this is that each object must then be copyable.
     This can be messy if you're making extensive use of non-copyable
     objects, such as in the Boost Threads library.  Also, it can lead
     to unbounded inefficiency in the case of objects with lots of
     non-cyclic-ptr material, which is intended to be copyable (for
     example, imagine an image class).

4.  shared_cyclic_ptr - by Larry Evans.  See
     http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr.
     This one seems to be under active development right (new
     version uploaded a day or two ago).  Again, I haven't studied
     this one yet.  About the "discovery" problem, Larry writes:
     "[it] works around this by using a smart ptr enumerator
     function specialized for each type of container".  As I
     understand this, it means that shared_cyclic_ptr objects
     must either be within objects owned by another shared_cyclic_ptr
     (as with sp_collector), or they can be in "tagged" STL
     containers, e.g.:

         template <typename T> struct SpecialList : public list<T>,
                                    public SpecialTag { };

     That would be a best case.  Or, it might be necessary to do
     something much messier, like this:

         template <typename T> struct SpecialList {
             // Implement wrapper for each std::list function...
         private:
             list<T> list_;
         };

     Perhaps Larry can comment.

5.  juju_ptr -- my own effort, under development.  Perhaps if I
     finish it, I'll upload it for public examination.  If you're
     even luckier, I may change the name.  I'm using a unique (I
     think) discovery method -- some "wicked juju" (but, I believe,
     adhering to Standard C++, and portable) -- which avoids
     cyclic_ptr's need to copy instances.  For the STL containers,
     it uses a public inheritance tagging method:

         template <typename T> struct j_list : public list<T>,
                                    public SpecialTag { };

     All the std::list methods bleed through.  For example, it doesn't
     require a special list<>::iterator.  It also avoids cyclic_ptr's
     need to keep a global map of cyclic_ptr instances.  To clarify,
     juju_ptr's must exist either directly in objects owned by another
     juju_ptr (as with sp_collector), or in arbitrary structures within
     j_ versions of the STL containers.  It uses a "perfect discovery"
     method -- not conservative collection, like sp_collector.

Those are all the relevant cyclic ptr efforts I'm aware of.

Breaking it down another way:  these are the parameters of any cyclic 
ptr lib:

1.  Standard C++ portability

         Boehm - no (I keep mentioning it only as a reference -- it
                     clearly isn't relevant to Boost)

         sp_collector - yes (except that we need to know the pointer
                            alignment constraints on each platform --
                            an easy hurdle)

         cyclic_ptr - yes.

         shared_cyclic_ptr - I imagine so.

         juju_ptr - yes (I believe, but this isn't your father's
                    C++ code...)

2.  Discovery method:

         Boehm - examines all memory, including stack and registers,
                 looking for possible object pointers.

         sp_collector - examines the raw memory of all objects owned
                        by shared_ptr's, looking for shared_ptr instances
                        (based on a unique signature, and pointed-to
                        address).

         cyclic_ptr - performs full object copy -- T *p; ...; *p = *p.
                        During this operation, cyclic_ptr's are put in a
                        mode where they accumulate their references.

         shared_cyclic_ptr - not sure.

         juju_ptr -  special juju is done.  Not necessary to copy owned
                     objects, ala cyclic_ptr.  It is required that
                     "internal" juju_ptr's be stored within j_ versions
                     of STL containers -- not in plain-vanilla STL
                     containers.

3.  Efficiency of pointer copying:

         Boehm  -  extremely efficient - pointers are just plain C-style
                   pointers -- not even smart pointers are required.

         sp_collector  -  shared_ptr's are used.  Copying requires the
                   updating of one or two reference counts.

         cyclic_ptr - very inefficient -- copying requires the updating
                    of a global map.   Especially bad in multi-threaded
                    applications.

         shared_cyclic_ptr - Probably like shared_ptr.

         juju_ptr  -  like shared_ptr.

4.  Restrictions on the location of pointers ("internal" and
     "external" -- an internal pointer is one which will be
     destroyed when the owning object is destroyed -- generally,
     and unless otherwise indicated, there are no restrictions on
     where external pointers may be stored):

         Boehm  -  absolutely none.

         sp_collector - internal shared_ptr's may only exist directly
                    within an allocated object which is owned by another
                    shared_ptr.  Very restrictive -- for example,
                    internal shared_ptr's can't be stored, directly or
                    indirectly, in an STL container.

         cyclic_ptr  - no restrictions on internal pointers

         shared_cyclic_ptr - probably like juju_ptr, except that the
                    STL container wrappers may not be "thin" (i.e. e.g.
                    special iterators may be required).

         juju_ptr - they may only exist directly within an allocated
                    object which is owned by another juju_ptr, or within
                    a "thinly wrapped" library-specific STL container
                    wrapper (e.g. j_list<>, j_vector<>).  Thin wrapping
                    means public inheritance, with no overloading of the
                    underlying STL container's methods.

That's all I know for now.  I'll leave it to others to fill in the 
enormous holes... (and thus will I benefit!)

     - Chuck Messenger