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

From: Gregory Colvin (gregory.colvin_at_[hidden])
Date: 2003-05-30 13:05:49

Thanks, but your description of cyclic_ptr is pretty far off the mark.
It does not maintain a global map, and copying cyclic_ptr cost the same
as copying shared_ptr.  The special assignment mode is used only during
the mark phase of a collection, and costs more or less the same as any
other discovery method.

On Friday, May 30, 2003, at 11:56 America/Denver, Chuck Messenger wrote:

> 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
>
>
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost