From: Talbot, George (Gtalbot_at_[hidden])
Date: 2008-07-23 10:29:13
Hi!
Thanks for responding.
> -----Original Message-----
> From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]]
> On Behalf Of Dean Michael Berris
> Sent: Tuesday, July 22, 2008 9:24 PM
> To: boost_at_[hidden]
> Subject: Re: [boost] Would anybody like a wrapper atomic_shared<T>
> aroundshared_ptr<T>?
>
> Hi George,
>
> On Wed, Jul 23, 2008 at 6:04 AM, Talbot, George
<Gtalbot_at_[hidden]>
> wrote:
> >
> > A while back (~2006 I think) I was asking around on this list about
> > using boost::shared_ptr<T> to build a composite data structure that
can
> > be accessed and modified by multiple threads.
> >
> > Peter Dimov's suggestion at the time was to write a wrapper class
for
> > boost::shared_ptr<T> that would protect access to the
> > boost::shared_ptr<T> with a spinlock. I've done this, and this
works
> > pretty good in my application. I'm interested in contributing this
code
> > to BOOST, as it's been quite useful.
> >
> > I have a few questions:
> >
> > 1) Is there interest in such a donation. It's just one header
file,
> > and it's wafer-thin...
>
> I am interested, although I do have some reservations with it not
> using the locks already available in Boost.Thread.
I would likely convert it to do so. Haven't got around to that yet.
> > 2) If so, how does one go about making such a donation?
>
> (I think it's a little funny that you use 'donation' instead of
> contribution... but nonetheless... ;-) )
Sorry....contribution. I'm a bit of a space cadet. ;^)
> >From what I gather, this is something that may have to go through a
> mini-review. The veterans can answer this question better though.
I'm sure, and that would be great, actually.
> > 3) My implementation below uses a spinlock to protect things and
> > as one might expect, under load my application does spend some
> > time in ::pthread_spin_lock(). Is there a way to rewrite this
> > class (possibly with friendship of boost::shared_ptr<T>) in a
> > lock-free manner? I've attached the code below...
> >
>
> I'm not sure about lock-free approaches, but doesn't shared_ptr<T>
> already use atomic operations when built in multi-threaded mode?
Yes, but read the Thread Safety page. The guarantee you get from
shared_ptr<T> is that two or more separate instances in separate threads
that point to the same object and refcount will be handled lock-free and
work properly. However it explicitly does not guarantee multiple
threads looking at the _same_ instance of shared_ptr<T> can perform
operations upon that same instance without some sort of additional
guarantees. The purpose of this class is to provide that guarantee.
> Another issue I see is the dependence to ::pthread_spin_lock() -- can
> you use a shared recursive_mutex instead?
How expensive is that in memory and time? I was using
::pthread_spin_lock() because on my x86_64 Linux box, pthread_spinlock_t
is a single machine word.
Also, it's just a proof-of-concept. I think the "right thing" is to be
able to implement the unary bool operators, get() and compare_and_set()
via a lock-free algorithm. My problem is that I don't have enough depth
of knowledge of the lock-free shared_ptr<T> class in BOOST to be able to
work out such an algorithm. I was hoping for a little bit of "pointing
in the right direction" from the author(s) of BOOST's lock-free
shared_ptr<T> implementation.
That said I'd have no problem "falling-back" to using a shared
recursive_mutex instead if a lock-free algorithm isn't available on a
particular platform. As such, attached below is a rewrite using
recursive_try_mutex...This appears similar in execution efficiency to my
previous implementation with the spinlock in my stress test. It appears
from examining the pthread libraries that the mutex is using about 8
machine words instead of one for the spinlock.
Of course, as above, I'd prefer no lock at all; I'll see what I can come
up with.
Thanks for looking at this.
--
George T. Talbot
gtalbot_at_[hidden]
/** \file atomic_shared.h
*
* \author George T. Talbot
* \author Peter Dimov
*
* \brief This file defines a template class that can wrap
* boost::shared_ptr and provide thread-safe atomic
* get/set operations on them.
*
* (C) Copyright Locus Pharmaceuticals, Inc., Peter Dimov 2006.
*
* Distributed under the Boost Software License, Version 1.0. (See
* accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
*/
#ifndef ATOMIC_SHARED_H
#define ATOMIC_SHARED_H
#include <boost/shared_ptr.hpp>
#include <boost/pointer_cast.hpp>
#include <boost/thread/recursive_mutex.hpp>
/** atomic_shared<T> wraps boost::shared_ptr<T> with a mutex and a very
* restricted set of operations so that a large composite data
structure
* may be accessed by multiple threads with a minimum of locking
contention.
*
* Threads working on a large composite data structure create their own
* private boost::shared_ptr<T> around their own new nodes and then use
* compare_and_set() to place their new nodes in the composite data
* structure.
*
* Threads that are viewing the composite data structure may call get()
to
* get a private copy of the pointer so they can do some work with it.
The
* intended idiom for modifications to nodes is like so:
*
* \code
*
* atomic_shared<const Blah> global_blah;
*
* void modify_the_global_blah_in_many_threads_with_no_locking()
* {
* bool done = false;
* do
* {
* boost::shared_ptr<const Blah>
my_blah(global_blah.get());
*
* boost::shared_ptr<Blah> new_blah(*my_blah);
* new_blah->some_modification();
* done = global_blah.compare_and_set(my_blah,
new_blah);
* }
* while (!done);
* }
*
* \endcode
*
* Threads that just need to do some work looking at the node:
*
* \code
*
* void print_the_global_blah_in_many_threads_with_no_locking()
* {
* boost::shared_ptr<const Blah> my_blah(global_blah.get());
*
* my_blah->print();
* }
*
* \endcode
*
* Using atomic_shared<T> this way satisfies the Thread Safety portion
of
* the boost::shared_ptr<T> documentation.
*/
template<class T>
class atomic_shared
{
atomic_shared& operator=(const atomic_shared&);
public:
typedef boost::shared_ptr<T> base_ptr;
/** construct an empty pointer. */
atomic_shared()
: ptr(),
mutex()
{
}
/** copy constructor. Since we like to put atomic_shared<> in
std::map<>
* via std::map<atomic_shared<T> >::insert(std::make_pair(key,
value)),
* this needs to be here.
*/
atomic_shared(const atomic_shared& p)
: ptr(p.get()),
mutex()
{
}
/** construct a protected pointer from a bare one. */
template<class Y>
explicit atomic_shared(Y* p)
: ptr(p),
mutex()
{
}
/** construct a protected pointer from a shared_ptr. */
template<class U>
explicit atomic_shared(const boost::shared_ptr<U>& p)
: ptr(p),
mutex()
{
}
~atomic_shared()
{
}
/** Is it not null? */
operator bool() const
{
bool rv;
{
boost::recursive_try_mutex::scoped_lock l(mutex);
rv = ptr;
}
return rv;
}
/** Is it null? */
bool operator!() const
{
bool rv;
{
boost::recursive_try_mutex::scoped_lock l(mutex);
rv = !ptr;
}
return rv;
}
/** Right here is the only way to _use_ the pointer. To use what
the
* pointer is pointing to, you must make a private copy in your
* thread.
*/
inline base_ptr get() const
{
base_ptr p;
{
boost::recursive_try_mutex::scoped_lock l(mutex);
p = ptr;
}
return p;
}
/** Attempt to set the value of the pointer with another pointer,
but
* only if the pointer is the same as a previously sampled value of
* the pointer.
*
* @param cmp Value of pointer previously retrieved with
get().
* @param x New value of pointer.
* @return true if the pointer could be set to x (i.e. its value
was
* still cmp with the mutex locked.)
*/
template<class Y, class X>
bool compare_and_set(const boost::shared_ptr<Y>& cmp,
boost::shared_ptr<X>& x)
{
bool r = false;
boost::recursive_try_mutex::scoped_try_lock l(mutex, false);
if (l.try_lock())
{
r = ptr == cmp;
if (r) ptr = x;
}
return r;
}
private:
base_ptr ptr;
mutable boost::recursive_try_mutex mutex;
}; // atomic_shared
#endif