Is writing std::deque at different memory locations concurrently thread-safe?

Question

I have a std::deque<std::pair<CustomObj, int>> that doesn't change in size when starting the concurrent block.

The concurrent block reads each CustomObj of the deque and sets the int.

I can guarantee that the deque won't change size therefore it won't reallocate, and that each thread will only access a memory chunk of the deque but not the other thread's.

Does it lead to undefined behaviour reading and writing concurrently? Should I put the writing and reading in a mutual exclusion zone?

Answer 1

Surprisingly to me, there is actually a very clear section about this in the current standard itself:

(C++17, 26.2.2 Container data races, 2)

2. Notwithstanding 20.5.5.9, Implementations are required to avoid data races when the contents of the contained object in different elements in the same container, excepting vector<bool>, are modified concurrently.

Also you are allowed to call the following accessors without worry:

1. For purposes of avoiding data races (20.5.5.9), implementations shall consider the following functions to be const: begin, end, rbegin, rend, front, back, data, find, lower_bound, upper_bound, equal_range, at and, except in associative or unordered associative containers, operator[].

Since std::deque is neither exception, you are fine to concurrently call any of those functions to get different elements and modify them. Just make sure to properly isolate any modifications to the container itself from the parallel region where you concurrently access and modify the elements.

For example this would be wrong:

std::dequeue<...> dq;
#pragma omp master
{
    ...
    dq.emplace(...);
}
// no implicit barrier here,
// use omp barrier or change to omp single instead of master
#pragma omp for
for (... i; ...)
    dq[i].second = compute(dq[i]);

Answer 2

As long as you can guarantee that the the size of the deque doesn't change and only one thread will ever write to a particular element then yes, that is safe. You only have an issue when you try to modify the deque (change it's size) or when you have multiple threads reading and writing to a single element inside the deque.

One thing you could experience though is called false sharing. That is the process of a single cache line having elements that are being used by multiple threads. Since a thread write would dirty the cache line the whole thing needs to be re-synchronized which will hurt performance