reset_and_collect root determination and sp_collect similarity
Hi Peter, The code here: http://lists.boost.org/boost-users/2005/05/11805.php appears to require the user to specify the root pointers in order to do a complete collection. This is in contrast to sp_collect.cpp which used Christopher's method [chri84] cited here: http://www.cs.kent.ac.uk/people/staff/rej/gcbib/gcbibC.html to find the roots, at least AFAICT. Is this intentional, or is the above code in 11805.php simply a sketch of a method which will eventually use something like Christopher's. I ask because some of the code in 11806.php appears similar to some in sp_collect.cpp. For example, I'm guessing that the map2_type in sp_collect corresponds to the map_type in reset_and_collect, i.e. the key is sorted on the referent, and the value is the number of smart_ptr's to that referent that are on the heap. Thanks for any clarification. -regards, Larry
Larry Evans wrote:
Hi Peter,
The code here:
http://lists.boost.org/boost-users/2005/05/11805.php
appears to require the user to specify the root pointers in order to do a complete collection. This is in contrast to sp_collect.cpp which used Christopher's method [chri84] cited here:
http://www.cs.kent.ac.uk/people/staff/rej/gcbib/gcbibC.html
to find the roots, at least AFAICT. Is this intentional, ...
Yes, this is intentional, as reset_and_collect does not require any help from the implementation of shared_ptr, so it can be used with tr1::shared_ptr as well. It has been developed in response to Eric Niebler's scenario where the roots that form cycles are known to the programmer. (He ended up not using it, though :-) ) It's possible to combine the two approaches and perhaps provide a default enable_tracking that does a memory scan as in sp_collector. I think that in most typical cyclic shared_ptr situations the problematic roots are known in advance, though, so a reset_and_collect-type solution may be enough. Note that reset_and_collect is perfectly capable of figuring out on its own that unknown roots to a node exist, it only needs a starting point (and can be modified to work with several starting points).
On 06/16/2005 06:38 AM, Peter Dimov wrote:
Larry Evans wrote: [snip]
to find the roots, at least AFAICT. Is this intentional, ...
Yes, this is intentional, as reset_and_collect does not require any help from the implementation of shared_ptr, so it can be used with tr1::shared_ptr as well. It has been developed in response to Eric Niebler's scenario where the roots that form cycles are known to the programmer.
Ah! My mind's fog is lifting slightly ;) [snip]
It's possible to combine the two approaches and perhaps provide a default enable_tracking that does a memory scan as in sp_collector. I think that in
I would be nice if somehow the method for finding a referent's contained smart_ptr's could be a determined by a policy.
most typical cyclic shared_ptr situations the problematic roots are known in advance, though, so a reset_and_collect-type solution may be enough.
Hadn't thought of that.
Note that reset_and_collect is perfectly capable of figuring out on its own that unknown roots to a node exist, it only needs a starting point (and can be modified to work with several starting points).
Hmm... is this anything like the 'local mark scan' in [mart90] cited on Jones page? Give a node, call it the subroot node, it traverses nodes reachable from that while decrementing the refcounts. If the subroot node still has a positve refcount, it can't be in a cycle; so, it undoes the decrementing. I'm guessing that the difference is that: 1) reset_and_collect doesn't decrement, it only increments the value associated with the node's key in a map_type. 2) instead of user selection of the staring point, the selection is made each time a decrement is made, and the starting point is the smart_ptr making the decrement. The modification to several starting points sounds like it may be a variation of the method in [lins90a], where a decrement doesn't immediately scan the subnodes, but waits until a que of decremented smart_ptr's is filled, and then scan's nodes reachable from each element in the que. Is that, at least approximately, what's happening in reset_and_collect?
Larry Evans wrote:
Hmm... is this anything like the 'local mark scan' in [mart90] cited on Jones page? Give a node, call it the subroot node, it traverses nodes reachable from that while decrementing the refcounts. If the subroot node still has a positve refcount, it can't be in a cycle; so, it undoes the decrementing. I'm guessing that the difference is that:
1) reset_and_collect doesn't decrement, it only increments the value associated with the node's key in a map_type.
2) instead of user selection of the staring point, the selection is made each time a decrement is made, and the starting point is the smart_ptr making the decrement.
Yes, this is pretty much what reset_and_collect does.
The modification to several starting points sounds like it may be a variation of the method in [lins90a], where a decrement doesn't immediately scan the subnodes, but waits until a que of decremented smart_ptr's is filled, and then scan's nodes reachable from each element in the que.
Exactly. In this variation, 'reset_and_collect' would just record a weak_ptr obtained from the shared_ptr being reset in a queue; then a separate function would mark starting from the weak_ptr queue and collect the unreachable nodes. It's also possible to allow the user to specify the weak pointers explicitly, if they are already being kept somewhere.
On 06/16/2005 06:38 AM, Peter Dimov wrote: [snip]
tr1::shared_ptr as well. It has been developed in response to Eric Niebler's scenario where the roots that form cycles are known to the programmer. (He ended up not using it, though :-) )
It's possible to combine the two approaches and perhaps provide a default enable_tracking that does a memory scan as in sp_collector. I think that in most typical cyclic shared_ptr situations the problematic roots are known in advance, though, so a reset_and_collect-type solution may be enough.
But if the problematic roots are known in advance, why doesn't the programmer simply use weak_ptr's to them? I guess it's because the programmer doesn't know he's connecting to a problematic root, although he knows what they are. I guess he doesn't want to store the identity of the problematic roots in some global data structure and check each time he makes a connection. Eric, is that about right?
On 06/16/2005 07:48 AM, Larry Evans wrote: [snip]
But if the problematic roots are known in advance, why doesn't the programmer simply use weak_ptr's to them? I guess it's because the programmer doesn't know he's connecting to a problematic root, although he knows what they are. I guess he doesn't want to store the identity of the problematic roots in some global data structure and check each time he makes a connection. Eric, is that about right?
OOPS. I jumped to the conclusion the "problematic root" must be the target of a "cycle closing smart pointer" instead of all "cycle closing smart pointers" were reachable from one or more of the "problematic roots". I hope that describes Eric's situation.
Larry Evans wrote:
But if the problematic roots are known in advance, why doesn't the programmer simply use weak_ptr's to them? I guess it's because the programmer doesn't know he's connecting to a problematic root, although he knows what they are.
The general scenario is that you have a class X that contains a shared_ptr<Y>, where the Y's can also contain shared_ptr<Y>s to each other, but the user never sees an Y directly. You know that all your roots are in the instances of X, but you can't use weak_ptr to link the Y's because this won't keep a cyclic structure alive until the last X to it is gone. However you can reset_and_collect the shared_ptr<Y> in ~X. (The problem that prevented Eric from using it is that reset_and_collect may throw.) Alternatively, you can also keep a {vector, set}< weak_ptr<Y> > global root structure, add to it in X::X and scan and prune it periodically.
participants (2)
-
Larry Evans -
Peter Dimov