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

From: Larry Evans (jcampbell3_at_[hidden])
Date: 2003-05-28 15:37:11

Chuck Messenger wrote:
[snip]
> Does the Boehm collector likewise do a full scan of the heap?  I assume 
> so...
Yes. From p. 28 of _Garbage Collection_, 1996
( http://www.cs.kent.ac.uk/people/staff/rej/gcbook/gcbook.html )
   "all cells are examined by the sweep"
However, this is theory.  In actual implementation, there's workarounds.
(See next comment).
> 
> 
>>> 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.  cyclic_ptr doesn't really
scan the whole heap, only those "cells" allocated by the cyclic_ptr
allocator.
[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?
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).  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.

> 
> 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 )
> 
[snip]