should I synchronize the deque or not

Question

I have a deque with pointers inside in a C++ application. I know there are two threads to access it.

Thread1 will add pointers from the back and Thread2 will process and remove pointers from the front.

The Thread2 will wait until deque reach certain of amount, saying 10 items, and then start to process it. It will only loop and process 10 items at a time. In the meantime, Thread1 may still keep adding new items into the deque.

I think it will be fine without synchronize the deque because Thread1 and Thread2 are accessing different part of the deque. It is deque not vector. So there is no case that the existing memory of the container will be reallocated.

Am I right? if not, why (I want to know what I am missing)?

EDIT:

I know it will not hurt to ALWAYS synchronize it. But it may hurt the performance or not necessary. I just want it run faster and correctly if possible.

I guess you should always use synchronization when in doubt. — bash.d, Aug 15 '13 at 12:20
Dupe of http://stackoverflow.com/questions/4105930/is-using-stddeque-or-stdpriority-queue-thread-safe?? — Peter M, Aug 15 '13 at 12:22
Boost has some [lock free data structures](http://www.boost.org/doc/libs/1_54_0/doc/html/lockfree.html), including queues, if you're worried about the cost of synchronisation. But they're quite new, so I don't know whether they're any good. — Mike Seymour, Aug 15 '13 at 12:30

score 4 · Accepted Answer · answered Aug 15 '13 at 12:22

4

The deque has to keep track of how many elements it has and where those elements are. Adding an element changes that stored data, as does removing an element. Changing that data from two threads without synchronization is a data race, and produces undefined behavior.

In short, you must synchronize those operations.

answered Aug 15 '13 at 12:22

Pete Becker

74,985
8
76
165

3

there are concurrent queues available for use (e.g. http://www.boost.org/doc/libs/1_54_0/doc/html/boost/lockfree/queue.html) you should use them instead of doing the synchronization for yourself. – Tobias Langner Aug 15 '13 at 12:25

score 2 · Answer 2 · answered Aug 15 '13 at 12:35

In general, the Standard Library containers cannot be assumed to be thread-safe unless all you do is reading from them.

If you take a look under the covers, at deque implementation, you will uncover something similar to this:

template <typename T>
class deque {
public:

private:
    static size_t const BufferCapacity = /**/;

    size_t _nb_available_buffer;
    size_t _first_occupied_buffer;
    size_t _last_occupied_buffer;

    size_t _size_first_buffer;
    size_t _size_last_buffer;

    T** _buffers; // heap allocated array of
                  // heap allocated arrays of fixed capacity
}; // class deque

Do you see the problem ? _buffers, at the very least, may be access concurrently by both enqueue and dequeue operations (especially when the array has become too small and need be copied in a bigger array).

So, what is the alternative ? What you are looking for is a concurrent queue. There are some implementations out there, and you should probably not worry too much on whether or not they are lock-free unless it proves to be a bottleneck. An example would be TTB concurrent_queue.

I would advise against creating your own lock-free queue, even if you heard it's all the fad, because all first implementations I have seen had (sometimes subtle) race-conditions.

should I synchronize the deque or not

2 Answers2