mt-safe deque with boost::threads? - C++ Language (Moderated)

C++Talk.NET
C++ language newsgroups

Archives

FAQ

Memberlist

Usergroups

Profile

mt-safe deque with boost::threads?
Goto page 1, 2 Next

C++Talk.NET Forum Index -> C++ Language (Moderated)

View previous topic :: View next topic

Author

Message

shakahshakah@gmail.com
Guest

Posted: Thu Oct 27, 2005 10:33 am Post subject: mt-safe deque with boost::threads?

Just started playing around with boost::threads, and I'm wondering if the following is (1) actually mt-safe and (2) in keeping with normal boost usage? From a quick look around boost I guess "class mt_deque : private boost::noncopyable" might be in order, but otherwise...? template<typename T> class mt_deque { public: mt_deque() { } T pop() { boost::mutex::scoped_lock lCond(m_) ; while(theQueue_.empty()) { cNotEmpty_.wait(lCond) ; } T t = theQueue_.front() ; theQueue_.pop_front() ; return t ; } void push(const T& t) { boost::mutex::scoped_lock lCond(m_) ; theQueue_.push_back(t) ; cNotEmpty_.notify_one() ; } private: boost::condition cNotEmpty_ ; boost::mutex m_ ; std::deque<T> theQueue_ ; } ; [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]

Raoul Gough
Guest

Posted: Fri Oct 28, 2005 10:59 am Post subject: Re: mt-safe deque with boost::threads?

[email]shakahshakah (AT) gmail (DOT) com[/email] wrote:

Quote:

Just started playing around with boost::threads, and I'm wondering if
the following is (1) actually mt-safe and (2) in keeping with normal
boost usage? From a quick look around boost I guess "class mt_deque :
private boost::noncopyable" might be in order, but otherwise...?

template<typename T
class mt_deque {
public:
mt_deque() {
}

T pop() {
boost::mutex::scoped_lock lCond(m_) ;
while(theQueue_.empty()) {
cNotEmpty_.wait(lCond) ;
}

T t = theQueue_.front() ;
theQueue_.pop_front() ;
return t ;
}

Strictly speaking, there is a bit of a problem with this in terms of
exception safety. If the T copy constructor can throw, then you might
lose items from the queue, since you (potentially anyway) need to copy
t on return from the function. At the point of return, you've already
popped the item of the queue, so an exception thrown on return would
lose the item. This may not be a practical issue, depending on how
you're using the queue.

The problem is slightly tricky to solve, since you need to hold a lock
to prevent the contents changing between calling empty(), front(), and
pop_front(). I did it once, more or less as a programming exercise,
using a "locking proxy" object that the container could return to
client code. The proxy provides functions blockOnEmpty() and
blockOnFull(), as well as access to the raw container object via
operator->(). This was probably a risky strategy, and involved the
proxy destructor checking for changes in container size and notifying
the relevant conditions (no longer full, no longer empty). My original
implementation was slightly different, but the idea would be to use it
like this:

typedef mt::SafeQueue<std::deque Queue;

void foo(Queue &q)
{
// Get a locking proxy
std::auto_ptr<Queue::proxy> p = q.proxy();

// Wait for something in the queue
p->blockOnEmpty();

// Now access the raw container directly
SomeType s = (*p)->front(); // Copy out the first item

(*p)->pop_front(); // Remove first item from queue

p.reset(); // Destroy proxy, releasing lock and notifying not full

// Now process s
}

One kind of nifty thing about this is that you could (potentially
anyway) access multiple items from the queue without having to acquire
and release the mutex for each one. i.e. you could get the proxy, look
at many items and only then destroy the proxy. It was an interesting
exercise anyway, but I'm not sure the complexity would be worth it in
many circumstances.

--
Raoul Gough.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Sebastian Redl
Guest

Posted: Fri Oct 28, 2005 6:30 pm Post subject: Re: mt-safe deque with boost::threads?

[email]shakahshakah (AT) gmail (DOT) com[/email] wrote:

Quote:

I think the biggest problem with using internally synchronized
containers is that you can't use iterators very well any longer. An
iterator would have to hold a lock for its entire existence; otherwise
you might run into concurrent modification problems. I think it would
be generally more desireable to synchronize the container
externally.

-- Sebastian Redl

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Steven E. Harris
Guest

Posted: Sat Oct 29, 2005 1:02 pm Post subject: Re: mt-safe deque with boost::threads?

"Raoul Gough" <RaoulGough (AT) yahoo (DOT) co.uk> writes:

Quote:

The problem is slightly tricky to solve, since you need to hold a
lock to prevent the contents changing between calling empty(),
front(), and pop_front(). I did it once, more or less as a
programming exercise, using a "locking proxy" object that the
container could return to client code.

For a similar approach, take a look at my two_lock_queue class
described in a recent thread on the boost-devel list:

http://article.gmane.org/gmane.comp.lib.boost.devel/132317

This article is part of the thread "bounded_blocking_queue,
unbounded_blocking_queue":

http://thread.gmane.org/gmane.comp.lib.boost.devel/132253

--
Steven E. Harris

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

shakahshakah@gmail.com
Guest

Posted: Sat Oct 29, 2005 1:11 pm Post subject: Re: mt-safe deque with boost::threads?

Raoul Gough wrote:

Quote:

shakahshakah (AT) gmail (DOT) com wrote:

[...stuff snipped...]

Strictly speaking, there is a bit of a problem with this in terms of
exception safety. If the T copy constructor can throw, then you might
lose items from the queue, since you (potentially anyway) need to copy
t on return from the function. At the point of return, you've already
popped the item of the queue, so an exception thrown on return would
lose the item. This may not be a practical issue, depending on how
you're using the queue.

[...more snipped...]

Thank you for the feedback. I guess the following would sidestep that
issue?

T& pop(T& t) {
boost::mutex::scoped_lock lCond(m_) ;
while(theQueue_.empty()) {
cNotEmpty_.wait(lCond) ;
}

t = theQueue_.front() ;
theQueue_.pop_front() ;
return t ;
}

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Branimir Maksimovic
Guest

Posted: Sat Oct 29, 2005 7:42 pm Post subject: Re: mt-safe deque with boost::threads?

[email]shakahshakah (AT) gmail (DOT) com[/email] wrote:

Quote:

What you actually wrote is consumer and producer.
In such cases something like shared_ptr is just right,
because it has certain gurantees about exceptions,
and then you don't have a problem.

Quote:

template<typename T
class mt_deque {
public:
mt_deque() {
}

shared_ptr

Quote:

boost::mutex::scoped_lock lCond(m_) ;
while(theQueue_.empty()) {
cNotEmpty_.wait(lCond) ;
}

shared_ptr<T> t = theQueue_.front();
theQueue_.pop_front() ;
return t ;
}

void push(shared_ptr<T> t) {
boost::mutex::scoped_lock lCond(m_) ;
theQueue_.push_back(t) ;
cNotEmpty_.notify_one() ;
}

private:
boost::condition cNotEmpty_ ;
boost::mutex m_ ;
std::deque<shared_ptr theQueue_;
} ;

Greetings, Bane.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Sean Kelly
Guest

Posted: Sat Oct 29, 2005 8:16 pm Post subject: Re: mt-safe deque with boost::threads?

Raoul Gough wrote:

Quote:

Assuming this doesn't need to be interface compatible:

T& pop(T& t) {
boost::mutex::scoped_lock lCond(m_) ;
while(theQueue_.empty()) {
cNotEmpty_.wait(lCond) ;
}

t = theQueue_.front() ;
theQueue_.pop_front() ;
return t ;
}

Though I generally do something closer to this:

bool pop(T& t) {
boost::mutex::scoped_lock lCond(m_) ;
if(theQueue_.empty())
return false;
t = theQueue_.front();
theQueue_.pop_front();
return true;
}

as I generally prefer being able to do other work instead of stalling
on an empty container.

Sean

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

James Kanze
Guest

Posted: Sun Oct 30, 2005 3:32 am Post subject: Re: mt-safe deque with boost::threads?

Branimir Maksimovic wrote:

Quote:

shakahshakah (AT) gmail (DOT) com wrote:

Just started playing around with boost::threads, and I'm
wondering if the following is (1) actually mt-safe and (2) in
keeping with normal boost usage? From a quick look around
boost I guess "class mt_deque : private boost::noncopyable"
might be in order, but otherwise...?

What you actually wrote is consumer and producer. In such
cases something like shared_ptr is just right, because it has
certain gurantees about exceptions, and then you don't have a
problem.

If what he wrote is meant to be used as a message queue between
threads (consumer/producer), then boost::shared_ptr (or
tr1::shared_ptr) is NOT right. This is a case where you
absolutely want the semantics of std::auto_ptr -- once you've
passed the object off to the other thread, you don't want to
accidentally access it until the other thread is through with it
and has passed it back.

I'm not sure, however, that this is what he wanted. His
mt_deque passed objects by value. Objects which might be on
the stack, or static. Using one of the smart pointers means
that all objects which are passed must be dynamically allocated.
Every time I've needed to pass objects between threads, the
objects have been polymorphic, and passing a pointer to a
dynamicly allocated object was the way to go, but that's not
what his class was designed to do, and I suppose he had his
reasons.

Anyway, what I've done is similar to what you've done, except
that it uses std::auto_ptr:

Quote:

template<typename T
class mt_deque {
public:
mt_deque() {
}

shared_ptr

std::auto_ptr<T> pop() {

Quote:

boost::mutex::scoped_lock lCond(m_) ;
while(theQueue_.empty()) {
cNotEmpty_.wait(lCond) ;
}

shared_ptr<T> t = theQueue_.front();

std::auto_ptr<T> t( theQueue_.front() ) ;

Quote:

theQueue_.pop_front() ;
return t ;
}

void push(shared_ptr<T> t) {

void push( std::auto_ptr<T> t ) {

Quote:

boost::mutex::scoped_lock lCond(m_) ;
theQueue_.push_back(t) ;

This one's tricky with auto_ptr. Can't release the pointer from
auto_ptr until it's really in the deque:

theQueue_.push_back( t.get() ) ;
t.release() ;

Quote:

cNotEmpty_.notify_one() ;

I generally use notify_all(). Just to be sure.

Quote:

}

private:
boost::condition cNotEmpty_ ;
boost::mutex m_ ;

std::deque<shared_ptr theQueue_;

std::deque< T* > theQueue_ ;

(Obviously, I can't use auto_ptr here.)

Quote:

} ;

And of course, since the deque can't hold auto_ptr, you need a
destructor:

mt_deque::~mt_deque()
{
while ( ! theQueue_.empty() ) {
std::auto_ptr< T > tmp( theQueue_.front() ) ;
theQueue_.pop_front() ;
}
}

--
James Kanze mailto: [email]james.kanze (AT) free (DOT) fr[/email]
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Roland Pibinger
Guest

Posted: Sun Oct 30, 2005 3:02 pm Post subject: Re: mt-safe deque with boost::threads?

On 29 Oct 2005 23:32:34 -0400, James Kanze <kanze (AT) none (DOT) news.free.fr>
wrote:

Quote:

Branimir Maksimovic wrote:
[email]shakahshakah (AT) gmail (DOT) com[/email] wrote:

If what he wrote is meant to be used as a message queue between
threads (consumer/producer), then boost::shared_ptr (or
tr1::shared_ptr) is NOT right.

Right!

Quote:

This is a case where you
absolutely want the semantics of std::auto_ptr -- once you've
passed the object off to the other thread, you don't want to
accidentally access it until the other thread is through with it
and has passed it back.

Strictly speaking, that doesn't work (as described by you below).
Nothing prevents you from using the _same_ auto_ptr in different
threads (by pointer to auto_ptr). Setting the internal pointer in
auto_ptr to 0 is not atomic in that case.

Quote:

Anyway, what I've done is similar to what you've done, except
that it uses std::auto_ptr:

template<typename T
class mt_deque {
public:
[...]
void push( std::auto_ptr
boost::mutex::scoped_lock lCond(m_) ;
theQueue_.push_back(t) ;

This one's tricky with auto_ptr. Can't release the pointer from
auto_ptr until it's really in the deque:

theQueue_.push_back( t.get() ) ;
t.release() ;

Problem here (at least)!

The general disadvantage of the above design is that the whole
underlying queue must be locked for for each 'push' and 'pop'. Even if
you use faster atomic primitives that is not accepptable in many
cases. One needs faster mechanisms (reportedly, Java has them in 1.5).

Best wishes,
Roland Pibinger

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Branimir Maksimovic
Guest

Posted: Mon Oct 31, 2005 10:51 am Post subject: Re: mt-safe deque with boost::threads?

James Kanze wrote:

Quote:

Branimir Maksimovic wrote:
[email]shakahshakah (AT) gmail (DOT) com[/email] wrote:

Just started playing around with boost::threads, and I'm
wondering if the following is (1) actually mt-safe and (2) in
keeping with normal boost usage? From a quick look around
boost I guess "class mt_deque : private boost::noncopyable"
might be in order, but otherwise...?

What you actually wrote is consumer and producer. In such
cases something like shared_ptr is just right, because it has
certain gurantees about exceptions, and then you don't have a
problem.

If what he wrote is meant to be used as a message queue between
threads (consumer/producer), then boost::shared_ptr (or
tr1::shared_ptr) is NOT right. This is a case where you
absolutely want the semantics of std::auto_ptr -- once you've
passed the object off to the other thread, you don't want to
accidentally access it until the other thread is through with it
and has passed it back.

True. But I don't do that way. Usually producer / consumer just
recycle same objects without frequent new/delete. So
at least two threads always have reference to same object.
In this way I reduce number of alloc/frees and
constructor/destructor calls. I implement busy/setbusy
member function that is protected by lock in order to signal if
thread can use or not particular object.
In this way, sometimes push pop operations are just
a matter of setting/resetting busy flag and object is alive
till session is open assiciated with particular object.
Of course such data structure is not in
this example in any way and you are completelly right.

Quote:

I'm not sure, however, that this is what he wanted. His
mt_deque passed objects by value. Objects which might be on
the stack, or static.

Fair enough.

Greetings, Bane.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

kanze
Guest

Posted: Tue Nov 01, 2005 9:47 am Post subject: Re: mt-safe deque with boost::threads?

Roland Pibinger wrote:

Quote:

On 29 Oct 2005 23:32:34 -0400, James Kanze
[email]kanze (AT) none (DOT) news.free.fr[/email]> wrote:
Branimir Maksimovic wrote:
[email]shakahshakah (AT) gmail (DOT) com[/email] wrote:

If what he wrote is meant to be used as a message queue
between threads (consumer/producer), then boost::shared_ptr
(or tr1::shared_ptr) is NOT right.

Right!

This is a case where you absolutely want the semantics of
std::auto_ptr -- once you've passed the object off to the
other thread, you don't want to accidentally access it until
the other thread is through with it and has passed it back.

Strictly speaking, that doesn't work (as described by you
below). Nothing prevents you from using the _same_ auto_ptr
in different threads (by pointer to auto_ptr). Setting the
internal pointer in auto_ptr to 0 is not atomic in that case.

Well, you can certainly go behind the back of the queue ; the
receiving process can, for example, copy the results of a get()
on its auto_ptr into a global variable, and then everybody can
access the object. The idiom is designed to protect against
Murphy, not Machiavelli.

Quote:

With a solution, which was given.

I think a more fundamental "problem" is that the deque itself
cannot hold auto_ptr, so you have to extract the raw pointer.
However, the code for doing this is pretty well encapsulated, so
as far as the user is concerned, he's sending an auto_ptr to the
queue, and getting one out of it.

Quote:

The general disadvantage of the above design is that the whole
underlying queue must be locked for for each 'push' and 'pop'.
Even if you use faster atomic primitives that is not
accepptable in many cases. One needs faster mechanisms
(reportedly, Java has them in 1.5).

It's not generally a problem. It might pose a problem in
certain, critical applications, but most of the current
applications, the time required to acquire the lock is
negligeable compared to the rest of what will be going on.

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

shakahshakah@gmail.com
Guest

Posted: Tue Nov 01, 2005 9:49 am Post subject: Re: mt-safe deque with boost::threads?

James Kanze wrote:

Quote:

[...stuff deleted...]

I'm not sure, however, that this is what he wanted. His
mt_deque passed objects by value. Objects which might be on
the stack, or static. Using one of the smart pointers means
that all objects which are passed must be dynamically allocated.
Every time I've needed to pass objects between threads, the
objects have been polymorphic, and passing a pointer to a
dynamicly allocated object was the way to go, but that's not
what his class was designed to do, and I suppose he had his
reasons.

[...stuff deleted...]

Intended use is a blocking queue for asynchronous Postgres
notifications, where the producers LISTEN on db connections and the
consumers block waiting for those notifications (logical meaning of a
notification is "there might be some work to do, wake up and go take a
look").

In any case, thank you all for the ideas and comments. Nice to see that
Usenet can still be helpful and polite.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Raoul Gough
Guest

Posted: Wed Nov 02, 2005 11:36 am Post subject: Re: mt-safe deque with boost::threads?

[email]shakahshakah (AT) gmail (DOT) com[/email] wrote:

Quote:

Raoul Gough wrote:
[email]shakahshakah (AT) gmail (DOT) com[/email] wrote:

[...stuff snipped...]

Strictly speaking, there is a bit of a problem with this in terms of
exception safety. If the T copy constructor can throw, then you might
lose items from the queue, since you (potentially anyway) need to copy
t on return from the function. At the point of return, you've already
popped the item of the queue, so an exception thrown on return would
lose the item. This may not be a practical issue, depending on how
you're using the queue.

[...more snipped...]

Thank you for the feedback. I guess the following would sidestep that
issue?

T& pop(T& t) {
boost::mutex::scoped_lock lCond(m_) ;
while(theQueue_.empty()) {
cNotEmpty_.wait(lCond) ;
}

t = theQueue_.front() ;
theQueue_.pop_front() ;
return t ;
}

Hmmm, never thought about doing it that way - the STL containers all
separate front() and pop_front() into two distinct functions to avoid
the exception safety problems. At least, I seem to remember reading
that that was the reason for separating them.

I suppose the only disadvantage of having to pass in a reference to the
object to be returned is that you would have first to construct a T
object before calling pop (and you then assign over the top of it). I
suppose another approach would be to pass a pointer to uninitialized
memory and copy-construct into it via placement new, but that would
bring a whole lot of other (probably worse) inconveniences.

--
Raoul Gough.

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

James Kanze
Guest

Posted: Wed Nov 02, 2005 11:38 am Post subject: Re: mt-safe deque with boost::threads?

Branimir Maksimovic wrote:

Quote:

James Kanze wrote:

Branimir Maksimovic wrote:

[email]shakahshakah (AT) gmail (DOT) com[/email] wrote:

Just started playing around with boost::threads, and I'm
wondering if the following is (1) actually mt-safe and (2)
in keeping with normal boost usage? From a quick look around
boost I guess "class mt_deque : private boost::noncopyable"
might be in order, but otherwise...?

What you actually wrote is consumer and producer. In such
cases something like shared_ptr is just right, because it has
certain gurantees about exceptions, and then you don't have a
problem.

If what he wrote is meant to be used as a message queue
between threads (consumer/producer), then boost::shared_ptr
(or tr1::shared_ptr) is NOT right. This is a case where you
absolutely want the semantics of std::auto_ptr -- once you've
passed the object off to the other thread, you don't want to
accidentally access it until the other thread is through with
it and has passed it back.

True. But I don't do that way. Usually producer / consumer
just recycle same objects without frequent new/delete.

My solution will work in that case as well. What it does
require is that 1) the original object is allocated on the heap
(regardless of how many times it is recycled after that), and 2)
in case of an exception in the put function (bad_alloc), the
object must be reallocated.

Quote:

So at least two threads always have reference to same object.

Why? Even recycling the objet, this isn't necessary, and
introduces an unnecessary risk (although I would agree that if
the program is correctly structured and documented, the risk
isn't that great).

Quote:

In this way I reduce number of alloc/frees and
constructor/destructor calls.

I've not found this to be a problem. If it were, I might start
by using some sort of fixed length allocator for the objects.
(I think Boost has one, and I have one in my tool kit.) But
don't forget that you're using a heavy-weight mechanism after
the allocate -- I find it hard to believe that the cost of the
allocation/deletion is measurable compared to what the receiving
process will be doing. And of course, construction/destruction
is not necessarily that much more expensive than the assignment
necessary to set up the new parameters.

What I do do fairly systematically is use the same object for
the request and the response (and that object will typically
contain the address of the message queue to which the response
should be sent).

Quote:

I implement busy/setbusy member function that is protected by
lock in order to signal if thread can use or not particular
object. In this way, sometimes push pop operations are just a
matter of setting/resetting busy flag and object is alive till
session is open assiciated with particular object. Of course
such data structure is not in this example in any way and you
are completelly right.

In the original example, I don't know what the goal of the deque
was. The poster didn't tell us:-). I described one particular
implication, for a particular use, which has worked well for me.
It's obviously not the only solution -- my use isn't even the
only possible problem. As it happens, I like the fact that the
objet is only accessible from one thread at a time. I find this
a safety feature. In fact, I use the idiom even when I'm using
garbage collection -- the interest of auto_ptr here isn't memory
management, per se (although in the absense of garbage
collection, it provides a safety net in case of exceptions);;
the interest is the "unusual" assignment semantics.

--
James Kanze mailto: [email]james.kanze (AT) free (DOT) fr[/email]
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

David Abrahams
Guest

Posted: Thu Nov 03, 2005 10:55 am Post subject: Re: mt-safe deque with boost::threads?

"Raoul Gough" <RaoulGough (AT) yahoo (DOT) co.uk> writes:

Quote:

No, they were just naturally written that way. Exception-safety came
later. If I had to guess, I'd say it was done that way because you
might want to inspect the front element without removing it, and you
might want to remove the front element without inspecting it.

--
Dave Abrahams
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! ]

Display posts from previous:

	C++Talk.NET Forum Index -> C++ Language (Moderated)	All times are GMT Goto page 1, 2 Next
Page 1 of 2

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