Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.
2464 Discussions

How to sort TBB concurrent_vector or concurrent_queue?

Jakcie_Jin
Beginner
844 Views

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.

0 Kudos
7 Replies
Dmitry_Vyukov
Valued Contributor I
844 Views
It's impossible to sort items in presence of continuous additions.
0 Kudos
RafSchietekat
Valued Contributor III
844 Views
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?
0 Kudos
Jakcie_Jin
Beginner
844 Views
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++?
0 Kudos
Anton_M_Intel
Employee
844 Views
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.
0 Kudos
Dmitry_Vyukov
Valued Contributor I
844 Views
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.


0 Kudos
alex_s_14
Beginner
844 Views

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());

 

0 Kudos
Alexei_K_Intel
Employee
844 Views

Hi Alex,

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

0 Kudos
Reply