|
|
Boost : |
From: Larry Evans (jcampbell3_at_[hidden])
Date: 2003-05-30 16:37:34
Chuck Messenger wrote:
> Gregory Colvin wrote:
[snip]
>> 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 ;->
[snip]
> Very briefly, here's what I've found so far -- please tear it apart at
> will:
>
[snip]
>
> 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.
As illustrated in:
shared_cyclic_ptr.zip
(boost/shared_cyclic_ptr/shared_cyclic_ptr.hpp)
in class:
scoped_cyclic_container
< Container
, Element
, cyclic_count_gc<GcMethod,ip_offset_iterator>
>
, public Container
<shared_cyclic_ptr
<Element
,cyclic_count_gc<GcMethod,ip_offset_iterator>
>
>
, private detail
::mk_proxiters_descriptor_static
::proxiter_record
the scoped_cyclic_container does not include the STL container (the
Container), instead it inherits it. This is simply to make the
interface the same without having to forward all method calls. The
container is "tagged" by inheritance from proxiter_record. However,
it's clearer in:
http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/stl_container.cpp
In that file, the function of proxiter_record is done by:
prox_container_allocator<Value>
in:
mod::vector
<Value
,Allocator=prox_children
::detail_iterators
::prox_container_allocator<Value>
>
NOTE:
One reason for this change is to see if the prox_children design
pattern (that's what I started calling it) could be adapted for use
with stl with as little change as possible. Hence, by just
specializing the container allocator, and then changing all
container code to use a prox_container_allocator<Value>
::root_pointer in place of the "root pointer" to the container, all
containers would be garbage collected. Since, I assumed, each
container must have some type of "root pointer" in its
implementation, it should work for all stl containers. For
uncollected containers, allocator<Value>::root_pointer would simply
be a do-nothing pointer-wrapper around a Value*.
The ONLY reason for making the root_pointer a pointer-wrapper is to
enable storing:
1) a constructor for the "smart ptr enumerator function"
mentioned above
2) an offset from whatever "subject" (using the GOF
terminology ) contains the container.
"WHOA...!" you say, "what is this 'subject"? I thought we were
talking about the constructor for an stl-like container?" Well,
that's where Detlef's genius appears. This "subject" is actually
created during construction of a static variable (so it's constructed
before the start of main). The SOLE purpose of this variable,
namespace prox_children
{
descriptor_builder<Subject>
descriptor_builder<Subject>
::this_descriptor
;
}
is to create a prox_children::prox_descriptor for Subject which
precisely describes the smart pointers in Subject which contain
pointers to objects to be garbage collected. This description
consists of a map of maker_proxiter_abs* to offsets within subject
where the proxies are located. Thus, given:
Subject* a_subj
offset a_offset
mk_proxiter_abs* a_maker
the collector can enumerate all the proxies contained in a_subj which
are of a particular type, i.e. the type corresponding to the a_maker.
For example, for a vector<T>, the corresponding a_maker would produce
an iterator somehow derived from vector<T>::iterator, and for list<T>,
the a_maker would produce an iterator from list<T>::iterator. For a
scalar proxy, prox_scalar_typed<T,ownership_policies>, the iterator simply
calculates ((char*)a_subj)+a_offset and casts it to
prox_scalar_typed<T,ownership_policies>*. This desription of the
iterator for prox_scalar_typed is essentially what Detlef described in
his 92 article.
[snip]
>
> 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
>
> shared_cyclic_ptr - I imagine so.
Yes.
>
> 2. Discovery method:
>
>
> shared_cyclic_ptr - not sure.
creates a "prox_descriptor" for each different class to be garbage
collected. The collector then uses these prox_descriptor's to
enumerate the pointers within an object. This means that there must
be some way to associate a descriptor with each gc'ed object. This is
easy to do if the type of the collector knows the object's type. In
that case, the descriptor is
prox_children::prox_description_of<T>::ptr() for any type, T. With
shared_ptr, the type information is stored within the counted_base* in
the derived class, counted_base_impl<T,D> (at least it was at the time
shared_cyclic_ptr.zip was written). Hence, shared_ptr could be
adapted to find cycles with very little additional overhead.
BTW, the prox_descriptor performs the same function as Boehm's
GC_descr:
hence, if Boehm's could be modified to use prox_descriptor instead,
the descriptor creation would be almost automatic (you'd still have to
declare the static:
descriptor_builder<Subject>::this_descriptor
[snip]
>
> 3. Efficiency of pointer copying:
>
> shared_cyclic_ptr - Probably like shared_ptr.
Yes.
>
> 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.
If an object to be collected is pointed to from the root, either
indirectly or directly, by an object allocated with
GC_local_malloc_atomic, then it won't be collected. Of course, this
is an error on the programmer's part. For example, he at one time
during his development knew the object was atomic, but as his program
evolved, it became non-atomic, but he forgot to change it.
I only bring this up to ease comparison with shared_cyclic_ptr.
[snip]
>
> 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).
If there is a pointer path between gc'ed object, A, and another gc'ed
object B, and that path is broken with a pointer other than a
prox_scalar_void<...> or prox_container_allocator<T>::root_pointer or
a pointer in a container whose "root pointer" is a
prox_container_allocator<T>::root_pointer, then A or B may not be
collected.
This means the programmer must explicitly specify which pointers are
used in garbage collection. In constrast, with the Boehm collector
(BC), (I think) a default allocator is specified which creates a
gc'ed object. If the programmer doesn't want this, he either
specifies atomic allocation (meaning the pointee is not to be
collected and does not contain the any pointers to collectable
objects) or uncollectable allocation (the object is not collected, but
may contain pointers to collectable objects):
The atomic allocation in BC corresponds to a raw pointer in
stl_container.cpp. Uncollectable allocation in BC corresponds to
prox_scalar_void <proxies ::owner_single >, and the collectable
allocation in BC corresponds to prox_scalar_void <proxies
::owner_shared >.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk