8

As far as the C++ standard is concerned (C++11 and later, I guess, since before threads were not considered), is it safe to write concurrently to different, possibly adjacent, elements of an array?

For example:

#include <iostream>
#include <thread>

int array[10];

void func(int i) {
   array[i] = 42;
}

int main() 
{
   for(int i = 0; i < 10; ++i) {
      // spawn func(i) on a separate thread
      // (e.g. with std::async, let me skip the details)
   }
   // join

   for(int i = 0; i < 10; ++i) {
      std::cout << array[i] << std::endl; // prints 42?
   }

   return 0;
}

In this case, is it guaranteed by the language that the writes of different elements of the array do not cause race conditions? And is it guaranteed for any type, or are there any requirements for this to be safe?

gigabytes
  • 3,104
  • 19
  • 35
  • As long as the array exists for as long as either thread accesses it, all should be okay. It would be unsafe if Thread A created an array of automatic storage duration, and thread B accessed any element of that array after Thread A had terminated. Also, if you are referring to a dynamically allocated array, that array cannot be resized while being accessed by either thread (e.g. one thread can't resize it safely while the other is accessing it). The logic does not work for adjacent bits in an `int` (e.g. treating an `int` as an array of 8 bits using bit fiddling operations). – Peter Apr 12 '19 at 08:56

4 Answers4

4

Yes.

From https://en.cppreference.com/w/cpp/language/memory_model:

When an evaluation of an expression writes to a memory location and another evaluation reads or modifies the same memory location, the expressions are said to conflict. A program that has two conflicting evaluations has a data race unless [...]

Then:

A memory location is

  • an object of scalar type (arithmetic type, pointer type, enumeration type, or std::nullptr_t)
  • or the largest contiguous sequence of bit fields of non-zero length

So, if the elements of an array are stored at different memory locations you do not have a conflicting evaluations.

And an array is:

A declaration of the form T a[N];, declares a as an array object that consists of N contiguously allocated objects of type T.

Since two distinct objects cannot have the same address, they and their constituants cannot have the same memory location. Which guarantees satisfaction of the earlier requirement.

Moreover, objects can consist of more than one memory location, so you could even have two threads operate on different members of the same object!

Please note that for your example to be correct, join has to be written correctly as well, but it's not related to adjacent elements of an array, but rather operating on the same one, so I guess it's beyond the scope of the question.

Personal note: Btw. If this wasn't guaranteed, it would seriously limit if not render useless parallel computing in standard library.

Community
  • 1
  • 1
luk32
  • 15,812
  • 38
  • 62
  • different elements of an array cannot be stored at the same memory location, I am afraid this whole answer is offtopic – 463035818_is_not_an_ai Apr 12 '19 at 09:55
  • @user463035818 That's the point. it says "*consists of N contiguously allocated objects*" How is it off topic? Do I have to write explicitly, that elements of an array can't have the same memory location? – luk32 Apr 12 '19 at 10:04
  • ah sorry, reread it and now I get it ;). I just stumbled upon the wording in "So **if** the elements of an array are stored at different memory locations...", I guess that is just meant as an intermediate step in your argumentation – 463035818_is_not_an_ai Apr 12 '19 at 10:07
  • and i dont really understand "as long as the synchornization (join) is written correctly." what do you mean by that? – 463035818_is_not_an_ai Apr 12 '19 at 10:07
  • That, if OP doesn't write join at all, then there can be a data race at the latter loop if a different thread gets to read same index. One could also erroneously join same thread object, which is UB etc. There is no actual code for that, so it's hard to tell, but there's a possbility of doing things wrong. I've written a clarification, so it's hopefully less convoluted. – luk32 Apr 12 '19 at 10:11
  • 1
    @user463035818 I've made it a note, since the problem would occur regarding the same memory location, elements being adjacent are not related, so it's beyond the point of question. – luk32 Apr 12 '19 at 10:18
2

Data races only occur on the same memory location, ie there can be a data race on two glvalues x and y only if &x == &y.

[intro.races]/2

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]/21

The execution of a program contains a data race if it contains two potentially concurrent conflicting actions [...]

The remainder of which doesn't apply here. So no there is no data race on your array.

Passer By
  • 19,325
  • 6
  • 49
  • 96
1

Yes, but 'OK' does not mean it is smart to do it.

There are several issues to consider, perhaps the most important one is CPU caches. On e.g. x86, cache lines are 64 bytes long, so each thread should e.g. work on a chunk of the array that matches the cache line length to avoid e.g. false sharing.

Here is one example: false sharing SO question/answer

Erik Alapää
  • 2,585
  • 1
  • 14
  • 25
1

It’s safe to concurrently access consecutive elements on separate threads, but if it occurs frequently, it could cause performance issues in the code. This is due to the fundamental limitations of parallelism on modern CPUs.

For most programs memory access is a major bottleneck. Performance-critical sections of the code have to be written carefully to avoid excessive cache misses. There are multiple levels to the cache, and each level is faster than the previous one. However, when data is not in the cache, or when data might have been changed by another CPU, it has to be re-loaded into the cache.

The CPU can’t keep track of the state of each individual byte, so instead it keeps track of blocks of bytes called Cache Lines. If any byte in a cache line is changed by a separate CPU, it has to be re-loaded to ensure synchronization.

Accessing separate bytes on different threads only causes this re-loading if they’re in the same cache line. And because cache lines are contiguous, accessing contiguous elements from separate threads will usually result in the memory having to be re-loaded into the cache. This is called false sharing, and should be avoided in parallel code if performance is a concern.

That being said, if it happens rarely it’s probably fine, and you should benchmark and test your code before optimizing it.

Alecto Irene Perez
  • 10,321
  • 23
  • 46