Re: STL Queue and multithreading
"kickit" <wasinapple@gmail.com> wrote in message
news:94d08a6e-b93f-426f-8e50-ed5907587609@y31g2000vbt.googlegroups.com...
[...]
if you want to one thread to produce and multiple threads to consume
you might have to write your own Queue which takes care of thread
synchronization among producer and consumers using atomic and it's
complex.
FWIW, Dmitriy Vyukov invented a very elegant algorithm that efficiently
solves the single-producer/multiple-consumer (SPMC) queue problem:
http://groups.google.com/group/lock-free/browse_frm/thread/55df71b87acb8201
Hint.. design queue such that it has internally two queues one active
and other standby, active queue will be used by consumers to consume
and producer will always write to standby queue... once written the
producer could switch active <=> standby.. it's difficult to explain
all different problems you might see.. but i have seen this working
with good performance benefits.
IMVHO, that is actually overly complex scheme when compare to the elegance
of Dmitriy's MPSC queue. Also, one can "easily" use the simple
"stack-into-queue" trick; here could be a sample impl in C++0x:
<pseudo-code quickly typed directly in newsreader>
_________________________________________________________
struct node
{
node* m_next;
};
struct stack
{
std::atomic<node*> m_head; // = NULL
void push(node* head, node* tail) throw();
{
tail->m_next = m_head.load(std::memory_order_relaxed);
while (! m_head.compare_exchange_weak(
tail->m_next,
head,
std::memory_order_release));
}
void push(node* head) throw()
{
push(head, head);
}
// returns entire list of nodes in LIFO order
node* flush_lifo() throw()
{
return m_head.exchange(NULL, std::memory_order_acquire);
}
// returns entire list of nodes in FIFO order...
node* flush_fifo() throw()
{
node* lifo = flush_lifo();
if (! lifo) return NULL;
node* fifo = NULL;
// simply reverse the list! ;^)
while (lifo)
{
node* next = lifo->m_next;
lifo->m_next = fifo;
fifo = lifo;
lifo = next;
}
return fifo;
}
};
_________________________________________________________
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]