Re: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)
On Friday, May 30, 2003, at 11:58 America/Denver, Larry Evans wrote: Gregory Colvin wrote: > On Friday, May 30, 2003, at 10:18 America/Denver, Larry Evans wrote: > [snip] >> >> http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/ >> draft-compare.zip might be a good starting point. It >> doesn't include the latest additions and still needs work :(. > > > Wow. Thanks (I guess). Since understanding some of the code was difficult, I think you understood cyclic_ptr better than I do now, and maybe better than I did then ;-> it would sure help if the authors of each of the codes would analyze their own code to check against what's already in draft-compare, or add to draft-compare, as appropriate. Also, it would most likely avoid the "jumping to conclusions" which I was guilty of when evaluating sp_collector earlier in a (this?) thread. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)
Gregory Colvin wrote: > On Friday, May 30, 2003, at 10:18 America/Denver, Larry Evans wrote: > [snip] >> >> http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/ >> draft-compare.zip might be a good starting point. It >> doesn't include the latest additions and still needs work :(. > > > Wow. Thanks (I guess). Since understanding some of the code was difficult, it would sure help if the authors of each of the codes would analyze their own code to check against what's already in draft-compare, or add to draft-compare, as appropriate. Also, it would most likely avoid the "jumping to conclusions" which I was guilty of when evaluating sp_collector earlier in a (this?) thread. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)
On Friday, May 30, 2003, at 10:18 America/Denver, Larry Evans wrote: Gregory Colvin wrote: 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++ [snip] 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 ;-> http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/ draft-compare.zip might be a good starting point. It doesn't include the latest additions and still needs work :(. Wow. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)
Gregory Colvin wrote: 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++ [snip] 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 ;-> http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/ draft-compare.zip might be a good starting point. It doesn't include the latest additions and still needs work :(. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)
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 ;-> ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
RE: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)
> -Original Message-
> From: Chuck Messenger [mailto:[EMAIL PROTECTED]
> Sent: Thursday, May 29, 2003 4:47 PM
> To: [EMAIL PROTECTED]
> Subject: [boost] Re: Cyclic smart pointers (holy grail: the
> uber-pointer)
>
>
> Schoenborn, Oliver wrote:
>
> >>>- You always have A owns A_impl owns B owns B_impl refs A (what your
> >>>original code seems to say), in this case B_impl contains an RRef
> >>>instead of a DynObj and everything works
> >
> > I'd like to hear whether that's your case or not.
>
> No. A and B are completely symmetrical. They each equally
> "own" the other.
Not possible. This has nothing to do with NoPtr or boost::shared_ptr, it's
even true for raw pointers. E.g.
// forget about forward declarations for brevity
struct A {
B* b;
~A() {delete b;} // A owns b
};
struct B {
A* a;
~B() {delete a;} // B owns a
};
A* a = new A;
a->b = new B;
a->b->a = a;
delete a;// *** illegal #1
delete a->b; // *** illegal #2
In illegal#1, a is owned by b means that only b is allowed to delete a, so
calling "delete a" ourselves is illegal (and will lead to double deletion).
In illegal#2, it's b that's being deleted, and same holds as illegal #1. So,
who destroys a and b? No one can and you have a memory leak.
If on the other hand you have
struct A {
B* b;
~A() {delete b;} // A owns b
};
struct B {
A* a; // B does NOT own a
};
then delete a is ok, but delete a->b is still not since a->b is owned by a.
> I looked at NoPtr, and quickly determined that it didn't implement
> garbage collection, so it couldn't solve my problem.
That's good, because NoPtr has nothing to do with garbage collection (though
one could perhaps use it for a form of gc).
> However, I don't understand what NoPtr *does*.
Simplistically,
- DynObj destroys what it owns when it goes out of scope, is reset or
acquires something new, and notifies any RRefs linked to it
- RRef refers to a DynObj, but asserts that DynObj still exists when
accessed
Note that I said simplistically.
Oliver
___
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)
Larry Evans wrote: [snip] See if the current stl_container.cpp can at least traverse your pointer graph correctly. Unfortunately, stl_container.cpp can't work with the stl because it prototypes a "slight" modification to stl to make stl easily gc'ed. If you want to work with the current stl, you'll have to do something similar to scoped_cyclic_container, i.e. derive a class from the stl container whose CTOR stores the method in the descriptor. This is on my todo list. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)
Chuck Messenger wrote:
Larry Evans wrote:
[snip]
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.
Not quite. The scoped_cyclic_ptr was designed to work-around a limitation
of Detlef's method:
http://www.cs.kent.ac.uk/people/staff/rej/cgi-bin/searchbib?pattern=Detl92
This limitation was that it didn't document how than handle container
classes. It only documented how scalars were handled. The adaptation
in scoped_cyclic_ptr (and stl_container) is, as you mentioned, to store
a pointer and offset into a prox_descriptor (see stl_container.cpp)
for each type which contains a proxy (i.e. smart pointer) or a container
of proxies. The pointer and offset is stored by the CTOR for either scalar proxies
(prox_scalar_typed<...>) or the prox_indirect_typed forming part of any
container of proxies (e.g. the test::m_vec_ptest_shared). The pointer points
to an instance of maker_proxiter_abs which produces an iterator over proxies
contained in a subject class (subject is term used for pointee or referent
in GOF) given the start of a subject. (I know, its too complicated, but
I can't think of how to simplify it. Any ideas?)
Nice!
Thanks.
[snip]
Is stl_container.cpp an experimental Boost lib? Where can I get it?
It's in:
http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/stl_container.cpp
You'll also need the col_io library in:
http://groups.yahoo.com/group/boost/files/col_io/
and then there's a simple trace_scope.hpp which I'll upload.
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.
Thanks.
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?
That's at:
http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/shared_cyclic_ptr.zip
It uses an earlier version of method to enumerate pointers in an object. It also
demonstrates how to adapt shared_ptr for to use the method. It also shows
that the enumeration method is pretty much independent of the collection method because
it uses two different methods (one using Detlef's, or offset_iterator method and
one using Colvin's or assign_op_switch) to implement the same gc method (Lin's local
mark-scan). BTW, Lin's method suffers from quadratic behavior with nested cycles
as pointed out in Bacon's paper (I think I made a reference to that earlier. I know
I did in a post responding to one of Terekov's posts). The work-around is
lazy-local mark-scan which maintains a queue of possible garbage nodes. Anyway,
I had a version of this also, but it's been rm'ed from boost long ago.
See if the current stl_container.cpp can at least traverse your pointer graph
correctly.
If it can, then it's easy to use any of the cyclic rc algorithms
(i.e. lazy local mark scan, eager local mark scan, global mark scan).
___
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)
Chuck Messenger wrote: > What is the status of sp_collector.cpp? It's distributed as part of > Boost right now. Is it intended to remain part of the shared_ptr > library? It sounds like it should suit my purposes quite well, after > all... sp_collector.cpp has a "gift" status. ;-) Meaning that it is not one of my priorities to support or maintain it, but if someone finds it useful as a starting point for further work, all the better. Its main purpose was/is to demonstrate that it is possible to write a collector for cyclic shared_ptr structures without altering the shared_ptr specification, i.e. that the spec is flexible enough to handle an optional collector should someone decide to provide one as part of their std::shared_ptr. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)
Chuck Messenger wrote:
> Schoenborn, Oliver wrote:
>
> Imagine that I'm supplying a network simulation library. I have:
>
> #include
> #include
> #include
> #include
>
> using namespace std;
> using namespace boost;
>
> struct Node;
>
> struct NodeImpl : noncopyable {
> NodeImpl(int id) : id_(id) { cout << id_ << " lives\n"; }
> ~NodeImpl() { cout << id_ << " dies\n"; }
> private:
> set nodes_;
> int id_;
> friend struct Node;
> };
>
> struct Node {
> Node(int id) : pimpl_(new NodeImpl(id)) { }
> Node(const Node& n) : pimpl_(n.pimpl_) { }
> void Connect(const Node& n) { pimpl_->nodes_.insert(n); }
> void Disconnect(const Node& n) { pimpl_->nodes_.erase(n); }
> private:
> shared_ptr pimpl_;
> friend bool operator<(const Node& n1, const Node& n2);
> };
>
> bool operator<(const Node& n1, const Node& n2) {
> return n1.pimpl_ < n2.pimpl_;
> }
>
> int main() {
> {
> Node n1(1);
>
> {
> Node n2(2), n3(3), n4(4);
>
> n1.Connect(n2);
> n2.Connect(n2);
> n3.Connect(n3);
> n4.Connect(n4);
> }
>
> cout << "n1 points to the cluster {n2, n3, n4}\n";
> }
>
> cout << "n2, n3, n4 remain alive. That sucks.\n";
> }
This is a graph. The classic "tree structure" combined with reference
counting can only represent (possibly multiply linked) DAGs, but not general
graphs.
One possible representation of a general graph is a vertex pool and a
separate edge pool. This avoids the ownership issues inherent in the tree
representation since now nodes don't own each other, the two pools are the
owners.
Perhaps the boost graph library can help here?
___
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)
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 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] ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)
On Wednesday, May 28, 2003, at 13:04 America/Denver, Chuck Messenger wrote: 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... It marks all objects on the heap pointed to by the machine registers, and all objects pointed to by those objects, and so on. It is conservative in the sense that it cannot generally tell whether a register or memory cell contains a pointer or an integer. 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). Boehm's collector includes functions for allocating pointer-free memory. 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. It does. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
