Write Concurrently Vector<Bool>

Write concurrently vectorbool

Concurrent writes to vector<bool> are never ok, because the underlying implementation relies on a proxy object of type vector<bool>::reference which acts as if it was a reference to bool, but in reality will fetch and update the bitfield bytes as needed.

When using multiple threads without synchronization, the following might happen: Thread 1 is supposed to update a bit, and reads the byte containing it. Then thread 2 reads the same byte, then thread 1 updates a bit and writes the byte back, and then thread 2 updates another bit and writes the byte back, overwriting the edit of thread 1.

This is just one possible scenario, there are others that would lead to the same kind of data corruption.

---

In the vector<int> situation, if you are absolutely sure that all threads write the same value into the vector, then this operation will generally not lead to data corruption. However, the standard is of course always extra careful and defines all concurrent accesses to a memory location, of which at least one is a write access, to be undefined behavior:

Two expression evaluations conflict if one of them modifies a memory location and the other one reads or modifies the same memory location. –
intro.races/2

Therefore, as soon as you do any modification operation on the same element from two different threads, you will have a race condition and need proper synchronization, e.g. by using std::atomic<int>.

C++ concurrent writes to array (not std::vector) of bools

You should use std::array<bool, 2048> someArray, not bool someArray[2048];. If you're in C++11-land, you'll want to modernize your code as much as you are able.

std::array<bool, N> is not specialized in the same way that std::vector<bool> is, so there's no concerns there in terms of raw safety.

As for your actual question:

Will the reader see all the writes to someArray that occurred before the lock was acquired?

Only if the writers to the array also interact with the lock, either by releasing it at the time that they finish writing, or else by updating a value associated with the lock that the reader then synchronizes with. If the writers never interact with the lock, then the data that will be retrieved by the reader is undefined.

One thing you'll also want to bear in mind: while it's not unsafe to have multiple threads write to the same array, provided that they are all writing to unique memory addresses, writing could be slowed pretty dramatically by interactions with the cache. For example:

void func_a() {
    std::array<bool, 2048> someArray{};
    for(int i = 0; i < 8; i++) {
        std::thread writer([i, &someArray]{
            for(size_t index = i * 256; index < (i+1) * 256; index++) 
                someArray[index] = true;
            //Some kind of synchronization mechanism you need to work out yourself
        });
        writer.detach();
    }
}

void func_b() {
    std::array<bool, 2048> someArray{};
    for(int i = 0; i < 8; i++) {
        std::thread writer([i, &someArray]{
            for(size_t index = i; index < 2048; index += 8) 
                someArray[index] = true;
            //Some kind of synchronization mechanism you need to work out yourself
        });
        writer.detach();
    }
}

The details are going to vary depending on the underlying hardware, but in nearly all situations, func_a is going to be orders of magnitude faster than func_b, at least for a sufficiently large array size (2048 was chosen as an example, but it may not be representative of the actual underlying performance differences). Both functions should have the same result, but one will be considerably faster than the other.

Thread safety of Vector of atomic bool

The OP appears to be asking whether multiple threads can evaluate

v[2].compare_exchange_strong(false, true)

when such evaluations are potentially concurrent, without causing a data race.

This will not compile because compare_exchange_strong requires an lvalue as its first argument. I will assume that this issue is corrected.

The answer is yes. According to [container.requirements.dataraces]/1:

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

This implies that evaluating v[2] is not allowed to modify the vector (nor any internal static data that might be shared between threads) and thus may not race with the same evaluation in another thread. The compare_exchange_strong operation is being performed on an atomic object, so it's impossible for it to race with anything.

Is std::vector thread-safe and concurrent by default? Why or why not?

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.

is vector threadsafe for read/write at different locations?

vector does not provide any thread-safety guarantees, so technically the answer would be no.

In practice, you should be able to get away with it... until the day that someone (possibly you) makes a small change in one corner of the program and all hell breaks loose. I wouldn't feel comfortable doing this in any non-trivial program.

C++11 reading a bool concurrently

Technically C++ only got a proper multi threaded memory model in C++11, and accessing the flag variable in a multi threaded context is basically undefined.

Accessing a thread-shared variable in C++ is well defined as long as there are no data races. See Threads and data races for more details:

... in particular, release of a std::mutex is synchronized-with, and therefore, happens-before acquisition of the same mutex by another thread, which makes it possible to use mutex locks to guard against data races.

---

Mutex lock/unlock constitute acquire/release memory barriers. You do not need std::atomic for thread-shared state that is only accessed when the mutex is locked. When a condition notification is received it first locks the mutex, so that you can access the shared state safely.

---

People often introduce data races when they try to use std::atomic variables with std::mutex/std::condition_variable and access that std::atomic without holding the mutex. An example.

---

Related Topics