How to sort TBB concurrent_vector or concurrent_queue?

How to sort TBB concurrent_vector or concurrent_queue?

Now I have a solver in that I need to keep a set of self-defined data
type objects in a concurrent_vector or queue. It has to be concurrent
because the objects come from different threads.With this concurrent
container, I hope to sort these objects, eliminate duplicates and send
them back when other threads need them.

However, I know TBB offers concurrent_vector and concurrent_queue
which can be read and written concurrently from different threads. But
how to sort the objects inside a container?
Does everyone know how to do that? Thanks.

8 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

It's impossible to sort items in presence of continuous additions.

All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
http://www.1024cores.net

It's all a matter of whether you want the scalability or the functionality, because, as Dmitriy indicates (if I interpreted correctly what he wrote), you can't have both, and the concurrent containers in TBB are about performance and scalability, ruthlessly sacrificing frivolous functionality that would stand in the way of that goal.

How about using the heap operations of C++, with appropriate use of locks of course?

How about at a time, I copy the contents of concurrent vector to a STL contanier and sort the copy? It is kind of troublesome but it may be possible.

In addition, what is the heap operations of C++?

You can sort concurrent_vector if there is no concurrent accesses (in general, though some might be possible with some restrictions). Another alternative may be concurrent_unordered_map which uses split-ordered-list algorithm, i.e. the list of items is always sorted by a bit-reversed hash value. So if you can zip your key into size_t, you may make use of it.

Quoting Anton Malakhov (Intel)
Another alternative may be concurrent_unordered_map which uses split-ordered-list algorithm
Is it that recursive split ordering with the second name "trash your cache" (consecutive nodes scattered as far as possible from each other)?.. Oh, never mind.

All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
http://www.1024cores.net

I can't understand if I can use tbb:parallel_sort with tbb concurrent vector? 

tbb::concurrent_vector<int> tbb_vec;
// ...fill tbb_vec
// sort
tbb::parallel_sort(tbb_vec.begin(), tbb_vec.end());

 

Hi Alex,

Quote:

alex s. wrote:

I can't understand if I can use tbb:parallel_sort with tbb concurrent vector? 

tbb::concurrent_vector<int> tbb_vec;
// ...fill tbb_vec
// sort
tbb::parallel_sort(tbb_vec.begin(), tbb_vec.end());

 

I suppose it should work. Have you tried it? Have you faced some issues?

Regards, Alex

Leave a Comment

Please sign in to add a comment. Not a member? Join today