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
