concurrent linked queue class for C++?
Andrew
then the child and parent thread will need to communicate. If this was
in java I would use ConcurrentLinkedQueue but what to do in C++? I
have googled and searched boost but cannot find anything.
There is a class that would serve in ACE but ACE is huge so I do not
want to introduce ACE to the project. The project is already using
boost and fighting the battle for more boost usage is hard enough.
Does anyone know if such a facility is planned for the upcoming std?
Regards,
Andrew Marlow
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Mathias Gaunard
> I am designing a system where an app will need to spawn a child thread
> then the child and parent thread will need to communicate. If this was
> in java I would use ConcurrentLinkedQueue but what to do in C++? I
> have googled and searched boost but cannot find anything.
There is one in the boost review queue.
Alternatively, there is one in Intel TBB as well.
Robert Kindred
"Andrew" <marlow...@googlemail.com> wrote in message
news:d5cc1f55-9de9-4f77...@u7g2000yqm.googlegroups.com...
>I am designing a system where an app will need to spawn a child thread
> then the child and parent thread will need to communicate. If this was
> in java I would use ConcurrentLinkedQueue but what to do in C++? I
> have googled and searched boost but cannot find anything.
>
> There is a class that would serve in ACE but ACE is huge so I do not
> want to introduce ACE to the project. The project is already using
> boost and fighting the battle for more boost usage is hard enough.
>
> Does anyone know if such a facility is planned for the upcoming std?
The design of the ACE message queue is given in "Pattern-Oriented Software
Architecture" Volume 2 by Schmidt et. al. It is not too hard to code into
your program, provided you have access to a pthreads library.
hth,
Robert Kindred
Anthony Williams
> I am designing a system where an app will need to spawn a child thread
> then the child and parent thread will need to communicate. If this was
> in java I would use ConcurrentLinkedQueue but what to do in C++? I
> have googled and searched boost but cannot find anything.
>
> Does anyone know if such a facility is planned for the upcoming std?
No, this is not planned for C++0x. There is an example implementation of
a queue that uses boost on my blog:
Anthony
--
Author of C++ Concurrency in Action http://www.stdthread.co.uk/book/
just::thread C++0x thread library http://www.stdthread.co.uk
Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk
15 Carrallack Mews, St Just, Cornwall, TR19 7UL, UK. Company No. 5478976
mzdude
> I am designing a system where an app will need to spawn a child thread
> then the child and parent thread will need to communicate. If this was
> in java I would use ConcurrentLinkedQueue but what to do in C++? I
> have googled and searched boost but cannot find anything.
>
> There is a class that would serve in ACE but ACE is huge so I do not
> want to introduce ACE to the project. The project is already using
> boost and fighting the battle for more boost usage is hard enough.
>
> Does anyone know if such a facility is planned for the upcoming std?
>
> Regards,
>
> Andrew Marlow
>
Check out the Intel Threaded Building Blocks. They have
concurrent_hash_map
concurrent_queue
concurrent_vector
We use the concurrent_queue for the producer/consumer. It works well.
Goran Pusic
> I am designing a system where an app will need to spawn a child thread
> then the child and parent thread will need to communicate. If this was
> in java I would use ConcurrentLinkedQueue but what to do in C++? I
> have googled and searched boost but cannot find anything.
>
> There is a class that would serve in ACE but ACE is huge so I do not
> want to introduce ACE to the project. The project is already using
> boost and fighting the battle for more boost usage is hard enough.
>
> Does anyone know if such a facility is planned for the upcoming std?
>
> Regards,
>
> Andrew Marlow
Most obvious candidate (for me): http://www.threadingbuildingblocks.org/
(If I am not mistaken...) Note that it's not a surprise that there's
no standard library support for anything concurrency : up to the very
latest standard, language knew zilch about threading.
Goran.
Andrew
> > There is a class that would serve in ACE but ACE is huge so I do not
> > want to introduce ACE to the project. The project is already using
> > boost and fighting the battle for more boost usage is hard enough.
>
> > Does anyone know if such a facility is planned for the upcoming std?
>
> The design of the ACE message queue is given in "Pattern-Oriented Software
> Architecture" Volume 2 by Schmidt et. al. It is not too hard to code into
> your program, provided you have access to a pthreads library.
I would much rather use a library than code it myself.
I do not have access to the pthreads library. The code is locked into
a Micro$oft environment so some POSIX functions are not available. I
know about the WIN32 port of pthreads which is great, I have used it
before. However, on my current project there would be strong
resistance to using this. The project does use boost so boost threads
would be the only kind of threads that would be accepted.
Andrew
> Andrew <marlow.and...@googlemail.com> writes:
> > I am designing a system where an app will need to spawn a child thread
> > then the child and parent thread will need to communicate. If this was
> > in java I would use ConcurrentLinkedQueue but what to do in C++? I
> > have googled and searched boost but cannot find anything.
>
> > Does anyone know if such a facility is planned for the upcoming std?
>
> No, this is not planned for C++0x.
What a pity. Well, at least I know now.
> There is an example implementation of
> a queue that uses boost on my blog:
>
> http://www.justsoftwaresolutions.co.uk/threading/implementing-a-threa...
>
> Anthony
Wow, this is great, just want I needed, thanks! It's all coming back
to me, thanks to your article. I did something very similar to this,
using condition variables, when I had to solve this problem on Solaris
a couple of years ago.
-Andrew Marlow
--
Branimir Maksimovic
> I am designing a system where an app will need to spawn a child thread
> then the child and parent thread will need to communicate. If this was
> in java I would use ConcurrentLinkedQueue but what to do in C++? I
> have googled and searched boost but cannot find anything.
>
> There is a class that would serve in ACE but ACE is huge so I do not
> want to introduce ACE to the project. The project is already using
> boost and fighting the battle for more boost usage is hard enough.
>
> Does anyone know if such a facility is planned for the upcoming std?
I would advise against using threads. Processes and shared memory is
much more easier to maintain, no threading problems and performance
you gain from threads does not matter because there is always
something slow like hard disk and database which will make
no difference between processes and threads.
In java using threads is slower then using processes because
it is faster to have one gc per thread then one gc per
many threads.
So in java using processes will always be faster then using
threads because of gc which kills performance of threads anyway.
Greets
Francis Glassborow
> Andrew wrote:
>> I am designing a system where an app will need to spawn a child thread
>> then the child and parent thread will need to communicate. If this was
>> in java I would use ConcurrentLinkedQueue but what to do in C++? I
>> have googled and searched boost but cannot find anything.
>>
>> There is a class that would serve in ACE but ACE is huge so I do not
>> want to introduce ACE to the project. The project is already using
>> boost and fighting the battle for more boost usage is hard enough.
>>
>> Does anyone know if such a facility is planned for the upcoming std?
>
> I would advise against using threads. Processes and shared memory is
> much more easier to maintain, no threading problems and performance
> you gain from threads does not matter because there is always
> something slow like hard disk and database which will make
> no difference between processes and threads.
>
> In java using threads is slower then using processes because
> it is faster to have one gc per thread then one gc per
> many threads.
> So in java using processes will always be faster then using
> threads because of gc which kills performance of threads anyway.
>
All that may be perfectly true on a single core single CPU system. But
if your system provides concurrent execution and your language
implementation provides for concurrency then I do not see how your
argument works. As C++ does not have GC I do not see how that is
relevant either.
Zeljko Vrba
> Andrew wrote:
>> I am designing a system where an app will need to spawn a child thread
>> then the child and parent thread will need to communicate. If this was
>> in java I would use ConcurrentLinkedQueue but what to do in C++? I
>> have googled and searched boost but cannot find anything.
>>
>
> I would advise against using threads. Processes and shared memory is
> much more easier to maintain, no threading problems and performance
>
As soon as you establish shared memory between processes, you open the same
bag of problems as you do by just using threads. Except that shared memory
is in addition much clumsier to use...
>
> In java using threads is slower then using processes because
> it is faster to have one gc per thread then one gc per
> many threads.
> So in java using processes will always be faster then using
> threads because of gc which kills performance of threads anyway.
>
Any references to recent benchmarks that can support these claims?
Chris M. Thomasson
news:hgs21l$pm0$1...@news.albasani.net...
> Andrew wrote:
>> I am designing a system where an app will need to spawn a child thread
>> then the child and parent thread will need to communicate. If this was
>> in java I would use ConcurrentLinkedQueue but what to do in C++? I
>> have googled and searched boost but cannot find anything.
>>
>> There is a class that would serve in ACE but ACE is huge so I do not
>> want to introduce ACE to the project. The project is already using
>> boost and fighting the battle for more boost usage is hard enough.
>>
>> Does anyone know if such a facility is planned for the upcoming std?
>
> I would advise against using threads. Processes and shared memory is
> much more easier to maintain,
I am curious as to what made you come to that conclusion? Anyway, which one
is easier: Creating a dynamic unbounded queue with threads or shared memory
and processes? With threads you can get this done rather easily using
pointers. For instance, with threads the nodes and queue anchor might look
like:
_____________________________________________________
struct node
{
struct node* next;
};
struct queue
{
struct node* head;
struct node* tail;
intra_process_mutex mutex;
};
_____________________________________________________
With processes you are probably going to need to use *offsets off a base
memory; the queue might look like:
_____________________________________________________
struct node
{
size_t next;
};
struct queue
{
size_t head;
size_t tail;
inter_process_robust_mutex mutex;
unsigned char* base;
};
_____________________________________________________
and you get at the actual nodes by adding the offsets (e.g., node::next,
queue::head/tail) to the base memory (e.g., queue::base) that the process
mapped the shared memory for the queue to. Also, with processes you might
need to handle the case in which a process dies in the middle of accessing
the queue. IMO, it's normal for a process to die in general, however, it's
NOT normal for a thread to just up and die. This is why there are such
things as so-called robust mutexs for process synchronization. You have to
deal and fix up possible data corruption from the queue data-structure being
left in an intermediate state by the dead process.Therefore, IMHO, threads
are easier for me to work with than multiple processes.
[*] - This is only true if you cannot guarantee that each process maps
memory at the _exact_ same base address.
> no threading problems and performance
> you gain from threads does not matter because there is always
> something slow like hard disk and database which will make
> no difference between processes and threads.
Shared memory and processes should be equal in performance to threads if you
can use pointers. With the offsets you need to perform an addition in order
to get at the node data-structure; something like:
_____________________________________________________
struct node*
queue_get_head(struct queue const* const self)
{
return (struct node*)(self->base + self->head);
}
_____________________________________________________
Ahh, but you have to setup a special offset value for NULL. Perhaps:
_____________________________________________________
#define NULL 0xFFFFFFFFU /* assume 32-bit system */
struct node*
queue_get_head(struct queue const* const self)
{
if (self->head == NULL) return NULL;
return (struct node*)(self->base + self->head);
}
_____________________________________________________
Why would you think that all that is easier than using threads? What am I
missing here?
Thanks.
Andrew
> On 2009-12-23, Branimir Maksimovic <bm...@hotmail.com> wrote:> Andrew wrote:
> >> I am designing a system where an app will need to spawn a child thread
> >> then the child and parent thread will need to communicate. If this was
> >> in java I would use ConcurrentLinkedQueue but what to do in C++? I
> >> have googled and searched boost but cannot find anything.
>
> I'm not very familiar with Java, but Boost.interprocess has message queues:
>
The stuff that Anthony Williams provided suits me better than the
boost message queue. Anthony's class is templated on the message type
which is just what I want. This is the way I am used to it working
from when I used a similar facility in ACE. I am using this class,
which the later modification Anthony made to support timed waits, and
it works just fine. Thanks again, Anthony!
Regards,
Andrew Marlow
Branimir Maksimovic
> On 2009-12-23, Branimir Maksimovic <bm...@hotmail.com> wrote:
>> Andrew wrote:
>>> I am designing a system where an app will need to spawn a child thread
>>> then the child and parent thread will need to communicate. If this was
>>> in java I would use ConcurrentLinkedQueue but what to do in C++? I
>>> have googled and searched boost but cannot find anything.
>>>
> I'm not very familiar with Java, but Boost.interprocess has message queues:
>
> http://www.boost.org/doc/libs/1_41_0/doc/html/interprocess/synchronization_mechanisms.html#interprocess.synchronization_mechanisms.message_queue
>
>> I would advise against using threads. Processes and shared memory is
>> much more easier to maintain, no threading problems and performance
>>
> As soon as you establish shared memory between processes, you open the same
> bag of problems as you do by just using threads. Except that shared memory
> is in addition much clumsier to use...
Hm, with shared memory you don;t get surprised when someone links in
library which is not thread safe...
>
>> In java using threads is slower then using processes because
>> it is faster to have one gc per thread then one gc per
>> many threads.
>> So in java using processes will always be faster then using
>> threads because of gc which kills performance of threads anyway.
>>
> Any references to recent benchmarks that can support these claims?
You don;t need references just common reason. GC is thread(s) which
has to scan memory for unreferenced heap. Since threads are
roaming through heap, you have to stop all threads in order
to examine heap,stack,bss etc...
which means while you are scanning memory threads are not working...
either that or you have to use lock for every access to any pointer
in application...
application should also lock every access to any pointer value...
So if GC has to release memory often, performance goes down....
And I can't see simpler and faster way to perform collection than
to stop program, perform collection in multiple threads, then
continue program...
Compacting collector does not have other choice because it has
to update all references in a program...
Greets
Branimir Maksimovic
> "Branimir Maksimovic" <bm...@hotmail.com> wrote in message
> news:hgs21l$pm0$1...@news.albasani.net...
>> Andrew wrote:
>>> I am designing a system where an app will need to spawn a child thread
>>> then the child and parent thread will need to communicate. If this was
>>> in java I would use ConcurrentLinkedQueue but what to do in C++? I
>>> have googled and searched boost but cannot find anything.
>>>
>>> There is a class that would serve in ACE but ACE is huge so I do not
>>> want to introduce ACE to the project. The project is already using
>>> boost and fighting the battle for more boost usage is hard enough.
>>>
>>> Does anyone know if such a facility is planned for the upcoming std?
>>
>> I would advise against using threads. Processes and shared memory is
>> much more easier to maintain,
>
> I am curious as to what made you come to that conclusion? Anyway, which one
> is easier: Creating a dynamic unbounded queue with threads or shared memory
> and processes?
Depends. You can always use cout and simple pipe. Why queue?
When performance is concern vectorized operations on memory
parallel loops and such stuff have sense with threads.
There are many ways to do IPC... Depending on situation.
For example I had case when server version that is php which
with popen starts c executable which returns result with printf and
initialize data with every request, performs
three times faster than java multithreaded
server as search engine...
There is deque class in stdlib, it is good as queue, I use
it all the time...
OP can lock it with os mutex he have and that;s it...
Vector is also ok for this (push_back/back/pop_back), linked list etc...
I don;t see problem here. But since op asks this question,
probably he doesn;t know what is mutex...
That's why if he uses cout/pipe or sockets or something
else he will safe himself lot of maintenance problems...
> Why would you think that all that is easier than using threads? What am I
> missing here?
Maintenance problems. With processes, there is no problem.
For example there is pre forked and pre threaded version
of apache. People prefer forked version because of libraries
they have to link in. On my machine mt server serves
more than 60000 thousand simple echo requests per second
with 28000 connections on single cpu,
which is far too much , you get rarely more than 100 requests per
second...
Greets
For Op here is code for queue:
static std::deque<Service*> lstSvc_;
.....
Mutex::Mutex()
{
pthread_mutex_init(&mutex_,0);
}
void Mutex::lock()
{
int rc=pthread_mutex_lock(&mutex_);
if(rc)throw Exception("mutex lock error:%s",strerror(rc));
}
void Mutex::unlock()
{
int rc = pthread_mutex_unlock(&mutex_);
if(rc)throw Exception("mutex unlock error:%s",strerror(rc));
}
Mutex::~Mutex()
{
pthread_mutex_destroy(&mutex_);
}
template <class Lock>
class AutoLock{
public:
explicit AutoLock(Lock& l):lock_(l)
{
lock_.lock();
}
void lock()
{
lock_.lock();
}
void unlock()
{
lock_.unlock();
}
~AutoLock()
{
lock_.unlock();
}
private:
AutoLock(const AutoLock&);
AutoLock& operator=(const AutoLock&);
Lock& lock_;
};
.....
{
AutoLock<Mutex> l(lstSvcM_);
if(!lstSvc_.empty())
{
s= lstSvc_.front();
lstSvc_.pop_front();
}
else
{
more = false;
s=0;
continue;
}
}
....
case Socket::Reading:
if(s->doneReading())
{
AutoLock<Mutex> l(lstSvcM_);
lstSvc_.push_back(s);
}
else
pl_.read(s);
break;
I don;t use condition variables, every thread performs both io and
service. so for waking other threads I use:
Poll::Poll(nfds_t size)
:fds_(new pollfd[size+1]),maxfds_(size),nfds_(0)
{
if(socketpair(AF_LOCAL,SOCK_STREAM,0,wake_)<0)
throw Exception("Poll init error: %s",strerror(errno));
int flags = fcntl(wake_[0], F_GETFL, 0);
fcntl(wake_[0], F_SETFL, flags | O_NONBLOCK); // set non blocking
flags = fcntl(wake_[1], F_GETFL, 0);
fcntl(wake_[1], F_SETFL, flags | O_NONBLOCK); // set non blocking
AutoLock<Mutex> l(lstPollM_);
lstPoll_.push_back(this);
}
void Poll::wake()
{
int rc = ::write(wake_[0],"1",1);
}
Hope this helps.
Chris M. Thomasson
> Chris M. Thomasson wrote:
>> "Branimir Maksimovic" <bm...@hotmail.com> wrote in message
>> news:hgs21l$pm0$1...@news.albasani.net...
>>> Andrew wrote:
>>>> I am designing a system where an app will need to spawn a child thread
>>>> then the child and parent thread will need to communicate. If this was
>>>> in java I would use ConcurrentLinkedQueue but what to do in C++? I
>>>> have googled and searched boost but cannot find anything.
>>>>
>>>> There is a class that would serve in ACE but ACE is huge so I do not
>>>> want to introduce ACE to the project. The project is already using
>>>> boost and fighting the battle for more boost usage is hard enough.
>>>>
>>>> Does anyone know if such a facility is planned for the upcoming std?
>>>
>>> I would advise against using threads. Processes and shared memory is
>>> much more easier to maintain,
>>
>> I am curious as to what made you come to that conclusion? Anyway, which
>> one
>> is easier: Creating a dynamic unbounded queue with threads or shared
>> memory
>> and processes?
>
> Depends. You can always use cout and simple pipe. Why queue?
For performance and scalability reasons. A pipe or socket has fairly
significant overhead when compared to a clever shared memory based
synchronization. I prefer to use lightweight synchronization primitives and
I also know how to implement them. I am familiar with the caveats and
realize that it's easier to create intra-process facilities. Keep in mind
that I am writing this from the low-level implementation point of view.
> When performance is concern vectorized operations on memory
> parallel loops and such stuff have sense with threads.
> There are many ways to do IPC...
Indeed! :^)
> Depending on situation.
> For example I had case when server version that is php which
> with popen starts c executable which returns result with printf and
> initialize data with every request, performs
> three times faster than java multithreaded
> server as search engine...
Unfortunately, that does not prove anything.
> There is deque class in stdlib, it is good as queue, I use
> it all the time...
As I implied in the previous post, you _cannot_ use a `std::deque' _unless_
you can _ensure_ that every single process that wants to ever use the queue
will map there personal view of shared memory at the _exact_ same base
address as all the others. This is not always possible. Therefore, if you
have experience with creating inter-process synchronization primitives you
know to avoid pointers that the plague and always work in terms of offsets
in order to completely solve the issue in all cases.
> OP can lock it with os mutex he have and that;s it...
I am sorry, but that's not "all" of it. For instance, what happens if a
process dies while it's in the middle of mutating the deque? A `std::deque'
is not robust, and cannot roll itself back and recover for this scenario.
Keep in mind that it's normal for processes to die, unless you have strict
control and know for a 100% fact that none of them will ever die
prematurely. The OS provided inter-process mutex should have the ability to
detect this. Think `WAIT_ABANDONED ' on Windows and 'EOWNERDEAD' on POSIX.
On the other hand, threads should _never_ be randomly dieing in unexpected
places.
> Vector is also ok for this (push_back/back/pop_back), linked list etc...
>
> I don;t see problem here.
There are many caveats. Not only do you have to keep offsets, you are also
going to need to use a special allocator that works with a view of shared
memory.
> But since op asks this question,
> probably he doesn;t know what is mutex...
> That's why if he uses cout/pipe or sockets or something
> else he will safe himself lot of maintenance problems...
Granted, however I am focusing on performance and difficulty of
implementation. If you were actually implementing a high-performance
communication primitive, would it be easier to create an intra-process or a
robust inter-process version?
>> Why would you think that all that is easier than using threads? What am I
>> missing here?
>
> Maintenance problems. With processes, there is no problem.
> For example there is pre forked and pre threaded version
> of apache. People prefer forked version because of libraries
> they have to link in. On my machine mt server serves
> more than 60000 thousand simple echo requests per second
> with 28000 connections on single cpu,
> which is far too much , you get rarely more than 100 requests per
> second...
Well, one thing that is nice with processes is that you can gracefully
handle a buggy user plug-in that crashes. You isolate plug-in instances to
a separate process-pool. When the watchdog process detects that a process in
the pool has died, it can resurrect the process and everything's fine and
the main application is still up and running. Therefore, I would _not_ use
threads to handle a plug-in framework. I would use a single master process,
a single watchdog process, and multiple user plug-in processes.
[...]
Branimir Maksimovic
>> it all the time...
>
> As I implied in the previous post, you _cannot_ use a `std::deque' _unless_
> you can _ensure_ that every single process that wants to ever use the queue
> will map there personal view of shared memory at the _exact_ same base
> address as all the others. This is not always possible. Therefore, if you
> have experience with creating inter-process synchronization primitives you
> know to avoid pointers that the plague and always work in terms of offsets
> in order to completely solve the issue in all cases.
I'm using deque in combination with threads. That was meant for that.
For processes and shared memory you are right and I agree.
>
>
>
>
>> OP can lock it with os mutex he have and that;s it...
>
> I am sorry, but that's not "all" of it. For instance, what happens if a
> process dies while it's in the middle of mutating the deque?
Yes, these are all problems with processes/shared memory.
>
>
>
>> Vector is also ok for this (push_back/back/pop_back), linked list etc...
>>
>> I don;t see problem here.
>
> There are many caveats. Not only do you have to keep offsets, you are also
> going to need to use a special allocator that works with a view of shared
> memory.
>
I meant for threads. No need for special class. ACE/any other
>
>
>
>> But since op asks this question,
>> probably he doesn;t know what is mutex...
>> That's why if he uses cout/pipe or sockets or something
>> else he will safe himself lot of maintenance problems...
>
> Granted, however I am focusing on performance and difficulty of
> implementation. If you were actually implementing a high-performance
> communication primitive, would it be easier to create an intra-process or a
> robust inter-process version?
You have argument. Threaded version is easier to write.
>
>
>
>
>>> Why would you think that all that is easier than using threads? What
>>> am I
>>> missing here?
>>
>> Maintenance problems. With processes, there is no problem.
>> For example there is pre forked and pre threaded version
>> of apache. People prefer forked version because of libraries
>> they have to link in.
Therefore, I would _not_ use
> threads to handle a plug-in framework. I would use a single master process,
> a single watchdog process, and multiple user plug-in processes.
>
> [...]
>
That is what Im talking about. Problem is that I wrote cmd handler,
which other programmers use to write commands. Something like
rpc.
Once I got emergency call when I was in bus on road to Barcelona
on holiday, because one of programmers linked in non thread safe
library, and online servers started to have problems. Thanks god on
Internet cafes and ssh ;)
Greets
--
http:/maxa.homedns.org/
Chris M. Thomasson
> Chris M. Thomasson wrote:
>> "Branimir Maksimovic" <bm...@hotmail.com> wrote in message
>>
>>
>>
>>> There is deque class in stdlib, it is good as queue, I use
>>> it all the time...
>>
>> As I implied in the previous post, you _cannot_ use a `std::deque'
>> _unless_
>> you can _ensure_ that every single process that wants to ever use the
>> queue
>> will map there personal view of shared memory at the _exact_ same base
>> address as all the others. This is not always possible. Therefore, if you
>> have experience with creating inter-process synchronization primitives
>> you
>> know to avoid pointers that the plague and always work in terms of
>> offsets
>> in order to completely solve the issue in all cases.
>
> I'm using deque in combination with threads. That was meant for that.
> For processes and shared memory you are right and I agree.
Okay. As for STL deque, I personally prefer intrusive data-structures. Here
is sketch for a queue:
<pseudo-code in news reader>
___________________________________________________________
struct node
{
node* m_next;
};
struct queue
{
node* m_head; // = NULL
node* m_tail;
void push(node* n)
{
if (! m_head)
{
m_head = n;
}
else
{
m_tail->m_next = n;
}
m_tail = n;
}
node* pop()
{
node* n = m_head;
if (n)
{
m_head = n->m_next;
}
return n;
}
};
___________________________________________________________
IMVHO, there is no "need" for dynamic allocation for something as simple as
a FIFO. The interface allows the user to provide memory management. The
nodes could reside on the "stack" of the calling thread, or the caller could
use dynamic allocation. Not sure why something as simple as a queue should
be required to handle node allocation, why a special node allocator for a
simple queue? Why not let the user arrange and manage memory accordingly?
--
yeroen
> then the child and parent thread will need to communicate. If this was
> in java I would use ConcurrentLinkedQueue but what to do in C++? I
> have googled and searched boost but cannot find anything.
Herb Sutter, building on earlier work of Petru Marginean,
authored a series of articles in Dr. Dobbs containing a complete C++
implementation of a lock-free
concurrent queue:
http://www.ddj.com/cpp/210600279
http://www.ddj.com/hpc-high-performance-computing/210604448
http://www.ddj.com/cpp/211601363
The implementation depends on the availability of the std::atomic<>
template, which may or may not be provided by
your current working compiler. Intel TBB also provides an
tbb::atomic<> template.
Chris M. Thomasson
news:bf4fda3b-e4d4-4f12...@k9g2000vbl.googlegroups.com...
> On Dec 8, 9:19 pm, Andrew <marlow.and...@googlemail.com> wrote:
>> I am designing a system where an app will need to spawn a child thread
>> then the child and parent thread will need to communicate. If this was
>> in java I would use ConcurrentLinkedQueue but what to do in C++? I
>> have googled and searched boost but cannot find anything.
>
> Herb Sutter, building on earlier work of Petru Marginean,
> authored a series of articles in Dr. Dobbs containing a complete C++
> implementation of a lock-free
> concurrent queue:
FWIW, here is a decent algorithm for a wait-free single producer/consumer
queue:
http://thread.gmane.org/gmane.comp.lib.boost.devel/197400
(IMO, it's probably good to read the entire thread...)
You can use eventcounts for conditional blocking. IIRC, the code by Petru
used a timed wait on a condition variable which I consider to be sort of
"hackish" in nature.
Andrew
> > I am designing a system where an app will need to spawn a child thread
> > then the child and parent thread will need to communicate. If this was
> > in java I would use ConcurrentLinkedQueue but what to do in C++? I
> > have googled and searched boost but cannot find anything.
>
> Herb Sutter, building on earlier work of Petru Marginean,
> authored a series of articles in Dr. Dobbs containing a complete C++
> implementation of a lock-free
> concurrent queue:
> The implementation depends on the availability of the std::atomic<>
> template, which may or may not be provided by
> your current working compiler.
Thanks for the pointer but I really need a portable solution. The
compiler I am using is Visual Studio 2005. I have found that the code
provided by Anthony Williams works great. It uses boost which takes
care of the portability issues.
Chris M. Thomasson
news:vKA_m.44056$_b5....@newsfe22.iad...
[...]
> Okay. As for STL deque, I personally prefer intrusive data-structures.
> Here
> is sketch for a queue:
>
> <pseudo-code in news reader>
> ___________________________________________________________
> struct node
> {
> node* m_next;
> };
>
>
> struct queue
> {
> node* m_head; // = NULL
> node* m_tail;
>
>
> void push(node* n)
> {
// DAMN IT !
// I forgot to set the next pointer of the new node to NULL!
n->m_next = NULL;
// Sorry about that non-sense!
// ;^(...
> if (! m_head)
> {
> m_head = n;
> }
>
> else
> {
> m_tail->m_next = n;
> }
>
> m_tail = n;
> }
>
>
> node* pop()
> {
[...]
> }
> };
> ___________________________________________________________