Boost logo

Boost :

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

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