Thread safety for tiny simple functions

Hello,
I've found that dereferencing elements of an array can be done safely, in parallel, by different threads, as long as the threads are referring to different elements. That is,

Code:

---

//Thread 1....
for(int i = 0; i < 100; ++i)
    array[i] = 3*i;
//end Thread 1
// . . . .
//Thread 2 .....
for(int i = 100; i < 200; ++i)
    array[i] = i % 3;
//end Thread 2

---

is safe. Am I guaranteed the same for the following?

Code:

---

struct array
{
  type& operator()(unsigned int index) { return data[index]; }
  // . . .
};

array gyar;

//Thread 1....
for(int i = 0; i < 100; ++i)
    gyar(i) = 3*i;
//end Thread 1
// . . . .
//Thread 2 .....
for(int i = 100; i < 200; ++i)
    gyar(i) = i % 3;
//end Thread 2

---

If they're inlined then it's the same. What about if not? Is calling the same function ok? Will one have to wait? I'm looking for an answer in terms of standard behavior (if such a thing exists for threads).

Thanks.

This isn't specifically covered in C/C++ standards (out of scope) but is addressed in multithreading specifications (eg posix).

The practical rule is that, if any thread is modifying the data at a specific area of memory, your code needs to ensure that no other thread can access (read or modify) that same area of memory at the same time.

Your code is doing that, as long as the ranges of i in the two loops do not overlap, the variables i do not co-exist (eg i is not a shared global), and as long as the data array does not get reallocated (eg resized) during the loop.

Inlining is not likely to break things, if your code guarantees there is no concurrent access of any memory location. If you don't provide that guarantee, all bets are off.

Function calls are irrelevant to thread safety. Only data access matters.

Note that there are some peculiar rules there. Some architectures cannot access areas smaller than a machine word. For example, a DEC Alpha CPU can only write 64-bit blocks. If you write something smaller, it will load the 64-bit word, replace the relevant part, and write the whole word again. In practice, this means that if two threads access adjacent values that lie within the same word, they may overwrite each other's changes.
The x86 architecture can access single bytes, so you don't need to worry about that on a typical PC. More interesting is cache coherency. If I remember correctly, x86 is a cache-coherent architecture, which means that the architecture guarantees that multiple cores/CPUs have the same view of system memory. What one CPU writes, another reads, if the read is indeed later than the write. This makes life for the programmer a lot easier than on architectures without coherency, where a read might read the old value until the cache is flushed.
However, this convenience comes at a cost. When a CPU writes a value, it must signal all other CPUs, and those must then discard their cached versions of the memory area and reload it. Thus, if you have multiple CPUs mucking about a single cache line, you may see a massive performance drop as each CPU's cache is constantly flushed.

Just things to be aware of.

Quote:

---

Function calls are irrelevant to thread safety. Only data access matters.

---

Perfect. Thank you two for all of the useful information.

Simultaneous writing to array elements is not guaranteed to be safe, even if the elements are at different addresses. This is colloquially known as "word tearing."

Take for instance the SPARC architecture, where all memory access is done in 32-bit words. Writing to adjacent elements of a char array will probably involve accesses to the same underlying memory word, even though you are accessing different parts of that word. The read-alter-write cycle will cause data corruption if you don't properly protect these accesses.

Fortunately I will be dealing with doubles, which are generally 4 (*edit* 8) chars big, which is nice since that's two words for x86 and one for x64. So no problem, right?

Quote:

---

Originally Posted by CodeMonkey

Fortunately I will be dealing with doubles, which are generally 4 chars big, which is nice since that's two words for x86 and one for x64. So no problem, right?

---

You can safely declare "no problem" for any particular platform, but not for all platforms in general. In practice, on your typical PC hardware with an array of doubles, I'd say "no problem."

Quote:

---

Originally Posted by CodeMonkey

Fortunately I will be dealing with doubles, which are generally 4 chars big, which is nice since that's two words for x86 and one for x64. So no problem, right?

---

"doubles" are generally 8 chars big, but yes, on x86_(32, 64) it would work fine.

However, as mentioned before, cache-coherency can cause processing inefficiency - in fact one of the major limitations to performance on LARGE Opteron systems is the fact that each processor must at all times be told about every memory access of every other processor - and if the memory access causes the cache to be emptied, then the next access of that area (64 or 128 bytes) of memory will mean a read of it.

Also be aware that many floating point (double, float or long double) [as well as some integer] operations may decompose by the compiler into more than one instruction, e.g.

Code:

---

// Global variable.
double a;
  ...
  a *= 3.0;

---

this code may come to:

Code:

---

    fld    a
    fld    constant_3_0
    fmulp
    fstp  a

---

Now, if another thread is ALSO modifying a, there is absolutely no way to tell whether a has been or hasn't been multiplied by 3 when the other thread is modifying it. It also doesn't say that the other thread can't do it's operation, and then the result of fmulp is produced and a is stored with the value from that calculation.
(The above example applies to arrays too - I'm just making it REALLY simple)

You must MAKE SURE that you are never operating on the same data in two threads. If you walk through the same array from two different threads, you WILL not be sure which thread has gone how far - it may work the first two, three or hundred times you try it out. Then something changes (you add one more if-condition, another variable, or something else) and it breaks the whole thing. Or you run on a different model of processor where some particular operation is quicker, or ... I can go on for almost forever with possible scenarios - there are so many variables. There are only two safe options:
1. Your data is protected by some sort of lock (and locks are made safe by the fact that the processor has specific instructions that are safe in these places).
2. Your data is known to be clearly different locations.

--
Mats

If you don't use some type of lock in your code you stand the chance of introducing some very hard to find bugs.

Best bet is to ensure it cannot happen by using a lock mechanism rather than finding when and where you can get away with not locking. You will eventually get caught and therefore good coding practice would be to follow the multi thread guidelines as they have been laid out by others in this thread.

Using OpenMP, would this simple example be safe:

Code:

---

std::vector<int> arr(3000);
#pragma omp parallel for
for (int i = 0; i < 3000; i++)
{
    arr[i] = i;
}

---

...since only different indices will be written to at the same time?

From the MSDN help about vector thread safety:

Quote:

---

If a single object is being written to by one thread, then all reads and writes to that object on the same or other threads must be protected. For example, given an object A, if thread 1 is writing to A, then thread 2 must be prevented from reading from or writing to A.

---

...what is the "object" here, is it the whole vector or each item in the vector?

http://msdn.microsoft.com/en-us/libr...3b(VS.80).aspx

The whole vector.

gg

Quote:

---

Originally Posted by Codeplug

The whole vector.

gg

---

Are you sure? Why does it work that way for arrays then and not vector? From what I have read people are saying that vector is thread safe since all functions are synchronized, something like that.

I need a second opinion.

Quote:

---

Originally Posted by Codeplug

The whole vector.

---

I agree, except in the case where it is a vector of pointers. because you're not manipulating the data *in* the vector - just what it points to. I use this strategy in some of my code. I know it's not safe to directly manipulate data stored in a vector, so I allocate memory on the heap for my objects and store a pointer to the object in the vector. I can then pass that pointer to a thread procedure and read/write that object all I want.

It's the whole vector because the documentation says so. In reality, depending on the implementation, the thread safety might be the same as a simple dynamic array, i.e. element accesses are independent as long as you don't do something to the whole array. (Note that various operations on the vector can affect everything.)
However, this reality is implementation-dependent, and as long as the implementor doesn't guarantee independent element-wise access, you don't have it. MS talks of STL object in their threading guarantees, so you don't have the guarantee for individual objects.

However, the next standard guarantees that access to individual elements of any standard container does not conflict. See 23.1.2p2 in the current draft.

>> except in the case where it is a vector of pointers. because ...
You're referring to the thread safety of the objects within the container - not the container itself. Using invalidated references to container objects is bad with or without threads.

Since the C++03 standard doesn't address threading at all, any type of thread-safety within a standard library implementation has to be documented by the implementer. The above link to MSDN is the documentation for the MS implementation. It doesn't apply to anyone else's implementation. Here's STLport's documentation for example.

>> Are you sure?

Quote:

---

The following thread safety rules apply to the [MS] Standard C++ Library:
■ Container Classes and complex

The container classes are vector, deque, list, queue, stack, priority_queue, valarray, map, hash_map, multimap, hash_multimap, set, hash_set, multiset, hash_multiset, basic_string, and bitset.

A single object is thread safe for reading from multiple threads. For example, given an object A, it is safe to read A from thread 1 and from thread 2 simultaneously.

If a single object is being written to by one thread, then all reads and writes to that object on the same or other threads must be protected. For example, given an object A, if thread 1 is writing to A, then thread 2 must be prevented from reading from or writing to A.

It is safe to read and write to one instance of a type even if another thread is reading or writing to a different instance of the same type. For example, given objects A and B of the same type, it is safe if A is being written in thread 1 and B is being read in thread 2.

---

I don't see where the confusion is. It's obvious to me that the "objects A and B" refer to one of the listed container classes or complex.

gg

In an attempt to get quicker synchronization, I tried to implement a naive barrier system, using a busy wait, thinking that maybe not invoking system threading code would speed things up:

Code:

---


#include <utility>
#include <boost/thread.hpp>
#include <cmath>
#include <iostream>

const unsigned int lesize = 100000;
const unsigned int letime = 100000;
double v[lesize];
double u[lesize];

struct task
{
  enum state { running = 1, waiting = 0 };
  task(state & my_state, state & other_state, std::pair<unsigned int,unsigned int> interval) : me(my_state), it(other_state), r(interval) {}
  void operator()()
  {
        for(int t = 0; t < letime; ++t)
        {
          me = running;
          for(int i = r.first; i < r.second; ++i)
                u[i] = v[i-1] + v[i+1] - 2.0*v[i];
          me = waiting;
          while(it == running) /*nothing*/;
          me = running;
          for(int i = r.first; i < r.second; ++i)
                v[i] += 0.001 * u[i];
          me = waiting;
          while(it == running) /*nothing*/;
        }
  }
 private:
  state & me;
  state & it;
  std::pair<unsigned int,unsigned int> r;
};

int main()
{
  for(int i = 0; i < lesize; ++i)
        v[i] = std::sqrt( ((lesize+3)/2.0)*((lesize+3)/2.0) - (i-lesize/2.0)*(i-lesize/2.0) ); //semicircular arc, as initial condition
  boost::thread_group tg;
  task::state state1, state2;
  state1 = state2 = task::running;

  tg.create_thread( task(state1,state2, std::make_pair(1,lesize/2)) );
  tg.create_thread( task(state2,state1, std::make_pair(lesize/2, lesize-1)) );
  tg.join_all();
  std::cout << "Complete." << std::endl;
}

---

It hangs indefinitely. But why? Does constant checking block setting?
I posted a whole program so that you can run it without having to spend time.

>> But why?
You're not synchronizing access to state1 and state2. In general, when two threads access (read/write) the same memory location, synchronization is required. You have to use the synchronization primitives provided by the threading library.

gg