Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Fwiw, a thread-safe c++ deque example...
183 views
Skip to first unread message
Chris M. Thomasson
Mar 19, 2017, 8:42:19 PM3/19/17
to
This queue can be spiced up with exotic C++ atomics and such, but for
now, lets focus on this simple construct:
A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
deque. This queue is actually multi-producer/consumer, but the test
example code uses a single producer. Also, it uses a special mutex to
make sure calls to printf are thread-safe! ;^)
http://pastebin.com/raw/GA9pJvKN
(pastebin link without ads! ;^)
<code>
_________________________________________
#include <cstdio>
#include <deque>
#include <condition_variable>
#include <mutex>
#include <memory>
#include <thread>
#include <algorithm>
#include <cassert>
template<typename T>
struct queue
{
typedef std::deque<T> raw_queue_t;
raw_queue_t m_queue;
std::condition_variable m_cond;
std::mutex m_mutex;
void push(T const& obj)
{
{
std::unique_lock<std::mutex> lock(m_mutex);
m_queue.push_back(obj);
}
m_cond.notify_one();
}
T pop()
{
T front;
{
std::unique_lock<std::mutex> lock(m_mutex);
while (! m_queue.size()) m_cond.wait(lock);
front = m_queue.front();
m_queue.pop_front();
}
return front;
}
};
typedef queue<unsigned int> string_queue_t;
#define CONSUMERS 5
#define N 1000
void producer(std::mutex& std_out_mtx, string_queue_t& queue)
{
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("producer::queue::(%p) - enter\n", (void*)&queue);
}
for (unsigned int i = 0; i < N; ++i)
{
queue.push(i + 1);
std::this_thread::yield(); // just for some spice
}
for (unsigned int i = 0; i < CONSUMERS; ++i)
{
queue.push(0);
std::this_thread::yield(); // just for some spice
}
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("producer::queue::(%p) - exit\n", (void*)&queue);
}
}
void consumer(unsigned int id, std::mutex& std_out_mtx, string_queue_t&
queue)
{
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("consumer(%u)::queue::(%p) - enter\n", id,
(void*)&queue);
}
unsigned int prev = 0;
for (;;)
{
unsigned int msg = queue.pop();
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("consumer(%u)::msg::(%u)\n", id, msg);
}
if (msg == 0) break;
assert(msg > prev); // validate fifo nature
prev = msg;
}
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("consumer::queue::(%p) - exit\n", (void*)&queue);
}
}
int main(void)
{
{
string_queue_t queue;
std::mutex std_out_mutex;
std::thread consumers[CONSUMERS];
for (unsigned int i = 0; i < CONSUMERS; ++i)
{
consumers[i] = std::thread(
consumer,
i,
std::ref(std_out_mutex),
std::ref(queue)
);
}
std::thread producer_thread(
producer,
std::ref(std_out_mutex),
std::ref(queue)
);
producer_thread.join();
for (unsigned int i = 0; i < CONSUMERS; ++i)
{
consumers[i].join();
}
}
std::printf("\nComplete, hit <ENTER> to exit...\n");
std::fflush(stdout);
std::getchar();
return 0;
}
_________________________________________
Any thoughts?
Can anybody run this pile? ;^o
now, lets focus on this simple construct:
A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
deque. This queue is actually multi-producer/consumer, but the test
example code uses a single producer. Also, it uses a special mutex to
make sure calls to printf are thread-safe! ;^)
http://pastebin.com/raw/GA9pJvKN
(pastebin link without ads! ;^)
<code>
_________________________________________
#include <cstdio>
#include <deque>
#include <condition_variable>
#include <mutex>
#include <memory>
#include <thread>
#include <algorithm>
#include <cassert>
template<typename T>
struct queue
{
typedef std::deque<T> raw_queue_t;
raw_queue_t m_queue;
std::condition_variable m_cond;
std::mutex m_mutex;
void push(T const& obj)
{
{
std::unique_lock<std::mutex> lock(m_mutex);
m_queue.push_back(obj);
}
m_cond.notify_one();
}
T pop()
{
T front;
{
std::unique_lock<std::mutex> lock(m_mutex);
while (! m_queue.size()) m_cond.wait(lock);
front = m_queue.front();
m_queue.pop_front();
}
return front;
}
};
typedef queue<unsigned int> string_queue_t;
#define CONSUMERS 5
#define N 1000
void producer(std::mutex& std_out_mtx, string_queue_t& queue)
{
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("producer::queue::(%p) - enter\n", (void*)&queue);
}
for (unsigned int i = 0; i < N; ++i)
{
queue.push(i + 1);
std::this_thread::yield(); // just for some spice
}
for (unsigned int i = 0; i < CONSUMERS; ++i)
{
queue.push(0);
std::this_thread::yield(); // just for some spice
}
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("producer::queue::(%p) - exit\n", (void*)&queue);
}
}
void consumer(unsigned int id, std::mutex& std_out_mtx, string_queue_t&
queue)
{
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("consumer(%u)::queue::(%p) - enter\n", id,
(void*)&queue);
}
unsigned int prev = 0;
for (;;)
{
unsigned int msg = queue.pop();
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("consumer(%u)::msg::(%u)\n", id, msg);
}
if (msg == 0) break;
assert(msg > prev); // validate fifo nature
prev = msg;
}
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("consumer::queue::(%p) - exit\n", (void*)&queue);
}
}
int main(void)
{
{
string_queue_t queue;
std::mutex std_out_mutex;
std::thread consumers[CONSUMERS];
for (unsigned int i = 0; i < CONSUMERS; ++i)
{
consumers[i] = std::thread(
consumer,
i,
std::ref(std_out_mutex),
std::ref(queue)
);
}
std::thread producer_thread(
producer,
std::ref(std_out_mutex),
std::ref(queue)
);
producer_thread.join();
for (unsigned int i = 0; i < CONSUMERS; ++i)
{
consumers[i].join();
}
}
std::printf("\nComplete, hit <ENTER> to exit...\n");
std::fflush(stdout);
std::getchar();
return 0;
}
_________________________________________
Any thoughts?
Can anybody run this pile? ;^o
Alf P. Steinbach
Mar 20, 2017, 12:07:38 AM3/20/17
to
detects the executable from Visual C++ as “Trojan: Win32/Fuery.B!cl”…
:)
Cheers!,
- Alf
Alf P. Steinbach
Mar 20, 2017, 1:37:42 AM3/20/17
to
On 20-Mar-17 1:42 AM, Chris M. Thomasson wrote:
> This queue can be spiced up with exotic C++ atomics and such, but for
> now, lets focus on this simple construct:
>
> A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
> deque. This queue is actually multi-producer/consumer, but the test
> example code uses a single producer. Also, it uses a special mutex to
> make sure calls to printf are thread-safe! ;^)
>
> http://pastebin.com/raw/GA9pJvKN
> (pastebin link without ads! ;^)
>
[snip code]
> now, lets focus on this simple construct:
>
> A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
> deque. This queue is actually multi-producer/consumer, but the test
> example code uses a single producer. Also, it uses a special mutex to
> make sure calls to printf are thread-safe! ;^)
>
> http://pastebin.com/raw/GA9pJvKN
> (pastebin link without ads! ;^)
>
I re-expressed the code in the current Expressive C++ dialect (very
experimental and subject to change at any whim of mine), as now
partially documented at
<url: https://github.com/alf-p-steinbach/Expressive-Cpp/>
Dealing with your code prompted me to define $with and $with_var
statements, used below.
The code got shorter and IMHO a little more clear.
<code>
#include <stdio.h>
#include <deque>
#include <condition_variable>
#include <mutex>
#include <memory>
#include <thread>
#include <algorithm>
#include <assert.h>
#include <condition_variable>
#include <mutex>
#include <memory>
#include <thread>
#include <algorithm>
using namespace std;
template< class T >
class Queue_
{
private:
deque<T> m_queue;
condition_variable m_cond;
mutex m_mutex;
public:
$p push( ref_<const T> obj )
{
$with( unique_lock<mutex>( m_mutex ) ) m_queue.push_back(obj);
m_cond.notify_one();
}
$f pop() -> T
{
T front;
$with_var( lock, unique_lock<mutex>( m_mutex ) )
{
while( m_queue.size() == 0 ) m_cond.wait( lock );
front = m_queue.front();
m_queue.pop_front();
}
return front;
}
};
using String_queue = Queue_<unsigned int>;
m_queue.pop_front();
}
return front;
}
};
const int n_consumers = 5;
const int N = 1000;
$p producer(
ref_<mutex> std_out_mtx,
ref_<String_queue> queue
)
{
$with( unique_lock<mutex>( std_out_mtx ) )
printf("producer::queue::(%p) - enter\n", (void*)&queue);
for( $each i $in up_to( N ) )
{
queue.push( i + 1 );
this_thread::yield(); // just for some spice
}
for( $n_times( n_consumers ) )
}
{
queue.push( 0 );
this_thread::yield(); // just for some spice
}
$with( unique_lock<mutex>( std_out_mtx ) )
}
printf("producer::queue::(%p) - exit\n", (void*)&queue);
}
$p consumer(
}
const unsigned id,
ref_<mutex> std_out_mtx,
ref_<String_queue> queue
)
{
$with( unique_lock<mutex>( std_out_mtx ) )
printf("consumer(%u)::queue::(%p) - enter\n", id, (void*)&queue);
unsigned prev = 0;
$loop
{
const unsigned msg = queue.pop();
$with( unique_lock<mutex>( std_out_mtx ) )
printf("consumer(%u)::msg::(%u)\n", id, msg);
if( msg == 0 ) break;
assert( msg > prev ); // validate fifo nature
if( msg == 0 ) break;
prev = msg;
}
$with( unique_lock<mutex>( std_out_mtx ) )
printf("consumer::queue::(%p) - exit\n", (void*)&queue);
}
$just
}
{
String_queue queue;
mutex std_out_mutex;
raw_array_of_<n_consumers, thread> consumers;
for( $each it $in enumerated( consumers ) )
{
it.item() = thread(
consumer,
it.index(),
ref( std_out_mutex ),
ref( queue )
);
}
thread producer_thread(
producer,
ref( std_out_mutex ),
ref( queue )
);
producer_thread.join();
for( $each_object t $in consumers ) { t.join(); }
}
</code>
Cheers!,
- Alf
Bonita Montero
Mar 20, 2017, 5:32:44 AM3/20/17
to
Your queue lacks a pop() with a timeout - like the ConcurrentLinkedQueue
in Java.
--
http://facebook.com/bonita.montero/
in Java.
--
http://facebook.com/bonita.montero/
Chris Vine
Mar 20, 2017, 9:13:53 AM3/20/17
to
On Sun, 19 Mar 2017 17:42:13 -0700
"Chris M. Thomasson" <inv...@invalid.invalid> wrote:
> This queue can be spiced up with exotic C++ atomics and such, but for
> now, lets focus on this simple construct:
>
> A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
> deque. This queue is actually multi-producer/consumer, but the test
> example code uses a single producer. Also, it uses a special mutex to
> make sure calls to printf are thread-safe! ;^)
>
> http://pastebin.com/raw/GA9pJvKN
For a generic thread safe queue using the standard containers, I would
"Chris M. Thomasson" <inv...@invalid.invalid> wrote:
> This queue can be spiced up with exotic C++ atomics and such, but for
> now, lets focus on this simple construct:
>
> A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
> deque. This queue is actually multi-producer/consumer, but the test
> example code uses a single producer. Also, it uses a special mutex to
> make sure calls to printf are thread-safe! ;^)
>
> http://pastebin.com/raw/GA9pJvKN
generally use a list rather than a deque and splice the new item in
when pushing. This means that if T has a copy constructor which
allocates, the allocation takes place outside the queue mutex so
substantially reducing contention (all that is done under the mutex is
to splice, which only swaps some pointers). I say "generic" because if
you know T will be a fundamental type or an aggregate of fundamental
types, a deque would be better.
Doing a similar splice operation in the pop() method to minimize
contention does however mean sacrificing strong exception safety if the
queue item type's move assignment operator (or if it has none, its
copy assignment operator) might throw. So it is a matter of design
whether you want to de-queue using splicing also, or offer that as an
option.
Apropos of strong exception safety, your pop() method's strong
exception safety relies on RVO. That is OK I guess with C++17 which has
mandatory RVO (technically I don't think that the standard guarantees
that std::deque::pop_front() does not throw, but it seems inconceivable
that it would if the queue item's destructor does not throw). In
earlier times strong exception safety would have been dealt with by
pop() taking a T& out parameter so the popped object is not copied or
moved twice.
You might well want rate-limiting on a queue of this kind to prevent
producers overrunning consumers. That introduces all sorts of other
trade-offs.
Chris
Chris Vine
Mar 20, 2017, 10:45:20 AM3/20/17
to
On Mon, 20 Mar 2017 13:13:37 +0000
Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
[snip]
required by C++17 for named return values of this kind:
"In a return statement in a function with a class return type, when
the expression is the name of a non-volatile automatic object (other
than a function parameter or a variable introduced by the
exception-declaration of a handler (15.3)) with the same type
(ignoring cv-qualification) as the function return type, the
copy/move operation CAN be omitted by constructing the automatic
object directly into the function call’s return object" (my emphasis)
"Copy elision is required where an expression is evaluated in a
context requiring a constant expression (5.20) and in constant
initialization (3.6.2). [Note: Copy elision might not be performed
if the same expression is evaluated in another context. — end note]"
gcc-6.3 does in fact optimize on your code, so providing strong
exception safety. I do not have any older compilers to test at the
moment but out of interest I will try at the end of the week when I
will have some of the gcc-4.* versions available to me. I suspect that
the mutex release before the return statement may inhibit it in some
previous compilers.
So I would be inclined to use an out parameter here.
Chris
Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
[snip]
> Apropos of strong exception safety, your pop() method's strong
> exception safety relies on RVO. That is OK I guess with C++17 which
> has mandatory RVO (technically I don't think that the standard
> guarantees that std::deque::pop_front() does not throw, but it seems
> inconceivable that it would if the queue item's destructor does not
> throw). In earlier times strong exception safety would have been
> dealt with by pop() taking a T& out parameter so the popped object is
> not copied or moved twice.
On looking at N4640 (§12.8.3), I am not now convinced that RVO is
> exception safety relies on RVO. That is OK I guess with C++17 which
> has mandatory RVO (technically I don't think that the standard
> guarantees that std::deque::pop_front() does not throw, but it seems
> inconceivable that it would if the queue item's destructor does not
> throw). In earlier times strong exception safety would have been
> dealt with by pop() taking a T& out parameter so the popped object is
> not copied or moved twice.
required by C++17 for named return values of this kind:
"In a return statement in a function with a class return type, when
the expression is the name of a non-volatile automatic object (other
than a function parameter or a variable introduced by the
exception-declaration of a handler (15.3)) with the same type
(ignoring cv-qualification) as the function return type, the
copy/move operation CAN be omitted by constructing the automatic
object directly into the function call’s return object" (my emphasis)
"Copy elision is required where an expression is evaluated in a
context requiring a constant expression (5.20) and in constant
initialization (3.6.2). [Note: Copy elision might not be performed
if the same expression is evaluated in another context. — end note]"
gcc-6.3 does in fact optimize on your code, so providing strong
exception safety. I do not have any older compilers to test at the
moment but out of interest I will try at the end of the week when I
will have some of the gcc-4.* versions available to me. I suspect that
the mutex release before the return statement may inhibit it in some
previous compilers.
So I would be inclined to use an out parameter here.
Chris
Chris M. Thomasson
Mar 20, 2017, 3:37:19 PM3/20/17
to
On 3/19/2017 9:07 PM, Alf P. Steinbach wrote:
> On 20-Mar-17 1:42 AM, Chris M. Thomasson wrote:
>> This queue can be spiced up with exotic C++ atomics and such, but for
>> now, lets focus on this simple construct:
>>
>> A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
>> deque. This queue is actually multi-producer/consumer, but the test
>> example code uses a single producer. Also, it uses a special mutex to
>> make sure calls to printf are thread-safe! ;^)
>>
>> http://pastebin.com/raw/GA9pJvKN
>> (pastebin link without ads! ;^)
>>
>> <code>
>> _________________________________________
[...]
> On 20-Mar-17 1:42 AM, Chris M. Thomasson wrote:
>> This queue can be spiced up with exotic C++ atomics and such, but for
>> now, lets focus on this simple construct:
>>
>> A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
>> deque. This queue is actually multi-producer/consumer, but the test
>> example code uses a single producer. Also, it uses a special mutex to
>> make sure calls to printf are thread-safe! ;^)
>>
>> http://pastebin.com/raw/GA9pJvKN
>> (pastebin link without ads! ;^)
>>
>> <code>
>> _________________________________________
>> _________________________________________
>>
>>
>> Any thoughts?
>>
>> Can anybody run this pile? ;^o
>
> It works with MinGW g++ 6.3.0 and Visual C++ 2017, but Windows Defender
> detects the executable from Visual C++ as “Trojan: Win32/Fuery.B!cl”…
>
> :)
First of all thank you for giving it a go Alf. :^)
>>
>>
>> Any thoughts?
>>
>> Can anybody run this pile? ;^o
>
> It works with MinGW g++ 6.3.0 and Visual C++ 2017, but Windows Defender
> detects the executable from Visual C++ as “Trojan: Win32/Fuery.B!cl”…
>
> :)
However, your comment has me sort on edge here. What exactly is going on
wrt the Windows Defender detection of a God damn virus! WTF!?!?!?!?!
One of the compilers I am using is MSVC 2015 ver:14.0.25424.0 Update 3
under Win10 with most recent updates.
I have produced many executable's with it, and Windows Defender never
barfed up a warning. Are you sort of trying to say that MSVC 2017
injects viral code into its compiled exe's?
Confused, and worried here Alf!
;^o
Chris M. Thomasson
Mar 20, 2017, 3:41:23 PM3/20/17
to
On 3/19/2017 10:37 PM, Alf P. Steinbach wrote:
> On 20-Mar-17 1:42 AM, Chris M. Thomasson wrote:
>> This queue can be spiced up with exotic C++ atomics and such, but for
>> now, lets focus on this simple construct:
>>
>> A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
>> deque. This queue is actually multi-producer/consumer, but the test
>> example code uses a single producer. Also, it uses a special mutex to
>> make sure calls to printf are thread-safe! ;^)
>>
>> http://pastebin.com/raw/GA9pJvKN
>> (pastebin link without ads! ;^)
>>
>
> [snip code]
>
> I re-expressed the code in the current Expressive C++ dialect (very
> experimental and subject to change at any whim of mine), as now
> partially documented at
>
> <url: https://github.com/alf-p-steinbach/Expressive-Cpp/>
>
> Dealing with your code prompted me to define $with and $with_var
> statements, used below.
>
> The code got shorter and IMHO a little more clear.
[...]
> On 20-Mar-17 1:42 AM, Chris M. Thomasson wrote:
>> This queue can be spiced up with exotic C++ atomics and such, but for
>> now, lets focus on this simple construct:
>>
>> A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
>> deque. This queue is actually multi-producer/consumer, but the test
>> example code uses a single producer. Also, it uses a special mutex to
>> make sure calls to printf are thread-safe! ;^)
>>
>> http://pastebin.com/raw/GA9pJvKN
>> (pastebin link without ads! ;^)
>>
>
> [snip code]
>
> I re-expressed the code in the current Expressive C++ dialect (very
> experimental and subject to change at any whim of mine), as now
> partially documented at
>
> <url: https://github.com/alf-p-steinbach/Expressive-Cpp/>
>
> Dealing with your code prompted me to define $with and $with_var
> statements, used below.
>
> The code got shorter and IMHO a little more clear.
I see what you are doing here with $with and $with_var. I have to admit
that it does seem like a sort of "different" language. IIRC, I used some
macros back in the day wrt trying to automate for loops a bit.
;^)
Chris M. Thomasson
Mar 20, 2017, 3:44:39 PM3/20/17
to
On 3/20/2017 2:32 AM, Bonita Montero wrote:
> Your queue lacks a pop() with a timeout - like the ConcurrentLinkedQueue
> in Java.
>
Yes it does: Also, it lacks a try_pop()! FWIW, I basically quickly
> Your queue lacks a pop() with a timeout - like the ConcurrentLinkedQueue
> in Java.
>
created this for Kushal Bhattacharya in the following thread:
https://groups.google.com/d/topic/comp.lang.c++/yrgAm7Cf1QY/discussion
as an example of how one can use a deque from multiple threads.
Chris M. Thomasson
Mar 20, 2017, 4:33:20 PM3/20/17
to
On 3/20/2017 6:13 AM, Chris Vine wrote:
> On Sun, 19 Mar 2017 17:42:13 -0700
> "Chris M. Thomasson" <inv...@invalid.invalid> wrote:
>> This queue can be spiced up with exotic C++ atomics and such, but for
>> now, lets focus on this simple construct:
>>
>> A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
>> deque. This queue is actually multi-producer/consumer, but the test
>> example code uses a single producer. Also, it uses a special mutex to
>> make sure calls to printf are thread-safe! ;^)
>>
>> http://pastebin.com/raw/GA9pJvKN
>
> For a generic thread safe queue using the standard containers, I would
> generally use a list rather than a deque and splice the new item in
> when pushing. This means that if T has a copy constructor which
> allocates, the allocation takes place outside the queue mutex so
> substantially reducing contention (all that is done under the mutex is
> to splice, which only swaps some pointers). I say "generic" because if
> you know T will be a fundamental type or an aggregate of fundamental
> types, a deque would be better.
I like how you basically covered both bases here. Using a list is fine.
> On Sun, 19 Mar 2017 17:42:13 -0700
> "Chris M. Thomasson" <inv...@invalid.invalid> wrote:
>> This queue can be spiced up with exotic C++ atomics and such, but for
>> now, lets focus on this simple construct:
>>
>> A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
>> deque. This queue is actually multi-producer/consumer, but the test
>> example code uses a single producer. Also, it uses a special mutex to
>> make sure calls to printf are thread-safe! ;^)
>>
>> http://pastebin.com/raw/GA9pJvKN
>
> For a generic thread safe queue using the standard containers, I would
> generally use a list rather than a deque and splice the new item in
> when pushing. This means that if T has a copy constructor which
> allocates, the allocation takes place outside the queue mutex so
> substantially reducing contention (all that is done under the mutex is
> to splice, which only swaps some pointers). I say "generic" because if
> you know T will be a fundamental type or an aggregate of fundamental
> types, a deque would be better.
Separating object creation from any synchronization is very important.
Object init should be private and complete, before the execution of any
release-style membar. The release membar should be completed before any
aspect of the the object makes itself visible to any potential reader
threads.
Fwiw, an intrusive queue can be a single pointer overhead in a user
item, and we need head and tail pointers in the queue structure itself.
<general layout>
struct intruder_node // ;^)
{
node* m_next;
};
struct queue
{
intruder_node* m_head;
intruder_node* m_tail;
// [...]
};
struct USER_DATA
{
intruder_node m_intrusion_node;
// [...] user data...
};
[...]
> You might well want rate-limiting on a queue of this kind to prevent
> producers overrunning consumers. That introduces all sorts of other
> trade-offs.
I need more time to read your detailed response and properly respond
> producers overrunning consumers. That introduces all sorts of other
> trade-offs.
here Chris. Thank you for posting. Will get back later on today.
I am hoping we can talk a little shop about a restricted "lock-free"
version of this lock-based construct. Restricted in the sense that I am
going to post a simple lock-free version of this code that takes
advantage of the single producer/multi consumer nature of the "test code
itself". Since C++ is std now wrt atomic ops, membars, and a lot of that
fancy dandy stuff.
For some reason, I want to focus all my future posts to this group on
C++ -> and what it can offer wrt multi-threading, good and bad...
Should I link to comp.programming.threads? Its an infested rat nest now. ;^o
Gotta go.
Alf P. Steinbach
Mar 20, 2017, 7:44:00 PM3/20/17
to
On 20-Mar-17 2:13 PM, Chris Vine wrote:
> On Sun, 19 Mar 2017 17:42:13 -0700
> "Chris M. Thomasson" <inv...@invalid.invalid> wrote:
>> This queue can be spiced up with exotic C++ atomics and such, but for
>> now, lets focus on this simple construct:
>>
>> A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
>> deque. This queue is actually multi-producer/consumer, but the test
>> example code uses a single producer. Also, it uses a special mutex to
>> make sure calls to printf are thread-safe! ;^)
>>
>> http://pastebin.com/raw/GA9pJvKN
>
> For a generic thread safe queue using the standard containers, I would
> generally use a list rather than a deque and splice the new item in
> when pushing. This means that if T has a copy constructor which
> allocates, the allocation takes place outside the queue mutex so
> substantially reducing contention (all that is done under the mutex is
> to splice, which only swaps some pointers). I say "generic" because if
> you know T will be a fundamental type or an aggregate of fundamental
> types, a deque would be better.
That's an interesting advantage of `std::list`.
> On Sun, 19 Mar 2017 17:42:13 -0700
> "Chris M. Thomasson" <inv...@invalid.invalid> wrote:
>> This queue can be spiced up with exotic C++ atomics and such, but for
>> now, lets focus on this simple construct:
>>
>> A simple fifo thread-safe queue, based on mutexs, condvars, and a c++
>> deque. This queue is actually multi-producer/consumer, but the test
>> example code uses a single producer. Also, it uses a special mutex to
>> make sure calls to printf are thread-safe! ;^)
>>
>> http://pastebin.com/raw/GA9pJvKN
>
> For a generic thread safe queue using the standard containers, I would
> generally use a list rather than a deque and splice the new item in
> when pushing. This means that if T has a copy constructor which
> allocates, the allocation takes place outside the queue mutex so
> substantially reducing contention (all that is done under the mutex is
> to splice, which only swaps some pointers). I say "generic" because if
> you know T will be a fundamental type or an aggregate of fundamental
> types, a deque would be better.
I was sure that no practically relevant advantage was left after C++11.
> Doing a similar splice operation in the pop() method to minimize
> contention does however mean sacrificing strong exception safety if the
> queue item type's move assignment operator (or if it has none, its
> copy assignment operator) might throw. So it is a matter of design
> whether you want to de-queue using splicing also, or offer that as an
> option.
item type with possibly throwing move operation, allows it and then
doesn't offer any guarantee.
Let's define the strong exception guarantee for a pop-like operation,
whether it returns the item via function result or as out-argument, as
* either client code has a logical copy of the former front item, and
the front of the queue has been popped, or
* an exception was thrown and the queue is unchanged.
The C++03 standard library sought to /avoid/ providing this guarantee by
separating the value copying, `front()`, from the actual popping,
`pop_front()`. With no combined operation the queue itself was exception
safe, providing the strong guarantee for each of its operations. And by
just being somewhat awkward, with a separate `pop_front()` call after
acquiring the value, the client code was safe.
So the question is, how can that after-copy call be automated?
A natural way would be via a destructor. But doing that directly would
rely on detecting whether an exception was thrown by the (logical) copying.
Given that a combined pop operation can be called during a stack
unwinding, the only way I can think of to detect a copy exception is to
return not the value/object itself, but a double indirection, which
really complicates things relative to Chris M.thomasson's example:
<code>
#include <cstdio>
#include <deque>
#include <condition_variable>
#include <mutex>
#include <memory>
#include <thread>
#include <utility> // std::forward, std::move
#include <deque>
#include <condition_variable>
#include <mutex>
#include <memory>
#include <thread>
#include <algorithm>
#include <cassert>
template< class Item, class Queue >
class Queue_popper_;
template< class Item, class Queue_popper >
class Queue_front_item_
{
template< class I, class Q > friend class Queue_popper_;
private:
Queue_popper* p_popper_;
Queue_front_item_( Queue_front_item_ const& ) = delete;
public:
Item item;
~Queue_front_item_()
{ p_popper_->on_object_destroyed(); }
Queue_front_item_( Queue_front_item_&& other )
: p_popper_( other.p_popper_ )
, item{ std::move( other.item ) }
{ p_popper_->on_object_created(); }
private:
template< class... Args >
Queue_front_item_( Queue_popper& popper, Args&&... args )
: p_popper_{ &popper }
, item{ std::forward<Args>( args )... }
{ p_popper_->on_object_created(); }
};
template< class Item, class Queue >
class Queue_popper_
{
private:
using Lock = std::unique_lock<std::mutex>;
Queue* p_queue_ = nullptr;
int n_item_calls_ = 0;
int n_created_objects_ = 0;
Lock lock_;
Queue_popper_( Queue_popper_ const& ) = delete;
public:
void on_object_created() { ++n_created_objects_; }
void on_object_destroyed() { --n_created_objects_; }
auto item()
-> Queue_front_item_<Item, Queue_popper_>
{
assert( n_item_calls_ == 0 );
++n_item_calls_;
if( noexcept( Item{ std::move( p_queue_->front() ) } ) )
{
return { *this, std::move( p_queue_->front() ) };
}
else
{
return { *this, p_queue_->front() };
}
}
~Queue_popper_()
{
assert( 0 <= n_created_objects_ and n_created_objects_ <= 1 );
if( n_item_calls_ == 0 or n_created_objects_ == 1 )
{
p_queue_->pop_front();
}
}
Queue_popper_( Queue& q, Lock&& lock )
: p_queue_{ &q }
, lock_( move( lock ) )
{}
Queue_popper_( Queue_popper_&& other ) noexcept
: p_queue_{ exchange( nullptr, other.p_queue_ ) }
, n_item_calls_{ exchange( 0, other.n_item_calls_ ) }
, n_created_objects_{ exchange( 0, other.n_created_objects_ ) }
, lock_{ move( other.lock_ ) }
{}
};
template<typename T>
struct queue
{
typedef std::deque<T> raw_queue_t;
raw_queue_t m_queue;
std::condition_variable m_cond;
std::mutex m_mutex;
void push(T const& obj)
{
{
std::unique_lock<std::mutex> lock(m_mutex);
m_queue.push_back(obj);
}
m_cond.notify_one();
}
-> Queue_popper_<T, std::deque<T>>
{
std::unique_lock<std::mutex> lock(m_mutex);
while (! m_queue.size()) m_cond.wait(lock);
return { m_queue, move( lock ) };
std::unique_lock<std::mutex> lock(m_mutex);
while (! m_queue.size()) m_cond.wait(lock);
}
};
typedef queue<unsigned int> string_queue_t;
#define CONSUMERS 5
#define N 1000
void producer(std::mutex& std_out_mtx, string_queue_t& queue)
{
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("producer::queue::(%p) - enter\n", (void*)&queue);
}
for (unsigned int i = 0; i < N; ++i)
{
queue.push(i + 1);
std::this_thread::yield(); // just for some spice
}
for (unsigned int i = 0; i < CONSUMERS; ++i)
{
queue.push(0);
std::this_thread::yield(); // just for some spice
}
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("producer::queue::(%p) - exit\n", (void*)&queue);
}
}
void consumer(unsigned int id, std::mutex& std_out_mtx, string_queue_t&
queue)
{
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("consumer(%u)::queue::(%p) - enter\n", id,
(void*)&queue);
}
unsigned int prev = 0;
for (;;)
{
auto const msg = queue.pop().item();
};
typedef queue<unsigned int> string_queue_t;
#define CONSUMERS 5
#define N 1000
void producer(std::mutex& std_out_mtx, string_queue_t& queue)
{
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("producer::queue::(%p) - enter\n", (void*)&queue);
}
for (unsigned int i = 0; i < N; ++i)
{
queue.push(i + 1);
std::this_thread::yield(); // just for some spice
}
for (unsigned int i = 0; i < CONSUMERS; ++i)
{
queue.push(0);
std::this_thread::yield(); // just for some spice
}
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("producer::queue::(%p) - exit\n", (void*)&queue);
}
}
void consumer(unsigned int id, std::mutex& std_out_mtx, string_queue_t&
queue)
{
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("consumer(%u)::queue::(%p) - enter\n", id,
(void*)&queue);
}
unsigned int prev = 0;
for (;;)
{
{
std::unique_lock<std::mutex> lock(std_out_mtx);
}
if (msg.item == 0) break;
assert(msg.item > prev); // validate fifo nature
prev = msg.item;
}
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("consumer::queue::(%p) - exit\n", (void*)&queue);
}
}
int main()
{
std::unique_lock<std::mutex> lock(std_out_mtx);
std::printf("consumer::queue::(%p) - exit\n", (void*)&queue);
}
}
{
string_queue_t queue;
std::mutex std_out_mutex;
std::thread consumers[CONSUMERS];
for (unsigned int i = 0; i < CONSUMERS; ++i)
{
consumers[i] = std::thread(
consumer,
i,
std::ref(std_out_mutex),
std::ref(queue)
);
}
std::thread producer_thread(
producer,
std::ref(std_out_mutex),
std::ref(queue)
);
producer_thread.join();
for (unsigned int i = 0; i < CONSUMERS; ++i)
{
consumers[i].join();
}
}
</code>
string_queue_t queue;
std::mutex std_out_mutex;
std::thread consumers[CONSUMERS];
for (unsigned int i = 0; i < CONSUMERS; ++i)
{
consumers[i] = std::thread(
consumer,
i,
std::ref(std_out_mutex),
std::ref(queue)
);
}
std::thread producer_thread(
producer,
std::ref(std_out_mutex),
std::ref(queue)
);
producer_thread.join();
for (unsigned int i = 0; i < CONSUMERS; ++i)
{
consumers[i].join();
}
}
I'm not even entirely sure that that strong exception guarantee logic is
correct, but I've verified that this
modified-to-be-safe-for-general-item-type version produces exactly as
many bytes of output as original.
> Apropos of strong exception safety, your pop() method's strong
> exception safety relies on RVO. That is OK I guess with C++17 which has
> mandatory RVO (technically I don't think that the standard guarantees
> that std::deque::pop_front() does not throw, but it seems inconceivable
> that it would if the queue item's destructor does not throw). In
> earlier times strong exception safety would have been dealt with by
> pop() taking a T& out parameter so the popped object is not copied or
> moved twice.
on the item type will be no-throwing.
Not that it necessarily actually moves, but just that it doesn't throw.
> You might well want rate-limiting on a queue of this kind to prevent
> producers overrunning consumers. That introduces all sorts of other
> trade-offs.
- Alf
Alf P. Steinbach
Mar 20, 2017, 7:51:53 PM3/20/17
to
On 21-Mar-17 12:43 AM, Alf P. Steinbach wrote:
>
> I'm not even entirely sure that that strong exception guarantee logic is
> correct, but I've verified that this
> modified-to-be-safe-for-general-item-type version produces exactly as
> many bytes of output as original.
>
Well, just looking at it now that I posted it, I see that this,
>
> I'm not even entirely sure that that strong exception guarantee logic is
> correct, but I've verified that this
> modified-to-be-safe-for-general-item-type version produces exactly as
> many bytes of output as original.
>
~Queue_front_item_()
{ p_popper_->on_object_destroyed(); }
will in general by using a dangling pointer.
So even more complication is needed, that the popper nulls that pointer,
and that the destructor above checks it.
Apparently exception safety for the value-returning pop() is ugly! But
maybe someone has a bright idea. Maybe. :)
Cheers!,
- Alf
Chris Vine
Mar 20, 2017, 9:00:22 PM3/20/17
to
On Tue, 21 Mar 2017 00:43:52 +0100
"Alf P. Steinbach" <alf.p.stein...@gmail.com> wrote:
> On 20-Mar-17 2:13 PM, Chris Vine wrote:
> > On Sun, 19 Mar 2017 17:42:13 -0700
> > "Chris M. Thomasson" <inv...@invalid.invalid> wrote:
> >> This queue can be spiced up with exotic C++ atomics and such, but
> >> for now, lets focus on this simple construct:
> >>
> >> A simple fifo thread-safe queue, based on mutexs, condvars, and a
> >> c++ deque. This queue is actually multi-producer/consumer, but the
> >> test example code uses a single producer. Also, it uses a special
> >> mutex to make sure calls to printf are thread-safe! ;^)
> >>
> >> http://pastebin.com/raw/GA9pJvKN
> >
> > For a generic thread safe queue using the standard containers, I
> > would generally use a list rather than a deque and splice the new
> > item in when pushing. This means that if T has a copy constructor
> > which allocates, the allocation takes place outside the queue mutex
> > so substantially reducing contention (all that is done under the
> > mutex is to splice, which only swaps some pointers). I say
> > "generic" because if you know T will be a fundamental type or an
> > aggregate of fundamental types, a deque would be better.
>
> That's an interesting advantage of `std::list`.
>
> I was sure that no practically relevant advantage was left after
> C++11.
Yes, it is a kind of a poor man's lock free. It isn't strictly lock
"Alf P. Steinbach" <alf.p.stein...@gmail.com> wrote:
> On 20-Mar-17 2:13 PM, Chris Vine wrote:
> > On Sun, 19 Mar 2017 17:42:13 -0700
> > "Chris M. Thomasson" <inv...@invalid.invalid> wrote:
> >> This queue can be spiced up with exotic C++ atomics and such, but
> >> for now, lets focus on this simple construct:
> >>
> >> A simple fifo thread-safe queue, based on mutexs, condvars, and a
> >> c++ deque. This queue is actually multi-producer/consumer, but the
> >> test example code uses a single producer. Also, it uses a special
> >> mutex to make sure calls to printf are thread-safe! ;^)
> >>
> >> http://pastebin.com/raw/GA9pJvKN
> >
> > For a generic thread safe queue using the standard containers, I
> > would generally use a list rather than a deque and splice the new
> > item in when pushing. This means that if T has a copy constructor
> > which allocates, the allocation takes place outside the queue mutex
> > so substantially reducing contention (all that is done under the
> > mutex is to splice, which only swaps some pointers). I say
> > "generic" because if you know T will be a fundamental type or an
> > aggregate of fundamental types, a deque would be better.
>
> That's an interesting advantage of `std::list`.
>
> I was sure that no practically relevant advantage was left after
> C++11.
free (it uses a mutex), but it meets the guarantee of always proceeding,
because it only operates on pointer swaps which can't block except
transiently by contention.
> > Doing a similar splice operation in the pop() method to minimize
> > contention does however mean sacrificing strong exception safety if
> > the queue item type's move assignment operator (or if it has none,
> > its copy assignment operator) might throw. So it is a matter of
> > design whether you want to de-queue using splicing also, or offer
> > that as an option.
>
> Worth noting that std::vector, instead of prohibiting a non-copyable
> item type with possibly throwing move operation, allows it and then
> doesn't offer any guarantee.
not necessarily strong safety - you can lose a queue item but the queue
is left in a valid state.
> Let's define the strong exception guarantee for a pop-like operation,
> whether it returns the item via function result or as out-argument, as
>
> * either client code has a logical copy of the former front item, and
> the front of the queue has been popped, or
> * an exception was thrown and the queue is unchanged.
>
> The C++03 standard library sought to /avoid/ providing this guarantee
> by separating the value copying, `front()`, from the actual popping,
> `pop_front()`. With no combined operation the queue itself was
> exception safe, providing the strong guarantee for each of its
> operations. And by just being somewhat awkward, with a separate
> `pop_front()` call after acquiring the value, the client code was
> safe.
>
> So the question is, how can that after-copy call be automated?
to require a move not to throw, so side-stepping the problem. If that
is not good enough, then I suspect it is back to a pop_front() and so
deallocate defunct queue items under the mutex (not quite as bad as
allocating under the mutex, particularly if a move operation has been
carried out so there is little left to actually deallocate).
[snip]
> > Apropos of strong exception safety, your pop() method's strong
> > exception safety relies on RVO. That is OK I guess with C++17
> > which has mandatory RVO (technically I don't think that the
> > standard guarantees that std::deque::pop_front() does not throw,
> > but it seems inconceivable that it would if the queue item's
> > destructor does not throw). In earlier times strong exception
> > safety would have been dealt with by pop() taking a T& out
> > parameter so the popped object is not copied or moved twice.
>
> I think a more reasonable approach is to /require/ that a move
> operation on the item type will be no-throwing.
>
> Not that it necessarily actually moves, but just that it doesn't
> throw.
I think that is a good approach. The problem though is that if RVO is
> > exception safety relies on RVO. That is OK I guess with C++17
> > which has mandatory RVO (technically I don't think that the
> > standard guarantees that std::deque::pop_front() does not throw,
> > but it seems inconceivable that it would if the queue item's
> > destructor does not throw). In earlier times strong exception
> > safety would have been dealt with by pop() taking a T& out
> > parameter so the popped object is not copied or moved twice.
>
> I think a more reasonable approach is to /require/ that a move
> operation on the item type will be no-throwing.
>
> Not that it necessarily actually moves, but just that it doesn't
> throw.
not carried out you get a copy rather than a move generated by the
return statement. I am quite disappointed to find that C++11 does not
required named object return statements to be optimized away: I thought
the proposal was that they would be. Maybe there were reasons for not
proceeding with that. Having said that, I am not allergic to out
parameters.
Chris
Chris Vine
Mar 20, 2017, 9:06:14 PM3/20/17
to
On Tue, 21 Mar 2017 01:00:08 +0000
Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
> I think that is a good approach. The problem though is that if RVO is
> not carried out you get a copy rather than a move generated by the
> return statement. I am quite disappointed to find that C++11 does not
^^^^^
Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
> I think that is a good approach. The problem though is that if RVO is
> not carried out you get a copy rather than a move generated by the
> return statement. I am quite disappointed to find that C++11 does not
C++17
Chris M. Thomasson
Mar 21, 2017, 12:29:02 AM3/21/17
to
exceptions occurring in the following "out" version of the pop function
of the queue:
____________________________
template<typename T>
struct queue
{
typedef std::deque<T> raw_queue_t;
raw_queue_t m_queue;
std::condition_variable m_cond;
std::mutex m_mutex;
void push(T const& obj)
{
{
std::unique_lock<std::mutex> lock(m_mutex);
m_queue.push_back(obj);
}
m_cond.notify_one();
}
void pop(T& out)
struct queue
{
typedef std::deque<T> raw_queue_t;
raw_queue_t m_queue;
std::condition_variable m_cond;
std::mutex m_mutex;
void push(T const& obj)
{
{
std::unique_lock<std::mutex> lock(m_mutex);
m_queue.push_back(obj);
}
m_cond.notify_one();
}
{
std::unique_lock<std::mutex> lock(m_mutex);
while (!m_queue.size()) m_cond.wait(lock);
out = m_queue.front();
std::unique_lock<std::mutex> lock(m_mutex);
while (!m_queue.size()) m_cond.wait(lock);
m_queue.pop_front();
}
};
____________________________
Much better to me. The calling code can deal with that out parameter in
whatever way it wants to. ;^)
The way it was before, function returning, had this damn "ghost" user
type T out there:
____________________________
T pop()
{
T front; // HELLO? ARE YOU THERE?
{
std::unique_lock<std::mutex> lock(m_mutex);
while (! m_queue.size()) m_cond.wait(lock);
front = m_queue.front();
m_queue.pop_front();
}
return front;
}
____________________________
m_queue.pop_front();
}
return front;
}
I must of had POD's on the mind. Yikes!
Anyway, I thank you all for the most valuable input.
This has to be signal in the NG...
:^)
Chris M. Thomasson
Mar 21, 2017, 12:30:59 AM3/21/17
to
reference to the front of the queue. Not sure if this is Kosher or not.
I guess we can say, if this throws, the out param is undefined, even
thought it references the front of the queue.
Make any sense? Thanks.
> };
> ____________________________
kushal bhattacharya
Mar 21, 2017, 12:53:25 AM3/21/17
to
hi your mechanism is working fine but in my case i am implementing in a totally different scenario
Chris M. Thomasson
Mar 21, 2017, 12:56:23 AM3/21/17
to
On 3/20/2017 9:53 PM, kushal bhattacharya wrote:
> hi your mechanism is working fine but in my case i am implementing in a totally different scenario
How? Are you iterating over the deque in some cases without removing
> hi your mechanism is working fine but in my case i am implementing in a totally different scenario
anything from it? Like reader threads, reader access? Non-mutating access?
We need more details...
kushal bhattacharya
Mar 21, 2017, 1:00:13 AM3/21/17
to
Hi,
First i want to tell you where i am implementing this.
I am implementing it for building the mqtt broker.
So the parsing thread is run according to the packets coming from the client
and accordingly it is pushing information into the queue as a message object.
When the message is available from the queue,it
is pulled out from the queue by the prespawnned transmission threads so in those cases i am popping it out from the dequeue and also in the parser thread when all the acknowledgments are over.
First i want to tell you where i am implementing this.
I am implementing it for building the mqtt broker.
So the parsing thread is run according to the packets coming from the client
and accordingly it is pushing information into the queue as a message object.
When the message is available from the queue,it
is pulled out from the queue by the prespawnned transmission threads so in those cases i am popping it out from the dequeue and also in the parser thread when all the acknowledgments are over.
Alf P. Steinbach
Mar 21, 2017, 1:15:30 AM3/21/17
to
On 21-Mar-17 5:30 AM, Chris M. Thomasson wrote:
>> [snip]
it this throws then the out param does not reference the front of the
queue – it is instead unchanged, if that assignment guarantees that).
Since `m_queue.front()` produces a regular reference, the `=` here
denotes a regular copy assignment, not a move assignment.
And that's great for exception safety, because if T has a copy
assignment that offers the success-or-unchanged-with-exception
guarantee, which Dave Abrahams called “the strong exception guarantee”,
then all that happens if that assignment fails is that the assignment
fails, and execution of pop() is terminated via the exception.
And so this pop() offers the strong exception guarantee contingent on T
having a copy assignment operator with that guarantee.
One cost is the requirement that T must be copy assignable and – for
practical use – default constructible.
Another cost is that the T object in the client code can't be `const`.
• • •
One possible optimization is to use the `noexcept` /operator/ to check
if a move assignment to `T` can throw. And if it cannot, then just use a
move assignment, knowing that the possibly pilfered-for-resources front
of queue object will be removed in the next statement. Like this,
where the check with noexcept does not actually execute the expression:
if( noexcept( out = move( m_queue.front() ) ) )
{
out = move( m_queue.front() ); // Move, pilfering resources.
}
else
{
out = m_queue.front(); // Copy, possible exception.
}
> Make any sense? Thanks.
Yes.
But also see the solution I posted in "One way to get strong exception
guarantee for a multithreaded pop: a Dequeued_ class".
It requires only that T is copy constructible. The main other cost is an
unconventional notation for popping. Namely, not writing
T const item = q.pop(); // Sort of the ideal to strive for!
but
Dequeued_<T> const item{ q }; // Good enough, IMHO. :)
I did not optimize that for noexcept, but it's not difficult to add.
Cheers!,
- Alf
>> [snip]
>> void pop(T& out)
>> {
>> std::unique_lock<std::mutex> lock(m_mutex);
>> while (!m_queue.size()) m_cond.wait(lock);
>> out = m_queue.front();
>> m_queue.pop_front();
>> }
>
>
> If an exception occurs in pop_front, the out param will still hold a
> reference to the front of the queue. Not sure if this is Kosher or not.
> I guess we can say, if this throws, the out param is undefined, even
> thought it references the front of the queue.
The `=` here gives you an assignment, not a reference re-seating (i.e.,
>> {
>> std::unique_lock<std::mutex> lock(m_mutex);
>> while (!m_queue.size()) m_cond.wait(lock);
>> out = m_queue.front();
>> m_queue.pop_front();
>> }
>
>
> If an exception occurs in pop_front, the out param will still hold a
> reference to the front of the queue. Not sure if this is Kosher or not.
> I guess we can say, if this throws, the out param is undefined, even
> thought it references the front of the queue.
it this throws then the out param does not reference the front of the
queue – it is instead unchanged, if that assignment guarantees that).
Since `m_queue.front()` produces a regular reference, the `=` here
denotes a regular copy assignment, not a move assignment.
And that's great for exception safety, because if T has a copy
assignment that offers the success-or-unchanged-with-exception
guarantee, which Dave Abrahams called “the strong exception guarantee”,
then all that happens if that assignment fails is that the assignment
fails, and execution of pop() is terminated via the exception.
And so this pop() offers the strong exception guarantee contingent on T
having a copy assignment operator with that guarantee.
One cost is the requirement that T must be copy assignable and – for
practical use – default constructible.
Another cost is that the T object in the client code can't be `const`.
• • •
One possible optimization is to use the `noexcept` /operator/ to check
if a move assignment to `T` can throw. And if it cannot, then just use a
move assignment, knowing that the possibly pilfered-for-resources front
of queue object will be removed in the next statement. Like this,
where the check with noexcept does not actually execute the expression:
if( noexcept( out = move( m_queue.front() ) ) )
{
out = move( m_queue.front() ); // Move, pilfering resources.
}
else
{
out = m_queue.front(); // Copy, possible exception.
}
> Make any sense? Thanks.
Yes.
But also see the solution I posted in "One way to get strong exception
guarantee for a multithreaded pop: a Dequeued_ class".
It requires only that T is copy constructible. The main other cost is an
unconventional notation for popping. Namely, not writing
T const item = q.pop(); // Sort of the ideal to strive for!
but
Dequeued_<T> const item{ q }; // Good enough, IMHO. :)
I did not optimize that for noexcept, but it's not difficult to add.
Cheers!,
- Alf
Chris Vine
Mar 21, 2017, 6:54:21 AM3/21/17
to
On Mon, 20 Mar 2017 21:30:52 -0700
Yes, this is exactly what I was suggesting you should do.
There are variations on this theme. I would move into 'out':
out = std::move(m_queue.front());
and document that this pop is only strongly exception safe if either the
queue item's move constructor doesn't throw or, if it does, the move is
itself strongly exception safe (it either succeeds or leaves the object
unchanged). Giving this method the same exception safety as the
queue item's move assignment operator, and documenting that, seems
perfectly reasonable to me.
Alf has come up with a more sophisticated version which selects on
whether the move assignment operator is noexcept or not - I didn't
actually know you could do that. But that leaves out the case of a
queue item with a move assignment operator which is strongly exception
safe, and surely most are.
With a list there is the option of a splice, as I have mentioned. This
would only give strong exception safety if the queue item's move
assignment operator does not throw, otherwise it only gives the basic
guarantee. The basic guarantee gives you pretty much all you need for
many purposes, and is all you are going to get out of a lock free queue.
Chris
"Chris M. Thomasson" <inv...@invalid.invalid> wrote:
There are variations on this theme. I would move into 'out':
out = std::move(m_queue.front());
and document that this pop is only strongly exception safe if either the
queue item's move constructor doesn't throw or, if it does, the move is
itself strongly exception safe (it either succeeds or leaves the object
unchanged). Giving this method the same exception safety as the
queue item's move assignment operator, and documenting that, seems
perfectly reasonable to me.
Alf has come up with a more sophisticated version which selects on
whether the move assignment operator is noexcept or not - I didn't
actually know you could do that. But that leaves out the case of a
queue item with a move assignment operator which is strongly exception
safe, and surely most are.
With a list there is the option of a splice, as I have mentioned. This
would only give strong exception safety if the queue item's move
assignment operator does not throw, otherwise it only gives the basic
guarantee. The basic guarantee gives you pretty much all you need for
many purposes, and is all you are going to get out of a lock free queue.
Chris
Chris Vine
Mar 21, 2017, 6:55:57 AM3/21/17
to
On Tue, 21 Mar 2017 10:54:08 +0000
Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
[snip]
move assignment operator
Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
[snip]
> There are variations on this theme. I would move into 'out':
>
> out = std::move(m_queue.front());
>
> and document that this pop is only strongly exception safe if either
> the queue item's move constructor doesn't throw or, if it does, the
^^^^^^^^^^^^^^^^
>
> out = std::move(m_queue.front());
>
> and document that this pop is only strongly exception safe if either
> the queue item's move constructor doesn't throw or, if it does, the
move assignment operator
Chris M. Thomasson
Mar 21, 2017, 3:32:46 PM3/21/17
to
On 3/20/2017 10:15 PM, Alf P. Steinbach wrote:
> On 21-Mar-17 5:30 AM, Chris M. Thomasson wrote:
>>> [snip]
>>> void pop(T& out)
>>> {
>>> std::unique_lock<std::mutex> lock(m_mutex);
>>> while (!m_queue.size()) m_cond.wait(lock);
>>> out = m_queue.front();
>>> m_queue.pop_front();
>>> }
>>
>>
>> If an exception occurs in pop_front, the out param will still hold a
>> reference to the front of the queue. Not sure if this is Kosher or not.
>> I guess we can say, if this throws, the out param is undefined, even
>> thought it references the front of the queue.
>
> The `=` here gives you an assignment, not a reference re-seating (i.e.,
> it this throws then the out param does not reference the front of the
> queue – it is instead unchanged, if that assignment guarantees that).
Yikes! My C++ is rusty. Your are correct and I am wrong about the
> On 21-Mar-17 5:30 AM, Chris M. Thomasson wrote:
>>> [snip]
>>> void pop(T& out)
>>> {
>>> std::unique_lock<std::mutex> lock(m_mutex);
>>> while (!m_queue.size()) m_cond.wait(lock);
>>> out = m_queue.front();
>>> m_queue.pop_front();
>>> }
>>
>>
>> If an exception occurs in pop_front, the out param will still hold a
>> reference to the front of the queue. Not sure if this is Kosher or not.
>> I guess we can say, if this throws, the out param is undefined, even
>> thought it references the front of the queue.
>
> The `=` here gives you an assignment, not a reference re-seating (i.e.,
> it this throws then the out param does not reference the front of the
> queue – it is instead unchanged, if that assignment guarantees that).
reference. Also, pop_front does not seem to throw even if the side is
zero, according to:
http://en.cppreference.com/w/cpp/container/deque/pop_front
However, it does seem to fire off an assert saying that the deque was
empty, perhaps because NDEBUG was not defined. It messes things up if
one executes pop_front on an empty deque.
Undefined Behavior Indeed!
> Since `m_queue.front()` produces a regular reference, the `=` here
> denotes a regular copy assignment, not a move assignment.
>
> And that's great for exception safety, because if T has a copy
> assignment that offers the success-or-unchanged-with-exception
> guarantee, which Dave Abrahams called “the strong exception guarantee”,
> then all that happens if that assignment fails is that the assignment
> fails, and execution of pop() is terminated via the exception.
> One possible optimization is to use the `noexcept` /operator/ to check
> if a move assignment to `T` can throw. And if it cannot, then just use a
> move assignment, knowing that the possibly pilfered-for-resources front
> of queue object will be removed in the next statement. Like this,
> where the check with noexcept does not actually execute the expression:
>
> if( noexcept( out = move( m_queue.front() ) ) )
> {
> out = move( m_queue.front() ); // Move, pilfering resources.
> }
> else
> {
> out = m_queue.front(); // Copy, possible exception.
> }
Nice! Thank you for that. Did not know about it until now. Love to learn
> if a move assignment to `T` can throw. And if it cannot, then just use a
> move assignment, knowing that the possibly pilfered-for-resources front
> of queue object will be removed in the next statement. Like this,
> where the check with noexcept does not actually execute the expression:
>
> if( noexcept( out = move( m_queue.front() ) ) )
> {
> out = move( m_queue.front() ); // Move, pilfering resources.
> }
> else
> {
> out = m_queue.front(); // Copy, possible exception.
> }
new things Alf. :^)
>> Make any sense? Thanks.
>
> Yes.
>
> But also see the solution I posted in "One way to get strong exception
> guarantee for a multithreaded pop: a Dequeued_ class".
>
> It requires only that T is copy constructible. The main other cost is an
> unconventional notation for popping. Namely, not writing
>
> T const item = q.pop(); // Sort of the ideal to strive for!
>
> but
>
> Dequeued_<T> const item{ q }; // Good enough, IMHO. :)
>
> I did not optimize that for noexcept, but it's not difficult to add.
C++ modern constructs. My C++ code seems a bit dated, except for using
the new fancy threading constructs, I have not even used the auto
keyword yet in my code! ;^
My exception handling in C++ can be vastly improved. The fact is, that
you, and others have helped me in this thread.
Reading your code using all the new C++ stuff rather heavily, is okay
with me!
Thank you: Alf P. Steinbach
Chris M. Thomasson
Mar 21, 2017, 5:05:38 PM3/21/17
to
>
> and document that this pop is only strongly exception safe if either the
> queue item's move constructor doesn't throw or, if it does, the move is
> itself strongly exception safe (it either succeeds or leaves the object
> unchanged). Giving this method the same exception safety as the
> queue item's move assignment operator, and documenting that, seems
> perfectly reasonable to me.
>
> Alf has come up with a more sophisticated version which selects on
> whether the move assignment operator is noexcept or not - I didn't
> actually know you could do that. But that leaves out the case of a
> queue item with a move assignment operator which is strongly exception
> safe, and surely most are.
>
> With a list there is the option of a splice, as I have mentioned. This
> would only give strong exception safety if the queue item's move
> assignment operator does not throw, otherwise it only gives the basic
> guarantee. The basic guarantee gives you pretty much all you need for
> many purposes, and is all you are going to get out of a lock free queue.
sense that the functions can be marked as nothrow.
Chris Vine
Mar 21, 2017, 8:45:51 PM3/21/17
to
On Tue, 21 Mar 2017 14:05:31 -0700
memory exhaustion, that is nothrow in any implementation, and not
really the context that we were talking about.
"Chris M. Thomasson" <inv...@invalid.invalid> wrote:
[snip]
> > With a list there is the option of a splice, as I have mentioned.
> > This would only give strong exception safety if the queue item's
> > move assignment operator does not throw, otherwise it only gives
> > the basic guarantee. The basic guarantee gives you pretty much all
> > you need for many purposes, and is all you are going to get out of
> > a lock free queue.
>
> Well, certain lock-free queues can be totally exception safe in the
> sense that the functions can be marked as nothrow.
Yes, but then they are queuing pointers to objects. Leaving aside
> > This would only give strong exception safety if the queue item's
> > move assignment operator does not throw, otherwise it only gives
> > the basic guarantee. The basic guarantee gives you pretty much all
> > you need for many purposes, and is all you are going to get out of
> > a lock free queue.
>
> Well, certain lock-free queues can be totally exception safe in the
> sense that the functions can be marked as nothrow.
memory exhaustion, that is nothrow in any implementation, and not
really the context that we were talking about.
Chris M. Thomasson
Mar 21, 2017, 8:49:29 PM3/21/17
to
Chris M. Thomasson
Mar 22, 2017, 6:37:23 PM3/22/17
to
On 3/21/2017 5:45 PM, Chris Vine wrote:
Fwiw, imagine an exception blasting the following pseudo-code of a MPMCQ
(multi-producer multi-producer queue) wrt a copy-assign type of op in
the cell struct wrt the double being used as a totally generic user type
like T:
_______________________________________________
struct cell { uint32_t ver; double state; };
// think of cell.state as a being of type T,
// that can potentially throw shi% all over the place.
// makes one want to restrict this to POD. Humm...
// XADD is atomic fetch-and-add
// LOAD/STORE are simple atomic loads and stores
uint32_t head = 0;
uint32_t tail = 0;
cell cells[N]; // N must be a power of 2
void init() {
// prime the cells...
for (uint32_t i = 0; i < N; ++i) cells[i].ver = i;
}
void producer(double state) {
uint32_t ver = XADD(&head, 1);
cell& c = cells[ver & (N - 1)];
while (LOAD(&c.ver) != ver) backoff();
MB_ACQUIRE()
//*****************************
c.state = state; // Can go BAM wrt exception in T!
MB_RELEASE()
STORE(&c.ver, ver + 1);
}
double consumer() {
uint32_t ver = XADD(&tail, 1);
cell& c = cells[ver & (N - 1)];
while (LOAD(&c.ver) != ver + 1) backoff();
MB_ACQUIRE()
//*****************************
double state = c.state; // Can go BAM wrt exception in T!
// humm, not sure if we need release right here.
// do not think so, need to verify.
MB_RELEASE()
STORE(&c.ver, ver + N);
return state;
}
_______________________________________________
Yikes!
Chris M. Thomasson
Mar 23, 2017, 4:56:25 AM3/23/17
to
On 3/20/2017 6:13 AM, Chris Vine wrote:
> On Sun, 19 Mar 2017 17:42:13 -0700
> "Chris M. Thomasson" <inv...@invalid.invalid> wrote:
>> This queue can be spiced up with exotic C++ atomics and such, but for
>> now, lets focus on this simple construct:
[....]
> "Chris M. Thomasson" <inv...@invalid.invalid> wrote:
>> This queue can be spiced up with exotic C++ atomics and such, but for
>> now, lets focus on this simple construct:
> You might well want rate-limiting on a queue of this kind to prevent
> producers overrunning consumers. That introduces all sorts of other
> trade-offs.
Right. Well, I am thinking of a fun way to do this. We can add some
> producers overrunning consumers. That introduces all sorts of other
> trade-offs.
semaphore logic in the existing condvar-mutex relationship, or get rid
of the condvar for a semaphore. Hummm... Need to think here.
Are you familiar with the following "fast" semaphore logic, membars
aside for a moment, pseudo-code:
_________________________________________
struct fast_sem
{
int count = initial count;
slow_sem_os = os_sempahore with a count of zero;
dec() // wait
{
if (ATOMIC_DEC(&count) < 0) slow_sem_os.dec();
}
inc() // post
{
if (ATOMIC_INC(&count) <=0) slow_sem_os.inc();
}
};
_________________________________________
Pretty compact, and completely doable in std C++. ;^)
Chris Vine
Mar 23, 2017, 10:45:19 AM3/23/17
to
On Thu, 23 Mar 2017 01:56:18 -0700
You could do it using semaphores, but for a queue of this kind
something more prosaic (using components provided by the standard
library) may be more in keeping. There are two common ways of doing
that. First, have producers block on a condition variable when the
queue reaches a given size, in the same way that consumers block when
the size is 0. Such devices are normally described as some form of
buffered channel. A second is to apply throttling to producers when
the queue exceeds a given size, with a delay that increases
non-linearly (say, quadratically or by cubically) once the threshold
has been hit. The second approach seems better for a queue implemented
using a list or deque, where the throttle size may be large (a queue of
this kind could easily take a million items if each item is small
enough, and it doesn't need a hard edge).
I do not think I can get as enthusiastic about this stuff as you are.
The original code you produced with the corrections I mentioned and the
kind of throttling I have described seems good enough to me for most
cases.
something more prosaic (using components provided by the standard
library) may be more in keeping. There are two common ways of doing
that. First, have producers block on a condition variable when the
queue reaches a given size, in the same way that consumers block when
the size is 0. Such devices are normally described as some form of
buffered channel. A second is to apply throttling to producers when
the queue exceeds a given size, with a delay that increases
non-linearly (say, quadratically or by cubically) once the threshold
has been hit. The second approach seems better for a queue implemented
using a list or deque, where the throttle size may be large (a queue of
this kind could easily take a million items if each item is small
enough, and it doesn't need a hard edge).
I do not think I can get as enthusiastic about this stuff as you are.
The original code you produced with the corrections I mentioned and the
kind of throttling I have described seems good enough to me for most
cases.
0 new messages