Re: [Boost-users] boost::weak_ptr and boost::intrusive_ptr
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Sebastian Redl Sent: Friday, December 01, 2006 1:23 PM To: boost-users@lists.boost.org Subject: Re: [Boost-users] boost::weak_ptr and boost::intrusive_ptr
The use case here is this:
NodePtr base = make_tree(); NodePtr child = base.get("path/to/child"); base.reset(); Now, unless the parent knows that it owns the child and notifies it, the parent pointer of child is dangling. A weak pointer can detect this situation.
[Nat] Okay.
The reason I see for there being no weak_intrusive_ptr is that it is quite simply impossible to implement while staying intrusive. Let's remember what a weak pointer does: after the death of the object it points to, it knows that it is now invalid. There being no notification of pointers when other pointers get destructed, there's only one way to do this: to keep the refcount for the object alive, so that the weak pointer can check it. But if the refcount is part of the object, as is the case for intrusive_ptr, it's impossible to keep the refcount alive while destroying the object.
In other words, the appeal of intrusive_ptr is that it doesn't require any resources outside the object it points to. However, this restriction makes it impossible to implement an efficient weak pointer.
[Nat] Not to be argumentative, but... It seems possible to implement weak_ptr notification by building a list of weak_ptr instances referencing a given object. If we don't want that list to consume additional heap memory, the list could itself be intrusive in the weak_ptr objects. If we want it to be efficient, we build a doubly-linked list. (This may call for a policy-based implementation so the consumer can decide which overhead is least noxious.)
Just a small question: Isn't it so, that linked lists (double or single), can be spreaded in the memory, so that cache misses and page faults are subject to happen? I think deque is a better choice (which can be better optimized in terms of locality)... With Kind Regards, Ovanes Markarian On Fri, December 1, 2006 20:13, Nat Goodspeed wrote:
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Sebastian Redl Sent: Friday, December 01, 2006 1:23 PM To: boost-users@lists.boost.org Subject: Re: [Boost-users] boost::weak_ptr and boost::intrusive_ptr
The use case here is this:
NodePtr base = make_tree(); NodePtr child = base.get("path/to/child"); base.reset(); Now, unless the parent knows that it owns the child and notifies it, the parent pointer of child is dangling. A weak pointer can detect this situation.
[Nat] Okay.
The reason I see for there being no weak_intrusive_ptr is that it is quite simply impossible to implement while staying intrusive. Let's remember what a weak pointer does: after the death of the object it points to, it knows that it is now invalid. There being no notification of pointers when other pointers get destructed, there's only one way to do this: to keep the refcount for the object alive, so that the weak pointer can check it. But if the refcount is part of the object, as is the case for intrusive_ptr, it's impossible to keep the refcount alive while destroying the object.
In other words, the appeal of intrusive_ptr is that it doesn't require any resources outside the object it points to. However, this restriction makes it impossible to implement an efficient weak pointer.
[Nat] Not to be argumentative, but...
It seems possible to implement weak_ptr notification by building a list of weak_ptr instances referencing a given object. If we don't want that list to consume additional heap memory, the list could itself be intrusive in the weak_ptr objects. If we want it to be efficient, we build a doubly-linked list. (This may call for a policy-based implementation so the consumer can decide which overhead is least noxious.) _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On 12/1/06, Nat Goodspeed <ngoodspeed@solidworks.com> wrote:
It seems possible to implement weak_ptr notification by building a list of weak_ptr instances referencing a given object. If we don't want that list to consume additional heap memory, the list could itself be intrusive in the weak_ptr objects. If we want it to be efficient, we build a doubly-linked list. (This may call for a policy-based implementation so the consumer can decide which overhead is least noxious.)
Interestingly, since you define the intrusive_ptr_add_ref and release, you can probably implement the list management without changing intrusive_ptr. Would you prefer to have the list of weak_ptrs kept on the intrusive_ptr (on the actual 'intruded' object, actually), or have a global map of intrusive_ptr object to weak_ptr list? ie void intrusive_ptr_release(MyPointer *p) { decr_refcount(p); if (refcount(p) == 0) { weak_ptr_list weaklist = ??? // where does the list come from? from p? global? for_each_weak_ptr_notify_object_gone(weaklist); delete p; } } Tony
Nat Goodspeed wrote:
[Nat] Not to be argumentative, but...
It seems possible to implement weak_ptr notification by building a list of weak_ptr instances referencing a given object. If we don't want that list to consume additional heap memory, the list could itself be intrusive in the weak_ptr objects. If we want it to be efficient, we build a doubly-linked list. (This may call for a policy-based implementation so the consumer can decide which overhead is least noxious.) So basically, within the referenced object, you have a pointer to the first weak pointer, which holds a pointer to the next weak pointer, and so on, linked in both directions?
Interesting idea. I can't find any problems with it. template<class Pointee, class Access = weak_member_access<Pointee, &Pointee::weak_head> > class intrusive_weak_ptr { intrusive_weak_ptr *prev, *next; Pointee *ptr; public: typedef intrusive_ptr<Pointee, ...> strong_ptr; intrusive_weak_ptr(const strong_ptr &o) : prev(0), ptr(o.get()) { intrusive_weak_ptr * head = Access::get_head(*o); head->prev = this; next = head; Access::set_head(*o, this); } strong_ptr lock() { if(!ptr) { throw lock_error(); } return strong_ptr(ptr); } void signal_destruction() { ptr = 0; if(next) { next->signal_destruction(); } next = 0; prev = 0; } }; With the destructor of intrusive_ptr starting the signal_destruction chain, of course. Some TMP would be required to make intrusive_ptr only require weak_ptr if it's actually used. intrusive_list could be used to make the weak_ptr list more robust. Sebastian
Nat Goodspeed wrote:
It seems possible to implement weak_ptr notification by building a list of weak_ptr instances referencing a given object. If we don't want that list to consume additional heap memory, the list could itself be intrusive in the weak_ptr objects. If we want it to be efficient, we build a doubly-linked list. (This may call for a policy-based implementation so the consumer can decide which overhead is least noxious.)
This works. It's also completely independent of intrusive_ptr. You can implement such a weak pointer (and I know people who have done so) without ever using an intrusive_ptr or reference counting at all. The object destructor just goes over the list and zeroes the weak pointers. Threads are problematic and would probably require a per-object mutex. Another option is to use http://boost.org/libs/smart_ptr/sp_techniques.html#weak_without_shared which also doesn't require intrusive_ptr and works for any object, and handles threads nicely. But you pay for a shared_ptr control block, so it probably won't satisfy intrusive_ptr users. Both options are intrusive, but then, so is intrusive_ptr. :-)
On Friday 01 December 2006 16:15, Peter Dimov wrote:
Nat Goodspeed wrote:
It seems possible to implement weak_ptr notification by building a list of weak_ptr instances referencing a given object. If we don't want that list to consume additional heap memory, the list could itself be intrusive in the weak_ptr objects. If we want it to be efficient, we build a doubly-linked list. (This may call for a policy-based implementation so the consumer can decide which overhead is least noxious.)
This works. It's also completely independent of intrusive_ptr. You can implement such a weak pointer (and I know people who have done so) without ever using an intrusive_ptr or reference counting at all. The object destructor just goes over the list and zeroes the weak pointers. Threads are problematic and would probably require a per-object mutex.
Another option is to use
http://boost.org/libs/smart_ptr/sp_techniques.html#weak_without_shared
which also doesn't require intrusive_ptr and works for any object, and handles threads nicely. But you pay for a shared_ptr control block, so it probably won't satisfy intrusive_ptr users.
Both options are intrusive, but then, so is intrusive_ptr. :-)
My motivation for wanting the intrusive pointer is really design simplicity. For a tree I ran into problems trying share the pointer from within the pointee. enable_shared_from_this didn't work in all cases, and could get downright confusing, even when it did work. It also obviates one of the primary arguments from not using an intrusive pointer. If I use it, I already have to open up the pointee to modification. The reason I want the weak pointer is simply to prevent access to an invalid pointer. If I had an easy to use pair of intrusive/weak pointers, then I would just used them and not have to think about the details.
participants (2)
-
Gottlob Frege -
Nat Goodspeed -
Ovanes Markarian -
Peter Dimov -
Sebastian Redl -
Steven T. Hatton