Re: [boost] Shared_ptr "mini garbage collector"
Larry Evans wrote: > Peter Dimov wrote: > > From: "Larry Evans" <[EMAIL PROTECTED]> [snip] > I'm pretty sure there a reference to it in some of the compare docs > or code in the files/shared_cyclic_ptr directory. I thought I'd be more help. The reference is: David L. Detlefs. "Garbage collection and runtime typing as a C++ library". In USENIX C++ Conference, Portland, Oregon, August 1992. USENIX Association. The version in shared_cyclic_ptr uses a static flag ( mk_offsets_descriptor_static::c_subject_start_val() )indicating whether or not the "internal pointers" are being calculated for a particular "subject" class. Before this flag is set, memory for an instance of this subject class is allocated ( in mk_internal_pointers_descriptor_of ::CTOR ). The start and end of this memory are also placed in static variables (Or it should be). and then placement new is used to create it. Each smart pointer (or "proxy", to use the shared_cyclic_ptr terminology) as a prox_record superclass which records the offset of the proxy from the start of the subject (available from the aforementioned c_subject_start_val()). These offsets are stored in mk_internal_pointers_descriptor_of ::m_ptr_offsets and subsequently used to find the internal pointers of a subject given the start address of that subject. The above paragraph basicly describes Detlef's method. However, there's a problem with containers, like a vector of proxies. To handle this, a function for accessing the proxies of the container (cyclic_count_ip_offset_iterator::mk_proxiter_fun_type) is stored in the ip descriptor. With scoped_cyclic_container (in shared_cyclic_ptr.hpp), this avoids problems with most stl-like containers. John Maddox enountered this problem with his felix gc. If the definitions of the stl container were modified to specialize the "root" pointer of the container (e.g. the vector::front or the head pointer in list) to be a proxy with the prox_record superclass, then this might be easily added to stl, thus easing the migration to gc for c++. > > does it require programmer > > support? > > > > Yes. It requires declaration of a single static variable for each > class that's garbage collected. It looks like this: > > ip_descriptor_of > ip_descriptor_of > ::c_mk_descriptor > ; At least in my latest incantation of my gc code. However, in the shared_cyclic_ptr directory, this appears as: boost::mk_internal_pointers_descriptor_of > >:: c_my_type ; in the iplimits.cpp file. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
At 10:22 AM 1/8/2003, David Abrahams wrote: >Greg Colvin <[EMAIL PROTECTED]> writes: > >> At 04:02 PM 1/7/2003, David Abrahams wrote: >>>... >>> >>>I can barely think of a reasonable design where GC is a big design win >>>;-) >> >> A Python interpreter? > >I obviously have a poor imagination ;-) More seriously, I've never found GC necessary except for writing interpreters for garbage collected languages. But once GC is there I have found it very liberating to not worry about memory leaks and dangling pointers, and not think about ownership except for non-memory resources. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
Greg Colvin <[EMAIL PROTECTED]> writes: > At 04:02 PM 1/7/2003, David Abrahams wrote: >>... >> >>I can barely think of a reasonable design where GC is a big design win >>;-) > > A Python interpreter? I obviously have a poor imagination ;-) -- David Abrahams [EMAIL PROTECTED] * http://www.boost-consulting.com Boost support, enhancements, training, and commercial distribution ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
Peter Dimov wrote: From: "Larry Evans" <[EMAIL PROTECTED]> [snip] This scan will also have to follow plain pointers. Plain pointers would have to be followed by a real collector, but why should a "simple cycle-breaker" bother? The iplimits.txt file in the shared_cyclic_ptr files directory also illustrates why raw pointers need to be followed. Search for: 2)"pointer cycle with raw cut" - This also hints at what was lacking in Detlef's article: an explanation of how to handle containers of smart pointers. This is handled by the shared_cyclic_container template defined in shared_cyclic_ptr.hpp. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
At 04:02 PM 1/7/2003, David Abrahams wrote: >... > >I can barely think of a reasonable design where GC is a big design win >;-) A Python interpreter? ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
Peter Dimov wrote: > From: "Larry Evans" <[EMAIL PROTECTED]> [snip] >>Why not use the Delef approach as demonstrated in shared_cyclic_ptr to > > avoid > >>false positives altogether? > > > I'm not familiar with Detlef's approach... I'm pretty sure there a reference to it in some of the compare docs or code in the files/shared_cyclic_ptr directory. > does it require programmer > support? > Yes. It requires declaration of a single static variable for each class that's garbage collected. It looks like this: ip_descriptor_of ip_descriptor_of ::c_mk_descriptor ; The c_mk_descriptor default CTOR creates a descriptor for test_subj. This descriptor is accessed with: bridge_stk_proxiterator::ip_descriptor const& subj_desc = ip_descriptor_of::the_descriptor() The iterator over smart pointers contained within an object of type, test_subj, is created as follows: test_subj a_subj; bridge_stk_proxiterator subj_proxiter(subj_desc, &a_subj); subj_proxiter iterates over all the shared_cyclic_ptr's and (hopefully in the near future) all the unshared_cyclic_ptrs contained within a_subj. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
Peter Dimov wrote:
From: "Larry Evans" <[EMAIL PROTECTED]>
[snip]
This doesn't look correct to me... did you mean something like
struct X
{
Y * p;
explicit X(Y * p): p(p) {}
~X() { delete p; }
};
struct Y
{
shared_ptr p;
};
int main()
{
Y * py = new Y;
shared_ptr px(new X(py));
py->p = px;
px.reset();
}
?
Yes. I had thought about the need to delete the Y* in the
X::DTOR, but that was days ago and I forgot to include it.
I also thought a little more about it and what I was suggesting
was more like:
struc Y;
struct X
{
boost::unshared_cyclic_ptr y; //cyclic involves this arc.
explicit X(void): y(new Y) {}
};
struct Y
{
boost::shared_cyclic_ptr x;
};
Where {unshared|shared}_cyclic_ptr use the detlef method to
record their offsets and hence enable tracing the pointer graph.
Then I'd imagine you'd ask, why not just use a shared_ptr instead
of bothering with unshared. The only answer I can think of is
that maybe that reflects better the meaning of the variable y.
The programmer knows it's never shared; so, he decides to
be explicit about it with unshared_ptr. If he had used
shared_ptr, then someone maintaining his code would have to wonder
who else is sharing this Y? Also, the overhead for unshared_ptr
would be at least a little less than shared_ptr (no reference count
or mark bit and no updating the reference count).
___
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
From: "Larry Evans" <[EMAIL PROTECTED]>
> > Currently I use a conservative scan that assumes that shared_ptr
instances
> > have a layout of
> >
> > T * px;
> > counted_base * pi;
> > int id;
> >
> > with pointers being aligned on a DWORD boundary. 'pi' must be in the
count
> > map, and 'id' must be detail::shared_count::id. (It's possible to test
'px'
> > for validity too.) False positives should be extremely rare, but could
not
> > be ruled out entirely, and hence, breaking cycles may potentially
corrupt
> > the object.
> Would false positives be any less frequent than in the BW conservative
collector?
BW = Boehm-Weiser? AFAIK BW false positives happen when a memory location
resembles a valid heap address, and are much more likely.
> Why not use the Delef approach as demonstrated in shared_cyclic_ptr to
avoid
> false positives altogether?
I'm not familiar with Detlef's approach... does it require programmer
support?
> > Plain pointers would have to be followed by a real collector, but why
should
> > a "simple cycle-breaker" bother?
> >
> Because the following would require it in order to find the cycle:
>
> struc Y;
> struct X
> {
>Y* y; //cyclic involves this arc.
> };
> struct Y
> {
>boost::shared_ptr x;
> };
>
> int main()
> {
> boost::shared_ptr p1(new X);
> boost::shared_ptr p2(new X);
>
> p1->y.x = p2;
> p2->y.x = p1;
>
> }
This doesn't look correct to me... did you mean something like
struct X
{
Y * p;
explicit X(Y * p): p(p) {}
~X() { delete p; }
};
struct Y
{
shared_ptr p;
};
int main()
{
Y * py = new Y;
shared_ptr px(new X(py));
py->p = px;
px.reset();
}
?
___
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
Peter Dimov wrote:
From: "Larry Evans" <[EMAIL PROTECTED]>
1. Find the two X objects (let's call them x1 and x2) on the heap, and
scan
Wouldn't this scan have to be either conservative, like BW, or use some
way
to determine the precise location of the shared_ptr's within, .e.g.
p1->get()?
Currently I use a conservative scan that assumes that shared_ptr instances
have a layout of
T * px;
counted_base * pi;
int id;
with pointers being aligned on a DWORD boundary. 'pi' must be in the count
map, and 'id' must be detail::shared_count::id. (It's possible to test 'px'
for validity too.) False positives should be extremely rare, but could not
be ruled out entirely, and hence, breaking cycles may potentially corrupt
the object.
Would false positives be any less frequent than in the BW conservative collector?
Why not use the Delef approach as demonstrated in shared_cyclic_ptr to avoid
false positives altogether?
This scan will also have to follow plain pointers.
Plain pointers would have to be followed by a real collector, but why should
a "simple cycle-breaker" bother?
Because the following would require it in order to find the cycle:
struc Y;
struct X
{
Y* y; //cyclic involves this arc.
};
struct Y
{
boost::shared_ptr x;
};
int main()
{
boost::shared_ptr p1(new X);
boost::shared_ptr p2(new X);
p1->y.x = p2;
p2->y.x = p1;
}
___
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
"Peter Dimov" <[EMAIL PROTECTED]> writes: > From: "David Abrahams" <[EMAIL PROTECTED]> >> >> Yes, but IIUC the reason the library's not doing it is because you >> might get the order wrong, which could cause a problem like a dangling >> pointer needed for some destructor. > > Not really... The library's not currently doing it because it hasn't been my > goal to provide a "real" garbage collected pointer. sp_debug_hooks.cpp is an > example that demonstrates what can be done with the debug hooks called by > shared_ptr; code using it operates in "safe mode" (or slightly safer mode.) > IOW a shared_ptr cycle is still not supposed to happen in bug free programs. > > That aside, can you think of a reasonable design that does not depend on > intentionally created shared_ptr cycles, but still needs a correct > destruction order when a cycle is broken? I can barely think of a reasonable design where GC is a big design win ;-) In my work, ownership relationships are usually very obvious. When they're not, destruction does nothing but release resources. -- David Abrahams [EMAIL PROTECTED] * http://www.boost-consulting.com Boost support, enhancements, training, and commercial distribution ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
From: "David Abrahams" <[EMAIL PROTECTED]> > > Yes, but IIUC the reason the library's not doing it is because you > might get the order wrong, which could cause a problem like a dangling > pointer needed for some destructor. Not really... The library's not currently doing it because it hasn't been my goal to provide a "real" garbage collected pointer. sp_debug_hooks.cpp is an example that demonstrates what can be done with the debug hooks called by shared_ptr; code using it operates in "safe mode" (or slightly safer mode.) IOW a shared_ptr cycle is still not supposed to happen in bug free programs. That aside, can you think of a reasonable design that does not depend on intentionally created shared_ptr cycles, but still needs a correct destruction order when a cycle is broken? ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
"Peter Dimov" <[EMAIL PROTECTED]> writes: > Currently I use a conservative scan that assumes that shared_ptr instances > have a layout of > > T * px; > counted_base * pi; > int id; It's easy enough to enforce that by inheriting from a POD struct. Don't know about the next part, though: > with pointers being aligned on a DWORD boundary. -- David Abrahams [EMAIL PROTECTED] * http://www.boost-consulting.com Boost support, enhancements, training, and commercial distribution ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
From: "Larry Evans" <[EMAIL PROTECTED]> > > 1. Find the two X objects (let's call them x1 and x2) on the heap, and scan > Wouldn't this scan have to be either conservative, like BW, or use some way > to determine the precise location of the shared_ptr's within, .e.g. p1->get()? Currently I use a conservative scan that assumes that shared_ptr instances have a layout of T * px; counted_base * pi; int id; with pointers being aligned on a DWORD boundary. 'pi' must be in the count map, and 'id' must be detail::shared_count::id. (It's possible to test 'px' for validity too.) False positives should be extremely rare, but could not be ruled out entirely, and hence, breaking cycles may potentially corrupt the object. > This scan will also have to follow plain pointers. Plain pointers would have to be followed by a real collector, but why should a "simple cycle-breaker" bother? ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
"Peter Dimov" <[EMAIL PROTECTED]> writes: > From: "David Abrahams" <[EMAIL PROTECTED]> >> "Peter Dimov" <[EMAIL PROTECTED]> writes: >> >> > It's true that, in general, there is no safe way to break the cycle; x1 > may >> > keep a raw pointer to x2, or it might be a X invariant that X::p is >> > non-empty, causing ~X to fail. This is why the final decision to break > the >> > cycles should be left to the user, and the collector should not >> > automatically reclaim memory. Still, most reasonable classes would be >> > collect-friendly. >> >> Isn't the biggest problem one of system design? How does the user >> write the cycle-breaking code which does different things based on the >> dynamic type of the objects being referenced? > > The user doesn't need to write any cycle-breaking code. All that is > needed is to reset() the shared_ptr instances that keep the cycle > alive. I.e. the requirement is that the object's invariants must not > be broken if a shared_ptr member is suddenly reset. > > It's not necessary to know the T in shared_ptr in order to reset it if > shared_ptrs are layout-compatible (true on most implementations.) Yes, but IIUC the reason the library's not doing it is because you might get the order wrong, which could cause a problem like a dangling pointer needed for some destructor. How will the user decide the order if not by examining T? -- David Abrahams [EMAIL PROTECTED] * http://www.boost-consulting.com Boost support, enhancements, training, and commercial distribution ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
Peter Dimov wrote:
From: "William E. Kempf" <[EMAIL PROTECTED]>
I don't follow this. How does the user prevent the destructors from
referencing the other
object(s) participating in the cycle which may no longer exist? The only
safe way to break
the cycle is to have intimate knowledge about the objects participating in
the cycle and do
what ever clean up is required in a determistic manner *before* the
object's are destroyed
and the memory is freed.
(please use line wrapping)
Consider the original example:
struct X
{
boost::shared_ptr p;
};
int main()
{
boost::shared_ptr p1(new X);
boost::shared_ptr p2(new X);
p1->p = p2;
p2->p = p1;
p1.reset();
p2.reset();
break_cycles();
}
Here is what break_cycles would do:
An alternative is to modify the cyclic_count_gc_local_mark_scan.hpp
file I uploaded to the shared_cyclic_ptr directory on about 9/21/02.
This modifcation would not only restore the refcounts for the live object
but also, or almost also, for the dead ones. Whenever the restoration
encounters a cycle (it could keep track via some mark on the object
indicating it was earlier visted on the stack) it would zero the pointer and
not add the 1, thus breaking the cycle. Then it would delete the original
arg to local_mark_scan (since if any objects are deleted, this one has to be
one of them), and everything would work fine. That is, everything work
work fine except you wouldn't know which node in the cycle is the first one
to be an argument to local_mark_scan.
I haven't tested any of this, but so far I can't see a flaw (except for the
uncertainty about the which is the first delete in the cycle).
1. Find the two X objects (let's call them x1 and x2) on the heap, and scan
Wouldn't this scan have to be either conservative, like BW, or use some way
to determine the precise location of the shared_ptr's within, .e.g. p1->get()?
This some way could be, for example, that used in the shared_cyclic_ptr
directory.
This scan will also have to follow plain pointers. In order to do that
precisely using smart pointers and the method in shared_cyclic_ptr, you'd have
to use another type of smart pointer, e.g. scoped_uncollected_ptr, which only
records its offset in the containing subject, like shared_cyclic_ptr does
in the files/shared_cyclic_ptr directory.
I'm working on this now. I could post it, but it's incomplete. I could use
some feedback though. It's uses a "bridge_iterator" instead of the function
stack, cyclic_count_ip_base::graph_traverser_base::m_visit_parent_stk in
cyclic_count_ip_base.hpp. Because of this, it should be easier to understand.
___
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
From: "David Abrahams" <[EMAIL PROTECTED]> > "Peter Dimov" <[EMAIL PROTECTED]> writes: > > > It's true that, in general, there is no safe way to break the cycle; x1 may > > keep a raw pointer to x2, or it might be a X invariant that X::p is > > non-empty, causing ~X to fail. This is why the final decision to break the > > cycles should be left to the user, and the collector should not > > automatically reclaim memory. Still, most reasonable classes would be > > collect-friendly. > > Isn't the biggest problem one of system design? How does the user > write the cycle-breaking code which does different things based on the > dynamic type of the objects being referenced? The user doesn't need to write any cycle-breaking code. All that is needed is to reset() the shared_ptr instances that keep the cycle alive. I.e. the requirement is that the object's invariants must not be broken if a shared_ptr member is suddenly reset. It's not necessary to know the T in shared_ptr in order to reset it if shared_ptrs are layout-compatible (true on most implementations.) ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: Re: [boost] Shared_ptr "mini garbage collector"
(Sorry for any line break problems... more normal mail system is down because my Linux box has crashed, and the temporary access I have to e-mail is a cheap webmail interface for which I have little control over the formatting.) > From: David Abrahams <[EMAIL PROTECTED]> > "Peter Dimov" <[EMAIL PROTECTED]> writes: > > > It's true that, in general, there is no safe way to break the cycle; x1 may > > keep a raw pointer to x2, or it might be a X invariant that X::p is > > non-empty, causing ~X to fail. This is why the final decision to break the > > cycles should be left to the user, and the collector should not > > automatically reclaim memory. Still, most reasonable classes would be > > collect-friendly. > > Isn't the biggest problem one of system design? How does the user > write the cycle-breaking code which does different things based on the > dynamic type of the objects being referenced? That's basically the question I had, but much better worded. With out a solution for this, I think it's better to just call the destructors and leave it up to the user to write "garbage collector safe destructors", which is the norm any way. William E. Kempf [EMAIL PROTECTED] ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
At 01:23 PM 1/7/2003, Peter Dimov wrote: >From: "Peter Dimov" <[EMAIL PROTECTED]> >> From: "Greg Colvin" <[EMAIL PROTECTED]> >> > My old cyclic_ptr code is still somewhere on the Boost pages, >> > and might offer a better solution to these problems. >> >> Indeed. After having reinvented that wheel, I am now (finally) able to >> understand cyclic_ptr. ;-) > >As it turns out, that wheel has been invented by > >Christopher, Thomas W. >Reference Count Garbage Collection >Software-Practice and Experience >Vol.14(6), pp.503-507, June 1984 Yes, Christopher's work was the inspiration for cyclic_ptr, but I made some changes to adapt it to C++. >as referenced in Larry Evans' comparison > >http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/draft-compare.zi >p > >___ >Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
From: "Peter Dimov" <[EMAIL PROTECTED]> > From: "Greg Colvin" <[EMAIL PROTECTED]> > > My old cyclic_ptr code is still somewhere on the Boost pages, > > and might offer a better solution to these problems. > > Indeed. After having reinvented that wheel, I am now (finally) able to > understand cyclic_ptr. ;-) As it turns out, that wheel has been invented by Christopher, Thomas W. Reference Count Garbage Collection Software-Practice and Experience Vol.14(6), pp.503-507, June 1984 as referenced in Larry Evans' comparison http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/draft-compare.zi p ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: Re: [boost] Shared_ptr "mini garbage collector"
At 11:04 AM 1/7/2003, William E. Kempf wrote: >> From: Greg Colvin <[EMAIL PROTECTED]> >> At 09:23 AM 1/7/2003, Peter Dimov wrote: >> >From: "William E. Kempf" <[EMAIL PROTECTED]> >> >> >> >> I think that extending it to free memory in cycles would be a great idea. >> >Of course, this opens a large can of worms about how to handle destruction >> >of objects which refer to each other...< >> > >> >One possible approach is to return a list of references to the "offending" >> >shared_ptr instances to the user, who can then reset() them as appropriate. >> >Actually it's not as simple as that since a reset() can invalidate some of >> >the returned references; the shared_ptr instances would first need to be >> >copied to a temporary container, the originals reset(), and the temporary >> >container destroyed, but the general idea is the same. >> >> Finalization semantics is of course a very big can of worms >> that has kept a lot of GC experts arguing for years. But I >> take the success of Java as evidence that getting it right >> might not be all that important. > >The "Java solution" is to not have a solution. Finalizers need never be called in >Java. Right. You need finally clauses for most resource management. A GC for C++ could just as easily never call destructors, and provide a separate mechanism for optional finalizers. > I'd prefer to always call the destructors, with the knowledge that dereferencing a >GC pointer that's participating in a cycle during the destructor results in undefined >behavior. I can usually avoid doing this. That is one reasonable approach. The collector can make it easier by providing a topological sort of the soon-to-be-dead objects, so that you can safely dereference pointers in the destructors. But then you have to do something else for cycles. Like I said, the GC experts have been discussing this for years without any clear resolution. >> >> I think that full GC is one of the major things missing from the C++ >> >language, and the appeal of a smart pointer approach, where I pay for GC >> >only when I want/need it, is a great idea.< >> >> A smart pointer approach is the only way I know to write a >> portable collector, but it is not really the best way to >> write a high-performance collector. My preference is to >> have a special new(gc) allocator for collectable objects, >> and compiler support for a collector that can scan all >> objects for pointers to collectable objects. If new(gc) >> is never called there need be no overhead. > >Creating an efficient GC system is tricky, yes, but I don't see why a smart pointer >approach can't be just as efficient as a compiler solution? It probably can be, but the literature so far indicates that it isn't. A collector that has compiler support and knows all about how the stack and heap are laid out and can take advantage of the virtual memory hardware and so on has a big advantage. It's also nice to be able to use raw pointers to collected objects. Still, a portable smart pointer GC would be nice to have, as it will take years of work to see GC added to C++, if it ever happens at all. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
"Peter Dimov" <[EMAIL PROTECTED]> writes: > It's true that, in general, there is no safe way to break the cycle; x1 may > keep a raw pointer to x2, or it might be a X invariant that X::p is > non-empty, causing ~X to fail. This is why the final decision to break the > cycles should be left to the user, and the collector should not > automatically reclaim memory. Still, most reasonable classes would be > collect-friendly. Isn't the biggest problem one of system design? How does the user write the cycle-breaking code which does different things based on the dynamic type of the objects being referenced? -- David Abrahams [EMAIL PROTECTED] * http://www.boost-consulting.com Boost support, enhancements, training, and commercial distribution ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: Re: [boost] Shared_ptr "mini garbage collector"
From: "William E. Kempf" <[EMAIL PROTECTED]>
> I don't follow this. How does the user prevent the destructors from
referencing the other
> object(s) participating in the cycle which may no longer exist? The only
safe way to break
> the cycle is to have intimate knowledge about the objects participating in
the cycle and do
> what ever clean up is required in a determistic manner *before* the
object's are destroyed
> and the memory is freed.
(please use line wrapping)
Consider the original example:
struct X
{
boost::shared_ptr p;
};
int main()
{
boost::shared_ptr p1(new X);
boost::shared_ptr p2(new X);
p1->p = p2;
p2->p = p1;
p1.reset();
p2.reset();
break_cycles();
}
Here is what break_cycles would do:
1. Find the two X objects (let's call them x1 and x2) on the heap, and scan
them for shared_ptr instances, finding x1.p and x2.p; determine that x1 and
x2 are unreachable.
2. Create a temporary vector< shared_ptr > v and copy x1.p and x2.p
into it.
3. Reset x1.p and x2.p.
4. Clear v. This will cause x1 and x2 to be destroyed.
It's true that, in general, there is no safe way to break the cycle; x1 may
keep a raw pointer to x2, or it might be a X invariant that X::p is
non-empty, causing ~X to fail. This is why the final decision to break the
cycles should be left to the user, and the collector should not
automatically reclaim memory. Still, most reasonable classes would be
collect-friendly.
___
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
From: "Greg Colvin" <[EMAIL PROTECTED]> > My old cyclic_ptr code is still somewhere on the Boost pages, > and might offer a better solution to these problems. Indeed. After having reinvented that wheel, I am now (finally) able to understand cyclic_ptr. ;-) ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: Re: [boost] Shared_ptr "mini garbage collector"
> From: "Peter Dimov" <[EMAIL PROTECTED]> > From: "William E. Kempf" <[EMAIL PROTECTED]> > > > No, the user would not be expected to do any bookkeeping. He would only > need > > > to call find_unreachable_objects() that would return a list of the > > > unreachable objects, and then, optionally, call break_cycles() with that > > > list as an argument. Or something like that. :-) > > > > And how would break_cycles() accomplish its task with out book keeping? > > The information that is needed to break the cycles (a list of unreachable > shared_ptr instances) is generated by find_unreachable_objects for free, > since to determine object reachability, objects are scanned for shared_ptr > subobjects. When those shared_ptrs are reset() by break_cycles(), all > unreachable objects will be freed, their destructors will run, and any > weak_ptrs to those objects will correctly expire. I don't follow this. How does the user prevent the destructors from referencing the other object(s) participating in the cycle which may no longer exist? The only safe way to break the cycle is to have intimate knowledge about the objects participating in the cycle and do what ever clean up is required in a determistic manner *before* the object's are destroyed and the memory is freed. William E. Kempf [EMAIL PROTECTED] ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: Re: [boost] Shared_ptr "mini garbage collector"
> From: Greg Colvin <[EMAIL PROTECTED]> > At 09:23 AM 1/7/2003, Peter Dimov wrote: > >From: "William E. Kempf" <[EMAIL PROTECTED]> > >> > >> I think that extending it to free memory in cycles would be a great idea. > >Of course, this opens a large can of worms about how to handle destruction > >of objects which refer to each other...< > > > >One possible approach is to return a list of references to the "offending" > >shared_ptr instances to the user, who can then reset() them as appropriate. > >Actually it's not as simple as that since a reset() can invalidate some of > >the returned references; the shared_ptr instances would first need to be > >copied to a temporary container, the originals reset(), and the temporary > >container destroyed, but the general idea is the same. > > Finalization semantics is of course a very big can of worms > that has kept a lot of GC experts arguing for years. But I > take the success of Java as evidence that getting it right > might not be all that important. The "Java solution" is to not have a solution. Finalizers need never be called in Java. I'd prefer to always call the destructors, with the knowledge that dereferencing a GC pointer that's participating in a cycle during the destructor results in undefined behavior. I can usually avoid doing this. > >> I think that full GC is one of the major things missing from the C++ > >language, and the appeal of a smart pointer approach, where I pay for GC > >only when I want/need it, is a great idea.< > > A smart pointer approach is the only way I know to write a > portable collector, but it is not really the best way to > write a high-performance collector. My preference is to > have a special new(gc) allocator for collectable objects, > and compiler support for a collector that can scan all > objects for pointers to collectable objects. If new(gc) > is never called there need be no overhead. Creating an efficient GC system is tricky, yes, but I don't see why a smart pointer approach can't be just as efficient as a compiler solution? William E. Kempf [EMAIL PROTECTED] ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: Re: [boost] Shared_ptr "mini garbage collector"
From: "William E. Kempf" <[EMAIL PROTECTED]> > > No, the user would not be expected to do any bookkeeping. He would only need > > to call find_unreachable_objects() that would return a list of the > > unreachable objects, and then, optionally, call break_cycles() with that > > list as an argument. Or something like that. :-) > > And how would break_cycles() accomplish its task with out book keeping? The information that is needed to break the cycles (a list of unreachable shared_ptr instances) is generated by find_unreachable_objects for free, since to determine object reachability, objects are scanned for shared_ptr subobjects. When those shared_ptrs are reset() by break_cycles(), all unreachable objects will be freed, their destructors will run, and any weak_ptrs to those objects will correctly expire. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: Re: [boost] Shared_ptr "mini garbage collector"
> From: "Peter Dimov" <[EMAIL PROTECTED]> > From: "William E. Kempf" <[EMAIL PROTECTED]> > > > From: "Peter Dimov" <[EMAIL PROTECTED]> > > > From: "William E. Kempf" <[EMAIL PROTECTED]> > > > > I think that extending it to free memory in cycles would be a great > idea. > > > Of course, this opens a large can of worms about how to handle > destruction > > > of objects which refer to each other...< > > > > > > One possible approach is to return a list of references to the > "offending" > > > shared_ptr instances to the user, who can then reset() them as > appropriate. > > > Actually it's not as simple as that since a reset() can invalidate some > of > > > the returned references; the shared_ptr instances would first need to be > > > copied to a temporary container, the originals reset(), and the > temporary > > > container destroyed, but the general idea is the same. > > > > This just pushes the issue off on the end user... who may not be any more > capable of dealing with the problem either. If he can't do a lot of book > keeping to handle the circular problem, then pushing it off on him is not > much help. And if he can do the book keeping, there's probably a solution > he can code into the destructors themselves.< > > No, the user would not be expected to do any bookkeeping. He would only need > to call find_unreachable_objects() that would return a list of the > unreachable objects, and then, optionally, call break_cycles() with that > list as an argument. Or something like that. :-) And how would break_cycles() accomplish its task with out book keeping? William E. Kempf [EMAIL PROTECTED] ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
At 09:23 AM 1/7/2003, Peter Dimov wrote: >From: "William E. Kempf" <[EMAIL PROTECTED]> >> >> I think that extending it to free memory in cycles would be a great idea. >Of course, this opens a large can of worms about how to handle destruction >of objects which refer to each other...< > >One possible approach is to return a list of references to the "offending" >shared_ptr instances to the user, who can then reset() them as appropriate. >Actually it's not as simple as that since a reset() can invalidate some of >the returned references; the shared_ptr instances would first need to be >copied to a temporary container, the originals reset(), and the temporary >container destroyed, but the general idea is the same. Finalization semantics is of course a very big can of worms that has kept a lot of GC experts arguing for years. But I take the success of Java as evidence that getting it right might not be all that important. >> I think that full GC is one of the major things missing from the C++ >language, and the appeal of a smart pointer approach, where I pay for GC >only when I want/need it, is a great idea.< A smart pointer approach is the only way I know to write a portable collector, but it is not really the best way to write a high-performance collector. My preference is to have a special new(gc) allocator for collectable objects, and compiler support for a collector that can scan all objects for pointers to collectable objects. If new(gc) is never called there need be no overhead. >Making a real "zero overhead" collector is a bit harder, and I'm not sure I >have the time to do it. > >The main requirement is the ability to discover all active counted_base >objects; currently I maintain a global std::map of their addresses, and >that's probably not acceptable for production code. A dedicated allocator >that provides the ability to enumerate allocations may help here. > >An additional requirement is to be able to discover shared_ptr subobjects >and to distinguish a shared_ptr from a weak_ptr; I've used a "magic >constant" but this increases sizeof(shared/weak_ptr) from 8 to 12 on a >typical implementation. It is possible to "mangle" the object pointer (by >XOR-ing it, for example) in weak_ptr and replace the magic constant test >with a valid pointer test, but I'm not sure whether this is a good idea. :-) My old cyclic_ptr code is still somewhere on the Boost pages, and might offer a better solution to these problems. But I just haven't had time or motivation to integrate it with shared_ptr. ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: Re: [boost] Shared_ptr "mini garbage collector"
> From: David Abrahams <[EMAIL PROTECTED]> > "William E. Kempf" <[EMAIL PROTECTED]> writes: > > From: "Peter Dimov" <[EMAIL PROTECTED]> > >> One possible approach is to return a list of references to the > >> "offending" shared_ptr instances to the user, who can then reset() > >> them as appropriate. Actually it's not as simple as that since a > >> reset() can invalidate some of the returned references; the > >> shared_ptr instances would first need to be copied to a temporary > >> container, the originals reset(), and the temporary container > >> destroyed, but the general idea is the same. > > > > This just pushes the issue off on the end user... who may not be any > > more capable of dealing with the problem either. If he can't do a lot > > of book keeping to handle the circular problem, then pushing it off on > > him is not much help. And if he can do the book keeping, there's > > probably a solution he can code into the destructors themselves. > > What Python does is to collect only the memory from cycles, without > calling __del__ (the equivalent of a destructor). It also provides a > similar function which gets you a list of the objects that are in > cycles. A solution like this for C++ could easily result in memory leaks. If the object in question did it's own internal memory allocations which would normally be cleaned up in the destructor, you've got a leak when the "collector" releases the object's memory with out calling its destructor. William E. Kempf [EMAIL PROTECTED] ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: Re: [boost] Shared_ptr "mini garbage collector"
From: "William E. Kempf" <[EMAIL PROTECTED]> > > From: "Peter Dimov" <[EMAIL PROTECTED]> > > From: "William E. Kempf" <[EMAIL PROTECTED]> > > > I think that extending it to free memory in cycles would be a great idea. > > Of course, this opens a large can of worms about how to handle destruction > > of objects which refer to each other...< > > > > One possible approach is to return a list of references to the "offending" > > shared_ptr instances to the user, who can then reset() them as appropriate. > > Actually it's not as simple as that since a reset() can invalidate some of > > the returned references; the shared_ptr instances would first need to be > > copied to a temporary container, the originals reset(), and the temporary > > container destroyed, but the general idea is the same. > > This just pushes the issue off on the end user... who may not be any more capable of dealing with the problem either. If he can't do a lot of book keeping to handle the circular problem, then pushing it off on him is not much help. And if he can do the book keeping, there's probably a solution he can code into the destructors themselves.< No, the user would not be expected to do any bookkeeping. He would only need to call find_unreachable_objects() that would return a list of the unreachable objects, and then, optionally, call break_cycles() with that list as an argument. Or something like that. :-) ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
From: "David Abrahams" <[EMAIL PROTECTED]> > "Peter Dimov" <[EMAIL PROTECTED]> writes: > > > I've added a simple mark and sweep "garbage collector" to > > libs/smart_ptr/sp_debug_hooks.cpp > > Where's the code? I don't see it. In libs/smart_ptr/sp_debug_hooks.cpp? ;-) http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/boost/boost/libs/smart_ptr/sp _debug_hooks.cpp.diff?r1=1.1&r2=1.2 ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
"William E. Kempf" <[EMAIL PROTECTED]> writes: > From: "Peter Dimov" <[EMAIL PROTECTED]> >> One possible approach is to return a list of references to the >> "offending" shared_ptr instances to the user, who can then reset() >> them as appropriate. Actually it's not as simple as that since a >> reset() can invalidate some of the returned references; the >> shared_ptr instances would first need to be copied to a temporary >> container, the originals reset(), and the temporary container >> destroyed, but the general idea is the same. > > This just pushes the issue off on the end user... who may not be any > more capable of dealing with the problem either. If he can't do a lot > of book keeping to handle the circular problem, then pushing it off on > him is not much help. And if he can do the book keeping, there's > probably a solution he can code into the destructors themselves. What Python does is to collect only the memory from cycles, without calling __del__ (the equivalent of a destructor). It also provides a similar function which gets you a list of the objects that are in cycles. I know that re-using memory which contains an object without a trivial destructor is technically undefined behavior, but it's hard to imagine an implementation where it would be a problem. This would still "simulate infinite memory", though if you were comparing memory addresses you might notice some repetition ;-). I don't know if an approach like this is possible for shared_ptr. -- David Abrahams [EMAIL PROTECTED] * http://www.boost-consulting.com Boost support, enhancements, training, and commercial distribution ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: Re: [boost] Shared_ptr "mini garbage collector"
> From: "Peter Dimov" <[EMAIL PROTECTED]> > From: "William E. Kempf" <[EMAIL PROTECTED]> > > I think that extending it to free memory in cycles would be a great idea. > Of course, this opens a large can of worms about how to handle destruction > of objects which refer to each other...< > > One possible approach is to return a list of references to the "offending" > shared_ptr instances to the user, who can then reset() them as appropriate. > Actually it's not as simple as that since a reset() can invalidate some of > the returned references; the shared_ptr instances would first need to be > copied to a temporary container, the originals reset(), and the temporary > container destroyed, but the general idea is the same. This just pushes the issue off on the end user... who may not be any more capable of dealing with the problem either. If he can't do a lot of book keeping to handle the circular problem, then pushing it off on him is not much help. And if he can do the book keeping, there's probably a solution he can code into the destructors themselves. I don't know what the real answer is (if there is one), but personally I can live with this case simply being undefined behavior, since it can often (usually?) be avoided in the first place. > > I think that full GC is one of the major things missing from the C++ > language, and the appeal of a smart pointer approach, where I pay for GC > only when I want/need it, is a great idea.< > > Making a real "zero overhead" collector is a bit harder, and I'm not sure I > have the time to do it. Yep. I thought you were volunteering, though, from your post and question ;). > An additional requirement is to be able to discover shared_ptr subobjects > and to distinguish a shared_ptr from a weak_ptr; I've used a "magic > constant" but this increases sizeof(shared/weak_ptr) from 8 to 12 on a > typical implementation. It is possible to "mangle" the object pointer (by > XOR-ing it, for example) in weak_ptr and replace the magic constant test > with a valid pointer test, but I'm not sure whether this is a good idea. :-) Yep... a GC smart pointer is a non-trivial task. It would probably be best to make it a seperate smart pointer, so as not to impact usage of the ref-counted shared_ptr. I know that this topic has been brought up numerous times, but I do think it would be very beneficial for someone to submit a quality GC smart pointer to Boost. William E. Kempf [EMAIL PROTECTED] ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
"Peter Dimov" <[EMAIL PROTECTED]> writes: > I've added a simple mark and sweep "garbage collector" to > libs/smart_ptr/sp_debug_hooks.cpp Where's the code? I don't see it. -- David Abrahams [EMAIL PROTECTED] * http://www.boost-consulting.com Boost support, enhancements, training, and commercial distribution ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
From: "William E. Kempf" <[EMAIL PROTECTED]> > > I think that extending it to free memory in cycles would be a great idea. Of course, this opens a large can of worms about how to handle destruction of objects which refer to each other...< One possible approach is to return a list of references to the "offending" shared_ptr instances to the user, who can then reset() them as appropriate. Actually it's not as simple as that since a reset() can invalidate some of the returned references; the shared_ptr instances would first need to be copied to a temporary container, the originals reset(), and the temporary container destroyed, but the general idea is the same. > I think that full GC is one of the major things missing from the C++ language, and the appeal of a smart pointer approach, where I pay for GC only when I want/need it, is a great idea.< Making a real "zero overhead" collector is a bit harder, and I'm not sure I have the time to do it. The main requirement is the ability to discover all active counted_base objects; currently I maintain a global std::map of their addresses, and that's probably not acceptable for production code. A dedicated allocator that provides the ability to enumerate allocations may help here. An additional requirement is to be able to discover shared_ptr subobjects and to distinguish a shared_ptr from a weak_ptr; I've used a "magic constant" but this increases sizeof(shared/weak_ptr) from 8 to 12 on a typical implementation. It is possible to "mangle" the object pointer (by XOR-ing it, for example) in weak_ptr and replace the magic constant test with a valid pointer test, but I'm not sure whether this is a good idea. :-) ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Re: [boost] Shared_ptr "mini garbage collector"
> From: "Peter Dimov" <[EMAIL PROTECTED]> > > I've added a simple mark and sweep "garbage collector" to > libs/smart_ptr/sp_debug_hooks.cpp that is able to detect unreachable objects > kept alive by shared_ptr cycles. At the moment it's more a debugging aid, > and doesn't attempt to free memory, athough it is possible to extend it to > do so. This is mainly a research project; if you think that it might have a > practical use let me know. :-) I think that extending it to free memory in cycles would be a great idea. Of course, this opens a large can of worms about how to handle destruction of objects which refer to each other... I think that full GC is one of the major things missing from the C++ language, and the appeal of a smart pointer approach, where I pay for GC only when I want/need it, is a great idea. William E. Kempf [EMAIL PROTECTED] ___ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
