12

What does it mean to make a dynamic array thread-safe and concurrent? Say, for example, std::vector.

  1. Two threads may want to insert at the same position. No synchronization needed as it will be done as per thread scheduling.
  2. One thread erasing and another going to access the same element? This is not a data structure issue I believe, it is a usage problem.

So is there anything that needs to be done over std::vector to make it thread-safe and concurrent or is it thread-safe and concurrent by default?

Melebius
  • 6,183
  • 4
  • 39
  • 52
Abhishek Jain
  • 9,614
  • 5
  • 26
  • 40
  • 2
    Unless explicitly stated, consider *everything* thread unsafe, that way your assumptions will err on the safe side. And both of your example needs some kind of synchronization or mutual exclusion, remember that a thread can be preempted at any time. – Some programmer dude Jun 30 '15 at 07:09
  • 5
    The only thing you can reliably do concurrently on standard containers (of which `std::vector` is one) is *read*. As soon as you introduce a *potential* for concurrent write-operation on the same object within , the wheels begin to fall off, and unless the objects themselves support atomic updates in that scenario, the wheels have left the vehicle. And if the container itself is to undergo *any* potentially layout-altering mechanics, the wheels are already a quarter-mile behind you in the ditch. – WhozCraig Jun 30 '15 at 07:15
  • The STL containers aren't thread-safe in your scenario. You'd have to either use a lock to serialize access, or use different containers that are thread-safe – Panagiotis Kanavos Jun 30 '15 at 07:27
  • Try [Boost's LockFree containers](http://www.boost.org/doc/libs/1_58_0/doc/html/lockfree.html). – Panagiotis Kanavos Jun 30 '15 at 07:34
  • 2
    @PanagiotisKanavos: When linking boost.org, replace the version number in the URL with "release". That way your link will not go stale. – DevSolar Jun 30 '15 at 07:44

2 Answers2

23

C++11 says the following about the thread safetly of containers in the standard library:

23.2.2 Container data races [container.requirements.dataraces]

For purposes of avoiding data races (17.6.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[].

Notwithstanding (17.6.5.9), implementations are required to avoid data races when the contents of the contained object in different elements in the same sequence, excepting vector<bool>, are modified concurrently.

So, basically reading from a container from multiple threads is fine, and modifying elements that are already in the container is fine (as long as they are different elements).

So, neither of your two more specific questions are thread safe for std::vector:

1) Two threads inserting into the vector is modifying the vector itself - not existing separate elements.

2) One thread erasing and other walking to access the same element is not safe because erasing an element from the vector isn't an operation that is promised to be thread safe (or "free from data races", as the standard puts it).

To perform those operations safely will require that the program impose some external synchronization itself.

Michael Burr
  • 333,147
  • 50
  • 533
  • 760
  • Clear as mud Michael :p. – Robinson Jun 30 '15 at 07:24
  • 2
    I think the important part is implied: adding or removing are *not* thread-safe. This answer should be amended to say that any other operation except those described is *not* trhead-safe – Panagiotis Kanavos Jun 30 '15 at 07:24
  • While the listed operations may be thread-safe, they are not concurrent. Think, for example, of the scenario when one thread uses the subscript operator `[]` on a vector to get the element at index X, the thread is interrupted in the just as the call begins, and another thread inserts a new element before index X. Then the initial thread will still get the element at index X but it might not be the data that the thread expected. – Some programmer dude Jun 30 '15 at 07:32
  • 2
    @JoachimPileborg: the insert operation isn't an operation that is listed as "data race safe". So 23.2.2 doesn't suggest the situation you describe as being safe. – Michael Burr Jun 30 '15 at 15:09
  • Concurrent modification of the same element is allowed *if* the elements are individually `atomic`. But note that `atomic` has no copy constructor, so it's impossible to use any functions that check if they have to grow the vector, regardless of steps you take to ensure that it *doesn't* need to grow. Code in never-taken branches is still required to compile, in C++. [How to declare a vector of atomic in C++](https://stackoverflow.com/questions/13193484/how-to-declare-a-vector-of-atomic-in-c)). This still doesn't make it safe to modify the container itself, only elements in it. – Peter Cordes Dec 04 '17 at 08:44
2

The only concurrent operations on a single object in the standard library that are safe by default are - Only accessing const-member functions - All accesses to synchronization primitives (like mutex lock and unlock or atomic operations) Everything else has to be externally synchronized. In particular, the standard library doesn't have any thread safe containers yet (as of c++14)

So the answer to both of your examples is no, they both require a form of external synchronization.

What you can do of course is modifying the value of two different elements in the container.

MikeMB
  • 20,029
  • 9
  • 57
  • 102