concurrent_vector pop_back() support

concurrent_vector pop_back() support

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

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

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).

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.

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?

Leave a Comment

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