Why can relaxed operation be reordered? Doesn't program order imply happens-before?-CodePudding

In the book C Concurrency in Action, when introducing relaxed ordering, the author says:

Relaxed operations on different variables can be freely reordered provided they obey any happens-before relationships they’re bound by

but in this page on cppreference, it gives an example about relaxed ordering

// Thread 1:
r1 = y.load(std::memory_order_relaxed); // A
x.store(r1, std::memory_order_relaxed); // B
// Thread 2:
r2 = x.load(std::memory_order_relaxed); // C 
y.store(42, std::memory_order_relaxed); // D

is allowed to produce r1 == r2 == 42 because, although A is sequenced-before B within thread 1 and C is sequenced before D within thread 2, nothing prevents D from appearing before A in the modification order of y, and B from appearing before C in the modification order of x. The side-effect of D on y could be visible to the load A in thread 1 while the side effect of B on x could be visible to the load C in thread 2. In particular, this may occur if D is completed before C in thread 2, either due to compiler reordering or at runtime.

My question is: C is sequenced-before D in thread2 thus C is also happens-before D, right?

Does the reordering of operation D and C contradict with what says in the book, that relaxed operations can be reordered but must obey happens-before relationships? In what conditions can relaxed operations be reordered?

CodePudding user response：

This is a common misunderstanding. It is true that load C happens before store D. That is not saying that C has to actually be executed, or become visible, before D.

At the end of the day, the only relevance of the happens-before relation, or any other element of the memory model, is what it tells you about what your program will actually do (its observable behavior). And that is ultimately dictated by what values are returned by your loads. The happens-before relation provides such information in three ways:

the coherence rules explained on the page you link (write-write, read-write and so on),
in telling you whether or not you have a data race
via the "visible side effect" rule. (cppreference misstates that rule: it phrases it in terms of modification order, but it is meant to apply to non-atomic variables which in C 20 do not have a modification order.)

All of those rules are ultimately based on knowing whether or not you have a happens-before relationship between two reads or writes of the same variable.

So since C and D are accesses to different variables, the only reason that we would care whether one happens before the other is if we can use that fact as part of a longer chain of reasoning, to eventually deduce a happens-before (or a "does not happen before") between two accesses to the same variable. In the program at hand, we have no way to do that. The statement that C happens before D is true but completely useless, and so it does not in any way restrict the compiler / machine from reordering how C and D are actually executed or made visible.

In understanding relations such as happens before, dependency-ordered before, etc, it is best to be guided by the actual formal definitions, and not by your intuition about what their names seem to imply. The names are just names.