Is there a concurrent dequeue?

[yinghai]

Hi. In my application, I need to push and pop the elements from both ends of a queue. I noticed that the concurrent_queue in TBB can be operated only in FIFO fashion. So I wonder if there exists such concurrent dequeue in TBB since the task scheduling queue really seems to be such dequeue. Thank you.

[robert-reed]

Quoting - yinghai

Hi. In my application, I need to push and pop the elements from both ends of a queue. I noticed that the concurrent_queue in TBB can be operated only in FIFO fashion. So I wonder if there exists such concurrent dequeue in TBB since the task scheduling queue really seems to be such dequeue. Thank you.

So far there is no concurrent_deque in TBB just as there is no concurrent_stack. One of the design goals of TBB containers is to offer thread safe structures that have some edge to be able to run faster than the equivalent STL containers with locks wrapped around the access calls. That brute force technique is generally thread safe, though the serialization imposed by such "whole container" locks can seriously hamper performance scalingavailable withmultiple threads.

concurrent_queue and the new concurrent_bounded_queue can benefit from implementations more parsimonious in their lock use. All contenders to write are focused on one end of the queue while all contenders to read are at the other end. This localization allows threads simultaneously to read from and write to the queue, though clients of the queue with similarrequestswill contend with each other at either end. Those accesses can be abitrated by more local locks that block fewer threads or block for less time. The deque adds readers and writers at both ends and so poses a larger challenge to beat the performance of the unsafe-container-with-brute-lock approach. So far that's a challenge that no one has yet to overcome, at least as far as we know ;-).