Understanding memory sequences and std::memory_order_relaxed

Question

I am studying C++ memory sequences, but it's very confusing.

For example:

void sumUp(std::atomic<int>& sum, std::vector<int>& val)
{
   int tmpSum = 0;
   for(auto i = 0; i < 100; ++i) tmpSum += val[i];

   sum.fetch_add(tmpSum, std::memory_order_relaxed);
}

I don't understand that sum.fetch_add() operates after tmpSum += val[i]. Since it is not in order, can sum.fetch_add() operate before tmpSum += val[i]?

So is the sum 0 possible?

Many thanks.

Answer 1

memory_order has no observable effect in the context of a single thread:

Let's see (x, a and b are initially 0):

auto t1(std::atomic<int>& x, int& a, int& b)
{
    a = 3;                                       // 1
    b = 5;                                       // 2
    x.store(a, std::memory_order_relaxed);       // 3
}

Because (1) and (2) are not dependent one on another, the compiler can reorder them. E.g. can do (1) -> (2) or (2) -> (1)

Because (3) depends on (1) ((1) writes to a and (3) reads from a) the compiler cannot do (3) before (1). This is regardless of what memory order is specified in (3)

Because (3) does not depend on (2), normally in a single-threaded model, the compiler could do (3) before (2).

But since x is atomic consider another thread doing this (x, a and b are references to the same arguments as provided to t1 and are all initially 0):

auto t2(std::atomic<int>& x, int& a, int& b)
{
    while(x.load(std::memory_order_relaxed) == 3)  // 4
        assert(b == 5);                            // 5
}

This thread waits until x is 3 and then asserts that b is 5. Now you can see how in a sequential single threaded world (2) and (3) can be reordered without any observable behavior, but in a multi threaded model, the order of (2) and (3) could have an impact on the behavior of the program.

This is what memory_order does: it specifies if operations that could have been reordered before or after the atomic without any effect on a single thread can be reordered as such or not. The reason is that they could have an effect on a multi-threaded program. The compiler cannot know this, only the programmer, hence the extra memory_order parameter.

With memory_order_relaxed the assert could fail because (2) could happen after (3), but with memory_order_seq_cst (default) the assert will never fail, because (2) happens before (3).

---

Coming back to your example, regardless of what memory_order you specify, it is guaranteed that tmpSum += val[i]; will happen before sum.fetch_add(tmpSum, std::memory_order_relaxed); because the second one depends on the first. The memory_order would affect the possible reordering of instructions that do not affect the atomic operations. E.g. if you would have had a int unrelated = 24.

---

Btw, the official terminology is "sequenced before" and "sequenced after"

---

In the real world hardware makes things are a bit more complicated. Operations can appear in one order in the current thread, but another thread can see them in another order, so stricter memory_orders have to employ extra measures to ensure consistent order across threads.

---

Strictly speaking in this example if using memory_order_relaxed we would have Undefined Behavior because the access to b is not synchronized across threads.