25

I'm having a function that needs to be executed n=1000 times. This functions does a Monte Carlo style simulation and returns an int as the result. I'd like to run nthreads=4 in parallel. Whenever a thread finishes one cycle, it should put the result in a std::vector<int>. Thus, after 1000 cycles, I've a vector of 1000 ints that can be examined by statistics.

Since a std::vector is not thread-safe, I thought about std::mutex (which would surely work).

But I wonder if I can declare a vector to be atomic and thus get around mutexes? Is it possible to have a std::atomic<std::vector<int>>? And can I use push_back etc. on it?

Numeri
  • 1,027
  • 4
  • 14
  • 32
dani
  • 3,677
  • 4
  • 26
  • 60
  • Did std::atomic> compiled? – DawidPi Sep 21 '15 at 11:39
  • I can't try on this machine... but just came across atomic. – dani Sep 21 '15 at 11:42
  • I just wanted to add that if you know from the very beginning that you will have 1000 executions and your container will store exactly 1000 results then why you want to use dynamic container? I know that std::vector uses array in its implementation and no reallocation will be needed if you reserve enough space at the very beginning (so there won't be any performance gain from using std::array). – dptd Apr 21 '16 at 08:10

3 Answers3

31

C++11 §29.5/1 says

There is a generic class template atomic. The type of the template argument T shall be trivially copyable (3.9).

What does trivially copyable mean?

§3.9 tells

Scalar types, trivially copyable class types (Clause 9), arrays of such types, and cv-qualified versions of these types (3.9.3) are collectively called trivially copyable types.

For class types (of which std::vector is):

A trivially copyable class is a class that:

  • has no non-trivial copy constructors
  • has no non-trivial move constructors
  • has no non-trivial copy assignment operators
  • has no non-trivial move assignment operators
  • has a trivial destructor

According to this list std::vector is not trivially copyable and so you cannot use std::atomic<std::vector<int>>.

Since you know the size in advance and since you do not need to use methods that would require the vector be reallocated in a different location (like push_back). You can use std::vector<int>::resize or the size constructor to preallocate and preconstruct the required ints. Therefore your concurrent threads do not need to operate on the vector itself but on the elements.

If there is no access from different threads to the same element there is no race condition.

The same goes for int k[1000] which is trivially copyable. But you do not need it to be since the threads do not change the array/vector/list itself but the elements.

Community
  • 1
  • 1
Pixelchemist
  • 24,090
  • 7
  • 47
  • 71
13

You don't need to. It is totally okay to access a std::vector from multiple threads, if

  • you read objects
  • you write to different objects

So just make sure, you create a vector of size n=1000 and depending on your thread number (1 to 4) you assign elements 0-249, 250-499 etc. to your threads.

So each of your thread computes n/nthreads elements.

Community
  • 1
  • 1
UniversE
  • 2,419
  • 17
  • 24
  • 11
    It's very important that the vector is sized appropriately prior to assigning portions of it to the threads - any resizing will most definitely not be threadsafe. – Jeremy Sep 21 '15 at 12:52
  • 3
    But you still need to synchronize between the reader and the writer even if you do it like this. In particular, but not solely, because it's not guaranteed that accesses to `int` are atomic on all architectures unless you use `atomic_int` or `std::atomic`. – blubberdiblub Jun 27 '17 at 05:15
6

Atomic can be instantiated with trivially copyable types. Vector is not such a type.

DawidPi
  • 2,285
  • 2
  • 19
  • 41
  • A question is not an answer. Please write questions to the OP as a comment to the question – Gombat Sep 21 '15 at 11:38
  • Is an C-style array like `int k[1000]` a "trivially copyable type"? – dani Sep 21 '15 at 11:39
  • 1
    `k` is just a pointer. Pointers are trivially copyable. But I don't know if using this as a table will be threadsafe as `k` is a normal pointer, but `k[5]` can be written as `*(k+5)` and `k+5` is a different pointer, but I am not sure of it really. You can check `is_trivially_copyable` from `std`. You normally would write your own `threadsafe_vector` type for threadsafe containers. – DawidPi Sep 21 '15 at 11:52