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

From: Chuck Messenger (chuckm_at_[hidden])
Date: 2003-05-28 19:18:46

Larry Evans wrote:
> Chuck Messenger wrote:
> [snip]

>>>> 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).
> 
> You can specify which cells to scan by specifying it's "kind" during
> allocation ( http://www.hpl.hp.com/personal/Hans_Boehm/gc/gcdescr.html )
> thus there's no need to scan the whole heap.

I read some about the Boehm collector -- it falls in the category of GC 
schemes which take over your whole app.  That is -- it isn't suitable 
for use in a general-purpose library.

>  cyclic_ptr doesn't really
> scan the whole heap, only those "cells" allocated by the cyclic_ptr
> allocator.
> [snip]

It sounds like cyclic_ptr meets the "useable in a general-purpose 
library" test.  My problem with it is the requirement that pointed-to 
objects be copyable.

>> ... 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?
> 
> Right.  scoped_cyclic_ptr (in shared_cyclic_ptr.zip) works around this by
> using a smart ptr enumerator
> function specialized for each type of container.  The specialized function
> is then used to access all the smart ptrs in the container (via the 
> begin() end()
> iterator class).

OK, I see.

In fact, it seems like you don't need any special smart ptr enumerator 
function.  All you do is: you use derived-from versions of the std 
containers, so you can maintain an up-to-date list of references to each 
one.  During GC, for each such container c, "for (it = c.begin(); it != 
c.end(); ++it)", you treat *it as a Rangeable -- any {C} references in 
the range [&*it, &*it + sizeof(*it) - 1] are flagged as internal.

Nice!

> Thus, there's only the for the collector to know the
> start of the container, not the start of each element of the container, 
> which
> can be derived from the smart ptr enumerator function.  (The 
> stl_container.cpp
> should provide another example of this).  The I:C pointers you're 
> referring to
> I think correspond to the prox_policied<OwnershipPolicy> and the 
> prox_indirect
> classes in stl_container.cpp.

Is stl_container.cpp an experimental Boost lib?  Where can I get it?

>> I suppose we could supply our own allocator to std::map -- hmmm....
> 
> John Skaller suggested a similar solution, but said it wasn't
> workable with current stl design:
> ( http://aspn.activestate.com/ASPN/Mail/Message/1149745 )

Makes sense -- it seems pretty messy.  It's not clear that an STL 
container is *required* to allocate from the allocator (maybe it is - 
I'm just not certain).  Or, even that it is required, it isn't clear how 
the STL container would signal which range of the allocated memory was 
being used to store objects.

I like your "iterate through tagged STL containers" method.  The library 
writer (the one using the cyclic smart pointer system) has to take care 
to store {C} objects only in appropriately tagged containers.  But they 
get to use any containers they want.

Not too shabby.

I'd love to examine your scoped_cyclic_ptr lib -- to see if I can make 
use of it.  Perhaps I can help you flesh out requirements, if it's close 
enough to what I need.  Is it available for download?

     - Chuck Messenger