13

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?

quimnuss
  • 1,503
  • 2
  • 17
  • 37

3 Answers3

16

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)

  1. 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]);
Zulan
  • 21,896
  • 6
  • 49
  • 109
  • Oh man you put me in a tight spot now as to which answer to mark. Thanks for the standard quote, that's an excellent finding. – quimnuss May 31 '18 at 16:55
  • I was actually wondering how the general rule mentioned in Yakk's answer holds for `std::vector` which lead me to this answer because it was too long for a comment to the existing ones. – Zulan Jun 01 '18 at 07:07
  • Just to be sure, Is this annotation also on C++11? – quimnuss Jun 01 '18 at 14:02
  • Yes, since C++11 – Zulan Jun 01 '18 at 14:35
  • 1
    You could also point out that `deque` has reference stability on insertion at either end, so if it is possible to do `auto &ref = dq[i];` in a synchronous section of the code, then `ref` can be accessed concurrently with `push_back()`, `push_front()` etc. – unfortunately iterators are invalidated, so in the given loop, you'd have to store every single pointer or reference beforehand. – Arne Vogel Jun 04 '18 at 13:18
8

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

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
  • 4
    To prevent false sharing, try to access neighboring elements with the same thread. Typically you are fine with a standard `#pragma omp for`. – Zulan May 31 '18 at 14:23
  • Thanks for the mention Zultan. That's exactly what I'm doing so I'm reassured. – quimnuss May 31 '18 at 14:43
  • @NathanOliver [This answer](https://stackoverflow.com/questions/9042571/is-stdvector-or-boostvector-thread-safe) on `std::vector` claims that "no concurrent reader while writing". It doesn't say if he refers to the container or to an element of the container. I still think, like you, that given my context it is safe to write and read different memory locations. Also, there are no `push_back`'s in my concurrent block. – quimnuss May 31 '18 at 14:48
  • 1
    @quimnuss I'm referring to both. As long as you don't not have multiple threads modify the state of the deque itself (it's size) and as long as you do not have multiple threads reading and modifying a single element inside the `deque` you will be safe. – NathanOliver May 31 '18 at 14:50
1

Arule for all standard containers is:

  • Many readers or one writer on the entire container and on each element.
  • Individual element reading or modification (not adding/removing an element) is also read operation on the container.

That is only modestly too strong. You can do a small number of things that violate the above rules without being a race condition under the standard.

In the standard, this is usually worded in terms of const methods on the container. A read method is const, a write method is not const. The exception is that begin() and end() and data() (methods that just return iterators) that are non-const count as const.

For iteration and element access, it is worded in terms of iterator invalidation. Many operations invalidate iterators, and if an iterator is invalidated in an unsequenced manner with its use it is a race condition.

As an example of a case where the rule of thumb above says "no" but the standard says "ok":

You can have a map and a reference to a value in the map stored. You can be editing the value while another thread adds key value pairs to the map.

As no iterators are invalidated by the map, and you aren't touching the key, I beleive there is no race condition.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524