Implementation of a work stealing queue in C/C++?

c++ multithreading algorithm queue work-stealing
unknown picture unknown · Jan 20, 2010 · Viewed 15.7k times · Source

I'm looking for a proper implementation of a work stealing queue in C/CPP. I've looked around Google but haven't found anything useful.

Perhaps someone is familiar with a good open-source implementation? (I prefer not to implement the pseudo-code taken from the original academic papers).

Answer

minjang picture minjang · Jan 26, 2010

No free lunch.

Please take a look the original work stealing paper. This paper is hard to understand. I know that paper contains theoretical proof rather than pseudo code. However, there is simply no such much more simple version than TBB. If any, it won't give optimal performance. Work stealing itself incurs some amount of overhead, so optimizations and tricks are quite important. Especially, dequeues are must be thread-safe. Implementing highly scalable and low-overhead synchronizations are challenging.

I'm really wondering why you need it. I think that proper implementation means something like TBB and Cilk. Again, work stealing is hard to implement.

Related questions

Circular lock-free buffer

I'm in the process of designing a system which connects to one or more stream of data feeds and do some analysis on the data than trigger events based on the result. In a typical multi-threaded producer/consumer setup, I …

Read More
OpenMp C++ algorithms for min, max, median, average

I was searching Google for a page offering some simple OpenMp algorithms. Probably there is an example to calculate min, max, median, average from a huge data array but I am not capable to find it. At least I would …

Read More
Efficient Prime Factorization for large numbers

I've been working on a little problem where I need to compute 18-digit numbers into their respective prime factorization. Everything compiles and it runs just fine, considering that it actually works, but I am looking to reduce the run time …

Read More