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

concurrent_vector pop_back() support

AJ13
New Contributor I
772 Views
Hey,

I want to use the concurrent_vector as the support structure for a concurrent priority queue. The priority queue will require an rw mutex, so it won't support true concurrent addition, but should be decent since addition can be done in O(log n) time.

Now, the only part missing from concurrent_vector is pop_back(). I have inspected the code for concurrent_vector, and I believe it would be a simple matter to implement this with an atomic decrement of my_early_size.

I'm going to do this with my own TBB code in the header, I'll paste the changes I made.

Thanks,

AJ
0 Kudos
3 Replies
RafSchietekat
Valued Contributor III
772 Views
It will be interesting to see how you would improve over, e.g., a std::priority_queue fed from a tbb::concurrent_queue (additions accumulate in the concurrent_queue until it is drained into the priority_queue when the top is popped).
0 Kudos
Anton_M_Intel
Employee
772 Views
Adding pop_back() will break the assumption that vector's size will never decrease. It is used deeply in design of the container and missing this causes losing of some guarantees which concurrent_vector provides.

BTW, we've tried some implementations of concurrent_priority_queue few years ago and it was not worth including in TBB due to bad performance in comparison to std::priority_queue with fat lock around it. There were too many atomic operations per pop/push methods.
0 Kudos
AJ13
New Contributor I
772 Views
Is this concurrent_priority_queue available for study to see what is wrong with it? Also did you use std::priority_queue with std::vector or tbb::concurrent_vector?
0 Kudos
Reply