CODEWITHSUNDEEP
c++cmultithreadingdeque
5YrsLaterDBA
5YrsLaterDBA

Reputation: 34760

should I synchronize the deque or not

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.

Upvotes: 1

Views: 586

Answers (2)

Matthieu M.
Matthieu M.

Reputation: 299800

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.

Upvotes: 2

Pete Becker
Pete Becker

Reputation: 76245

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.

Upvotes: 4

Related Questions