[boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)

From: Chuck Messenger (chuckm_at_[hidden])
Date: 2003-05-28 14:04:53

Larry Evans wrote:
> Chuck Messenger wrote:
> [snip]
> 
>> collections, put them in object heirarchies, etc).  This freedom 
>> should ideally apply both internally (within library L code) and most 
>> importantly, externally (in the code of users of library L).  Crucially,
> 
> Would you require the users to use a smart pointer instead of a raw?
> If not, then you're only option, that I can tell, is use a conservative
> collector like Boehm's.

No -- users don't use pointers -- only objects.  The objects each have 
one pimpl_ (which will be whatever "smart" type "we" - the uber-pointer 
framework designers - want), pointing to the underlying object.

Note:  This is essentially a plain-vanilla Java-style object system 
which I am describing.

>>  The consequence of mis-identification is
>> that you may fail to destroy some unused objects.  If this leads to 
>> nothing worse than some leaked memory, then it's not a real problem -- 
>> it will be a vanishingly small amount of memory.
> 
> This is the justification for Boehm's conservative collector.
>  http://www.hpl.hp.com/personal/Hans_Boehm/gc/

Does the Boehm collector likewise do a full scan of the heap?  I assume 
so...

>> One big problem with this approach is that you end up having to scan 
>> all of your memory.  This could (and for me, would) be an outrageous 
>> proposition, as only a tiny portion of memory relates to my object 
>> set.  Most of it will be raw data (e.g. images, etc).
> 
> This is what Christopher's (alias= global rc mark-scan) algorithm does.
> It's also what mark-sweep algorithms do, i.e. they have to mark all 
> reachable
> objects, and then scan thru the whole heap sweeping the unmarked into the
> garbage collector. However, since this global scan is done, usually,
> infrequently, the time isn't that big a factor, at least compared with the
> updating of reference counts during each pointer copy.
> That's why Boehm's gc should work faster than refcounting.

Any algorithm which scans the entire heap is out of the question.  I 
want to use this garbage-collecting system as a part of a library -- I 
don't want the use of my library to impact the entire program in such a 
dramatic way!  For example, suppose I wrote 2 libraries using this 
uber-pointer framework?  Or suppose someone else wrote a library with a 
different, incompatible uber-pointer equivalent?

Basically, I want my library to behave itself, just like any normal C++ 
library.

>> My own semi-uber pointer implementation (concept):
>>
> [snip]
> 
>> Still, that's something.  It would be necessary to implement your own 
>> containers for {C} objects, for use within I:C objects -- these 
>> containers would themselves be {C} objects.  A very simple container 
>> you get "for free" is an array, which might be enough for some problem 
>> spaces.  Note that externally, you could use regular STL containers, 
>> or anything you want.
> 
> This is the solution implemented (by simply deriving from the stl 
> container)
> by an earlier upload to boost...files/shared_cyclic_ptr.  I've just
> uploaded them again in file, shared_cyclic_ptr.zip.  Explanations
> on output of test are in iplimits.out.  The solution for STL containers
> is in template scoped_cyclic_container in file shared_cyclic_ptr.hpp.
> [snip]

Interesting -- thanks!  I'll give it a look...

However, I thought about deriving from an STL container, and rejected 
it.  The reason is that you don't know how the STL container allocates 
memory.  In order to maintain the system's invariants, it is necessary 
that all "internal" C objects be contained physically within the bounds 
of an I:C object, which all derive from some common base class -- 
Rangeable, say.  The Rangeable 'structors add/remove 'this' to 
map_impl[].  OK, so we make our own map which is-a std::map and is-a 
Rangeable (multiple inheritance).  So far so good.  But what happens 
when std::map allocates memory internally?  We need those internal nodes 
to also be Rangeable, or the system won't work.

Right?

I suppose we could supply our own allocator to std::map -- hmmm....

Or, there could be a limitation that you can't store C objects directly 
in an STL container -- instead, you have to house them in an 
intermediate object which is Rangeable (in effect, you're storing I:C's 
in the STL container, rather than C's).

>> cyclic_ptr.hpp in Boost contributions
>>
>> I studied this a while, but must confess I couldn't wrap my head 
>> around it.  I did find one interesting thing: the way cyclic_ptr 
>> "traces" pointer references is by doing the following:
>>
>>     T *p = reinterpret_cast<T*>(raw memory pointer);
>>     *p = *p;
>>
>> that is, by copying an object onto itself.  This causes copy 
>> constructors to be called on all contained objects.  The copy 
>> constructors are the "hook" by which any embedded cyclic_ptr's are 
>> detected.
> 
> Don't you mean the operator=(T const&)?  At least that's the
> way I understand it.
> [snip]

Right.

>> NoPtr lib -- noptrlib.sourceforge.net
>>
>>  From what I can tell, this library is not at all suitable for what I 
>> want.  It appears to be a set of traditional smart pointers -- with 
>> components which are somewhere between auto_ptr and shared_ptr.  I saw 
>> no mention of detecting dead cyclic object pools.
>>
> The users of such a "sole-owner" gc method believe this happens rarely:
> 
> http://suif.stanford.edu/pipermail/suif-talk/2000-January/000491.html
> 
> However, I agree that it can happen, and if it can, it will (that's my
> experience).

And is certain to happen in my case.

    - Chuck