Boost logo

Boost :

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

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
     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
     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...
             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

         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

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

         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

Boost list run by bdawes at, gregod at, cpdaniel at, john at