C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Lock Free Programming with Boost::shared_ptr instead of Haza Goto page 1, 2, 3 ... 10, 11, 12  Next          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Roshan Naik Guest Posted: Sat Mar 19, 2005 10:47 am    Post subject: Lock Free Programming with Boost::shared_ptr instead of Haza After attending Andrei's talk at SDWest yesterday on Lock Free Prog (a pretty good talk by the way), it left me wondering... Do we really need the whole hazard pointer lists based pseudo garbage collection ? The talk seemed to suggest that the purpose of the technique was to collect/free unused pointers. So why can't boost::shared_ptr be put to task here ? I tried to think of a few reasons... but they didnt seem good enough... 1) One might say that shared_ptr does not solve the problem of cyclic references. But i think the same problem exists anyway with raw pointers used with in the Hazard pointers technique too. 2) Shared_ptr is not thread safe ?? I dont know. But it is possible that it is currently not implemented to perform its operations in an atomic/thread-safe fashion. But perhaps that can be fixed (with help from the future standard..volatile/CAS). But ofcourse, hazard pointers technique also relies on the similar requirements from the standard. 3) Andrei felt that boost::shared_ptr _may_ be using locks. I doubt it however. -Roshan [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Joe Seigh Guest Posted: Sun Mar 20, 2005 1:51 am    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of On 19 Mar 2005 05:47:23 -0500, Roshan Naik <roshan_naik (AT) yahoo (DOT) com> wrote: Quote: After attending Andrei's talk at SDWest yesterday on Lock Free Prog (a pretty good talk by the way), it left me wondering... Do we really need the whole hazard pointer lists based pseudo garbage collection ? The talk seemed to suggest that the purpose of the technique was to collect/free unused pointers. So why can't boost::shared_ptr be put to task here ? I tried to think of a few reasons... but they didnt seem good enough... 1) One might say that shared_ptr does not solve the problem of cyclic references. But i think the same problem exists anyway with raw pointers used with in the Hazard pointers technique too. The cyclic references problem for reference counting is a bit overstated. When was the last time you actually ran into that problem? You either have to be doing heavy graph theoritical programming or deliberately not coding explicit dtors in collection classes. Hazard pointers aren't shared, so you don't see them as part of a data structure. Any cyclic reference problems have to be solved by conventional means. Quote: 2) Shared_ptr is not thread safe ?? I dont know. But it is possible that it is currently not implemented to perform its operations in an atomic/thread-safe fashion. But perhaps that can be fixed (with help from the future standard..volatile/CAS). But ofcourse, hazard pointers technique also relies on the similar requirements from the standard. I believe there's a parameter to make it mostly threadsafe. The non thread-safe part is you have to know the refcount of any shared_ptr's you copy won't go to zero during the copy operation. Basically, you have to "own" the shared_ptr you're copying. I did an experimental atomically thread-safe refcounted ptr which can be found at http://atomic-ptr-plus.sourceforge.net/ . It's "not C++ as we know it, Jim", but just C++ being used for pointer abstraction which you can't do in C. I'm not a C++ programmer. The project is on hold until processors get multi-cored enough that lock-free gets taken more seriously. Assuming that all the useful applications of lock-free aren't locked up in patents by then. Anything involving lock-free is considered novel by the patent office. I was going to do a write up on how to do reader lock-free implementations of any data structure, not just linked lists or simple objects, provided certain conditions are met, until I realized it would be instructions for creating lock-free applications to patent. Quote: 3) Andrei felt that boost::shared_ptr _may_ be using locks. I doubt it however. It's possible. Thread-safe isn't the same as lock-free. It's not a problem unless you need lock-free or async safety. Getting back to the hazard pointers vs. refcounting issue. I recently ported atomic_ptr to powerpc and ran the testcase I had which also tested an implmentation of RCU. The testcase has reader threads traversing a linked list while writer threads update the list. With thread scheduling on Mac OS X changed to SCHED_RR and certain preemption settings, while the mutex version ran about 900 reads or writes per second per thread, the RCU version ran about 100000 reads per second per thread and about 300+ writes per second per thread. Even considering scheduling artifacts from running on a single cpu, that's still pretty impressive. The atomic_ptr version only did about 25000 reads per second per thread. -- Joe Seigh [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Alexander Terekhov Guest Posted: Sun Mar 20, 2005 2:00 am    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of Roshan Naik wrote: [...] Quote: 3) Andrei felt that boost::shared_ptr _may_ be using locks. I doubt it however. Boost::shared_ptr can be implemented without locks. But it provides basic thread-safety, not strong. Hazard pointers stuff is about lockless strong thread-safety, not basic. Another difference is that hazard pointers stuff needs hazardously expensive store-load barrier (not cheap even on IA32). regards, alexander. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Andrei Alexandrescu (See Guest Posted: Sun Mar 20, 2005 2:00 am    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of Roshan Naik wrote: Quote: After attending Andrei's talk at SDWest yesterday on Lock Free Prog (a pretty good talk by the way), it left me wondering... Do we really need the whole hazard pointer lists based pseudo garbage collection ? The talk seemed to suggest that the purpose of the technique was to collect/free unused pointers. So why can't boost::shared_ptr be put to task here ? I tried to think of a few reasons... but they didnt seem good enough... 1) One might say that shared_ptr does not solve the problem of cyclic references. But i think the same problem exists anyway with raw pointers used with in the Hazard pointers technique too. 2) Shared_ptr is not thread safe ?? I dont know. But it is possible that it is currently not implemented to perform its operations in an atomic/thread-safe fashion. But perhaps that can be fixed (with help from the future standard..volatile/CAS). But ofcourse, hazard pointers technique also relies on the similar requirements from the standard. 3) Andrei felt that boost::shared_ptr _may_ be using locks. I doubt it however. 4 and definitive) You can't CAS an entire smart pointer object. On systems that support CAS2 (not all!), you can CAS two adjacent words (a pointer and a pointer to the reference count next to it) but, as the CUJ Oct/Dec articles by Maged Michael and myself explain, that leaves only the reading lock-free, while the writing is locked by the readers. By the way, the sheer thought that boost::shared_ptr uses interlocked operations whether you need that or not, makes me feel uncomfortable performance-wise. Andrei [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jeremy J Guest Posted: Sun Mar 20, 2005 2:02 am    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of Quote: 3) Andrei felt that boost::shared_ptr _may_ be using locks. I doubt it however. From boost/detail/shared_count.hpp void add_ref_copy() { #if defined(BOOST_HAS_THREADS) mutex_type::scoped_lock lock(mtx_); #endif ++use_count_; } It's because of this code that I use Loki::SmartPtr insted of shared_ptr. Jeremy Jurksztowicz [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Joshua Lehrer Guest Posted: Sun Mar 20, 2005 9:02 am    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of Roshan Naik wrote: Quote: 3) Andrei felt that boost::shared_ptr _may_ be using locks. I doubt it however. shared_ptr<> requries an OS specific way of atomically incrementing and decrementing a value, while simultaneously providing the new (or old) value. For OS's that do not have atomic_increment and atomic_decrement, this requires a lock. For example, here is some pseudo-code: shared_ptr<>::~shared_ptr<>() { if (0==atomic_decrement(count)) delete ptr; } .... where atomic_decrement returns the new value. boost wraps up the fact that the increment and decrement are OS specific in a class, which, IIRC, is called shared_count<>. So, to answer your question, shared_ptr<> uses locks, or other OS specific techniques, in order to atomically increment and decrement the shared count. joshua lehrer factset research systems NYSE:FDS [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Eric Niebler Guest Posted: Sun Mar 20, 2005 9:04 am    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of Jeremy J wrote: Quote: 3) Andrei felt that boost::shared_ptr _may_ be using locks. I doubt it however. From boost/detail/shared_count.hpp void add_ref_copy() { #if defined(BOOST_HAS_THREADS) mutex_type::scoped_lock lock(mtx_); #endif ++use_count_; } It's because of this code that I use Loki::SmartPtr insted of shared_ptr. Two days ago, Peter Dimov made shared_ptr lock-free on Windows, and it's coming on other platforms in the coming days. Check the boost CVS for the latest. You can read Peter's announcement here: http://aspn.activestate.com/ASPN/Mail/Message/boost/2524769 -- Eric Niebler Boost Consulting www.boost-consulting.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Andrei Alexandrescu (See Guest Posted: Sun Mar 20, 2005 9:11 am    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of Jeremy J wrote: Quote: 3) Andrei felt that boost::shared_ptr _may_ be using locks. I doubt it however. From boost/detail/shared_count.hpp void add_ref_copy() { #if defined(BOOST_HAS_THREADS) mutex_type::scoped_lock lock(mtx_); #endif ++use_count_; } It's because of this code that I use Loki::SmartPtr insted of shared_ptr. Peter Dimov's post as of two days ago suggests that this problem has been fixed on Windows. Other known SP designs that cater for multithreading used atomic increment and decrement since time immemorial, so I'm not sure why this delay. Anyhow, for others the same preference is determined by shared_ptr's compulsory presence of the deleter, whether or not you have a use for it; for others it's the compulsory weak_ptr support, whether or not you need that, etc. I encourage you and others interested in adding a policy-based smart pointer to boost (which in turn might influence seeing a policy-based smart pointer in the next C++ standard), to stay tuned on boost's mailing list. A policy-based smart pointer implemented by David B. Held and Jonathan Turkanis is about to be reviewed. You may want to participate to the review process. Andrei [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Roshan Naik Guest Posted: Sun Mar 20, 2005 11:28 pm    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of Quote: Boost::shared_ptr can be implemented without locks. But it provides basic thread-safety, not strong. Hazard pointers stuff is about lockless strong thread-safety, not basic. Another difference is that hazard pointers stuff needs hazardously expensive store-load barrier (not cheap even on IA32). I looked for definitions of basic/strong thread safety but couldnt find anything concrete. Could you please define them or provide links ? Anyway, let me rephrase the question slightly and move away from boost::shared_ptr... and focus on the underlying intent of my question. Can we create a smart pointer that effectively replaces the hazard pointers stuff ? And if yes, what properties would it need to have ? Seems like strong thread safety would be one requirement from your above statement. On a side note... the one thing about hazard pointers that makes me (only) slightly fussy, is that the destruction of objects is lazy and order of destruction is not really deterministic. C++ programmers essentially loose control over the order in which objects should be freed. -Roshan [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Joe Seigh Guest Posted: Sun Mar 20, 2005 11:40 pm    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of On 19 Mar 2005 20:51:28 -0500, Joe Seigh <jseigh_01 (AT) xemaps (DOT) com> wrote: A correction here Quote: Getting back to the hazard pointers vs. refcounting issue. ... The atomic_ptr version only did about 25000 reads per second per thread. That was an atomic_ptr proxy collector scheme. A linked list with atomic_ptr linking each element of the list would have run much slower. Slower than the mutex based version though it still would have been lock-free. There isn't any one best scheme. All the schemes have trade offs. It all depends on your particular situation. -- Joe Seigh [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Andrei Alexandrescu (See Guest Posted: Sun Mar 20, 2005 11:43 pm    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of Joshua Lehrer wrote: Quote: shared_ptr<> requries an OS specific way of atomically incrementing and decrementing a value, while simultaneously providing the new (or old) value. For OS's that do not have atomic_increment and atomic_decrement, this requires a lock. What OSs (I think you mean threading systems) would be those? Andrei [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Peter Dimov Guest Posted: Sun Mar 20, 2005 11:50 pm    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail (AT) moderncppdesign (DOT) com> wrote Quote: Peter Dimov's post as of two days ago suggests that this problem has been fixed on Windows. Other known SP designs that cater for multithreading used atomic increment and decrement since time immemorial, so I'm not sure why this delay. shared_ptr is unique in that in the general case it needs to maintain two reference counts. It took some time for Alexander Terekhov to discover a lock-free algorithm. The algorithm is overhead-free when shared_ptr is used as an ordinary strong smart pointer (i.e. it only touches one count in this case). The delay in incorporating his algorithm in the Boost code base is entirely my fault, of course. It should also be noted that many other SP implementations ignore the need for the atomic decrement to be a memory barrier. Without a barrier, the destructor may not see the latest object state. This makes lock-free reference counting hard to implement portably. On non-Windows platforms we're pretty much limited to g++'s __exchange_and_add as a portable primitive, which is an implementation detail of libstdc++ and nobody knows for sure what memory synchronization semantics it's supposed to have. Quote: Anyhow, for others the same preference is determined by shared_ptr's compulsory presence of the deleter, whether or not you have a use for it; Fixed. Quote: for others it's the compulsory weak_ptr support, whether or not you need that, Cost: one word. (Aside: you need that. You just don't know it yet.) Quote: etc. Cost: two words. ;-) [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jonathan Turkanis Guest Posted: Sun Mar 20, 2005 11:52 pm    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of Andrei Alexandrescu (See Website For Email) wrote: Hi Andrei, Quote: I encourage you and others interested in adding a policy-based smart pointer to boost (which in turn might influence seeing a policy-based smart pointer in the next C++ standard), to stay tuned on boost's mailing list. A policy-based smart pointer implemented by David B. Held and Jonathan Turkanis Thanks for the credit, but I'd say "implemented by Andrei Alexandrescu and David B.Held (and others)". My contribution was miniscule. ;-) Quote: is about to be reviewed. You may want to participate to the review process. Jonathan [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Andrei Alexandrescu (See Guest Posted: Mon Mar 21, 2005 7:00 am    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of Roshan Naik wrote: Quote: Boost::shared_ptr can be implemented without locks. But it provides basic thread-safety, not strong. Hazard pointers stuff is about lockless strong thread-safety, not basic. Another difference is that hazard pointers stuff needs hazardously expensive store-load barrier (not cheap even on IA32). I looked for definitions of basic/strong thread safety but couldnt find anything concrete. Could you please define them or provide links ? Anyway, let me rephrase the question slightly and move away from boost::shared_ptr... and focus on the underlying intent of my question. Can we create a smart pointer that effectively replaces the hazard pointers stuff ? And if yes, what properties would it need to have ? Seems like strong thread safety would be one requirement from your above statement. On a side note... the one thing about hazard pointers that makes me (only) slightly fussy, is that the destruction of objects is lazy and order of destruction is not really deterministic. C++ programmers essentially loose control over the order in which objects should be freed. But that should make you glad, not fussy. That pointers are not deleted immediately is fundamental, and it is exactly the feature that gives you the joy of lock-free operation and wait-free retiring: reader and writer threads are humming around undisturbed, and as a natural effect, some readers will be in effect while writers need to do their job; whenever you update a pointer, some readers might linger reading the obsoleted data. Any attempt to introduce compulsive retiring would necessarily introduce one thread waiting for another, phenomenon known as... locking ). Andrei [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Andrei Alexandrescu (See Guest Posted: Mon Mar 21, 2005 7:00 am    Post subject: Re: Lock Free Programming with Boost::shared_ptr instead of Peter Dimov wrote: Quote: "Andrei Alexandrescu (See Website For Email)" <SeeWebsiteForEmail (AT) moderncppdesign (DOT) com> wrote ..com>... Quote: shared_ptr is unique in that in the general case it needs to maintain two reference counts. What does "in the general case" mean? Does it, or does it not? I didn't know shared_ptr is compile-time configurable in any way except the #define'd multithreading aspect. Quote: Anyhow, for others the same preference is determined by shared_ptr's compulsory presence of the deleter, whether or not you have a use for it; Fixed. What does "fixed" mean? Is there space allocated for a deleter for each smart pointer? Is there runtime overhead induced by the deleter? Quote: for others it's the compulsory weak_ptr support, whether or not you need that, Cost: one word. (Aside: you need that. You just don't know it yet.) No. You don't need it. You just don't know it yet ). Quote: etc. Cost: two words. So what's the total cost in size of shared_ptr, itemized as sizeof(shared_ptr), plus the extra memory allocated per shared_ptr instance? Andrei [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Goto page 1, 2, 3 ... 10, 11, 12  Next Page 1 of 12   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.