Re: [boost] boost::shared_ptr<>::compare_and_swap()--AmIinsaneforwanting this?
My mistake. So that seems like a bit of a useless guarantee--basically any structure constructed with shared_ptr can only be read by the same thread that's writing to the structure unless all of the pointer operations are guarded with a mutex or spinlock, right? Ignoring compare-and-swap, have you or anyone else experimented with using a spinlock (as you mentioned previously) to remove the above restriction? What would that do to performance and complexity? Could you use a compare-and-swap type of operation to implement read/write thread safety? -- George T. Talbot <gtalbot@locuspharma.com>
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Peter Dimov Sent: Friday, November 10, 2006 10:16 AM To: boost@lists.boost.org Subject: Re: [boost] boost::shared_ptr<>::compare_and_swap()-- AmIinsaneforwanting this?
Talbot, George wrote:
I'm sorry if I'm being too dense here. I think a section in the documentation saying exactly what is guaranteed and what isn't would help a lot.
Here you go:
http://boost.org/libs/smart_ptr/shared_ptr.htm#ThreadSafety
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Talbot, George wrote:
So that seems like a bit of a useless guarantee--basically any structure constructed with shared_ptr can only be read by the same thread that's writing to the structure unless all of the pointer operations are guarded with a mutex or spinlock, right?
Or an rwlock. Correct, the guarantee isn't useful for writing lock-free code.
Ignoring compare-and-swap, have you or anyone else experimented with using a spinlock (as you mentioned previously) to remove the above restriction? What would that do to performance and complexity? Could you use a compare-and-swap type of operation to implement read/write thread safety?
The atomic operations would look like: shared_ptr copy( shared_ptr const & p ) lock spinlock for p shared_ptr r = p; unlock spinlock for p return r void replace( shared_ptr & p, shared_ptr q ) lock spinlock for p p.swap( q ); unlock spinlock for p bool compare_and_swap( shared_ptr & p, shared_ptr const & cmp, shared_ptr xchg ) lock spinlock for p bool r = p == cmp; if( r ) p.swap( xchg ); unlock spinlock for p return r; The critical regions are comfortably short, so using a spinlock seems justified. One problem is that shared_ptr doesn't have space for a spinlock, so we'd need to use a hashed spinlock pool keyed on 'this'. Or it might be possible to reuse the pointer as a spinlock, using something like (void*)-1 as the 'locked' state. I haven't prototyped it, but it seems workable.
Peter Dimov wrote:
bool compare_and_swap( shared_ptr & p, shared_ptr const & cmp, shared_ptr xchg )
lock spinlock for p bool r = p == cmp; if( r ) p.swap( xchg ); unlock spinlock for p return r;
This actually should be trylock spinlock for p if failed return false bool r = p == cmp; if( r ) p.swap( xchg ); unlock spinlock for p return r;
Okay. I will go ahead and post the CAS operations for my "'mostly' lock-free refcount library alternative for Boost...": http://appcore.home.comcast.net/vzoom/refcount/ ;^) If you set your algorithm up right, the low-level nature of the API allows you to do perform lock-free naked loads for the CAS 'compare' logic. You can take advantage of its ability to allow you to know when you can make use of no/basic/strong thread-safety guarantees'. This is a reason why I like to make the API abstractions of my prototypes in a fairly low-level fashion... As soon as I add the rest of the code and the draft-level descriptions that go along with it to my paper; it has to reference atomic reference counting /w CAS anyway it anyway: http://appcore.home.comcast.net/vzdoc/atomic/static-init/ Luckily, I don't have to use DWCAS, and Boost can use it because its my prior art/invention. I do have to say that its performance is definitely not in the same league as my Virtually Zero-Overhead Object Management (vZOOM) solution, or some the zero-overhead algorithm that Joe Seigh has been inventing over at c.p.t. And, FWIW, here is a implementation of a smart-pointer that has lock-free atomic swap/cas, however, it uses SMR which has that memory barrier, and that patent application: http://appcore.home.comcast.net/ Enjoy! ;^)
Hi, sorry for the TP. I came across a post on the gcc mailing list today that says they are working on some sort of link time optimization. Specifically, they said separately compiled modules will no longer be safe from reordering. I don't know if there is a distinction between what you say here: "All of its “critical-sequences” are contained in externally assembled functions ( read all ) in order to prevent a rouge C compiler from reordering anything that would corrupt the data-structure" and what is implied by the post. Would a toolchain that provides link time rejigging possibly make this bomb at some point? -----Original Message----- From: boost-bounces@lists.boost.org on behalf of Chris Thomasson Sent: Fri 11/10/2006 8:20 PM To: boost@lists.boost.org Subject: Re: [boost]boost::shared_ptr<>::compare_and_swap()--AmIinsaneforwanting this? Okay. I will go ahead and post the CAS operations for my "'mostly' lock-free refcount library alternative for Boost...":
"Sohail Somani" <s.somani@fincad.com> wrote in message news:1C1EBEF8DBACDC439D038EA051674EC73EDF87@xbox.financialcad.com...
Hi, sorry for the TP.
I came across a post on the gcc mailing list today that says they are working on > some sort of link time optimization. Specifically, they said separately compiled > modules will no longer be safe from reordering. I don't know if there is a distinction between what you say here: "All of its "critical-sequences" are contained in externally assembled functions ( read all ) in order to prevent a rouge C compiler from reordering anything that would corrupt the data-structure" > and what is implied by the post.
Would a toolchain that provides link time rejigging possibly make this bomb at > > some point?
Well, that depends how how well the compiler in question supports the ability to turn this specific type of optimization on, or off... Humm... FWIW, here is what I have to say on the subject: http://groups.google.com/group/comp.programming.threads/msg/a8d7067bc1425ae1 http://groups.google.com/group/comp.programming.threads/msg/0afc1109d18c2991 http://groups.google.com/group/comp.programming.threads/msg/fd3b4b5a5cd7841e http://appcore.home.comcast.net/vzdoc/atomic/static-init/ (section 2...) Any thoughts? ;^)
"Chris Thomasson" <cristom@comcast.net> wrote in message news:ej3iak$use$1@sea.gmane.org...
Okay. I will go ahead and post the CAS operations for my "'mostly' lock-free refcount library alternative for Boost...":
http://appcore.home.comcast.net/vzoom/refcount/
;^)
Here is the code for the CAS functions that are compatible with my current refcount library: .align 16 # int refcount_ia32_cas( # refcount_ia32_t* volatile*, # refcount_ia32_t*, # refcount_ia32_t*) .globl _refcount_ia32_cas _refcount_ia32_cas: MOVL 4(%ESP), %ECX TESTL %ECX, %ECX JE refcount_ia32_cas_failed MOVL 8(%ESP), %EAX MOVL 12(%ESP), %EDX LOCK CMPXCHGL %EDX, (%ECX) JNE refcount_ia32_cas_failed MOVL $1, %EAX RETL refcount_ia32_cas_failed: XORl %EAX, %EAX RETL .align 16 # int refcount_ia32_add_cas_weak( # refcount_ia32_t* volatile*, # refcount_ia32_t*, # refcount_ia32_t*, # int) .globl _refcount_ia32_add_cas_weak _refcount_ia32_add_cas_weak: MOVL 4(%ESP), %ECX TESTL %ECX, %ECX JE refcount_ia32_cas_failed MOVL 12(%ESP), %EDX TESTL %EDX, %EDX JE refcount_ia32_add_cas_weak_execute MOVL 16(%ESP), %EAX CMPL $0, %EAX JLE refcount_ia32_add_cas_weak_execute LOCK XADDL %EAX, (%EDX) refcount_ia32_add_cas_weak_execute: MOVL 8(%ESP), %EAX LOCK CMPXCHG %EDX, (%ECX) JNE refcount_ia32_add_cas_weak_dec MOVL $1, %EAX RETL refcount_ia32_add_cas_weak_dec: TESTL %EDX, %EDX JE refcount_ia32_add_cas_weak_failed CMPL $0, 16(%ESP) JLE refcount_ia32_add_cas_weak_failed LOCK DECL (%EDX) refcount_ia32_add_cas_weak_failed: XORL %EAX, %EAX RETL If you want to use CAS with my refcount library now, just stick the posted source code in the refcount-ia32-mingw.asm file and assemble... Then create the declarations in the refcount-ia32.h file, and add the proper member functions to the refcount-sys.hpp and refcount.hpp files... Simple... ;^) I am going to add the CAS to my library very soon, I will definitely keep you posted...
participants (4)
-
Chris Thomasson -
Peter Dimov -
Sohail Somani -
Talbot, George