61

Stores are release operations and loads are acquire operations for both. I know that memory_order_seq_cst is meant to impose an additional total ordering for all operations, but I'm failing to build an example where it isn't the case if all the memory_order_seq_cst are replaced by memory_order_acq_rel.

Do I miss something, or the difference is just a documentation effect, i.e. one should use memory_order_seq_cst if one intend not to play with a more relaxed model and use memory_order_acq_rel when constraining the relaxed model?

4 Answers 4

57

http://en.cppreference.com/w/cpp/atomic/memory_order has a good example at the bottom that only works with memory_order_seq_cst. Essentially memory_order_acq_rel provides read and write orderings relative to the atomic variable, while memory_order_seq_cst provides read and write ordering globally. That is, the sequentially consistent operations are visible in the same order across all threads.

The example boils down to this:

bool x= false;
bool y= false;
int z= 0;

a() { x= true; }
b() { y= true; }
c() { while (!x); if (y) z++; }
d() { while (!y); if (x) z++; }

// kick off a, b, c, d, join all threads
assert(z!=0);

Operations on z are guarded by two atomic variables, not one, so you can't use acquire-release semantics to enforce that z is always incremented.

15
  • 2
    @acidzombie24, even in that case, z will be 2.
    – MSN
    Sep 10, 2012 at 20:40
  • 9
    @CandyChiu With ack_rel, c() can perceive that x=true; in a() happens before y=true; in b() at the same time d() can perceive that y=true; happens before x=true; (due to lack of "global ordering".) In particular c() can perceive x==true and y==false at the same time d() can perceive y==true and x==false. So z might not be incremented by either of c() or d(). With seq_cst, if c() perceives x=true; happens before y=true;, so does d().
    – nodakai
    Jan 20, 2016 at 11:03
  • 1
    @MSN You meant int z=0, not bool z=0
    – nodakai
    Jan 20, 2016 at 11:04
  • 2
    @nodakai, Your explanation is accurate but I think the phrase "happens before" can be misleading since the crux of the issue with acquire-release is that neither of the writes happens-before the other.
    – jhoffman0x
    May 1, 2018 at 3:50
  • 4
    This example is using pure loads and pure stores, not any actual RMW operations that could use std::memory_order_acq_rel. In an atomic read-modify-write, the load and store are tied together because they're an atomic. I'm not sure when if ever acq_rel can differ from seq_cst for something like .fetch_add or .compare_exchange_weak Nov 2, 2019 at 6:32
16

On ISAs like x86 where atomics map to barriers, and the actual machine model includes a store buffer:

  • seq_cst stores require flushing the store buffer so this thread's later reads are delayed until after the store is globally visible. (At least before the next seq_cst load, not necessarily before non-atomic or non-SC atomic loads or stores.)

    See below re: AArch64's hardware support for this; most other ISAs do just wait for the store buffer to drain after SC stores and RMWs. An alternate mapping from C++ to asm would be to drain the store buffer before each seq_cst load instead of after stores, but we want cheap loads even more than cheap stores. (Multiple cores can be loading the same object in parallel; stores necessarily cause contention to get exclusive ownership of the cache line.)

  • acquire or release do not have to flush the store buffer. Normal x86 loads and stores have essentially acq and rel semantics, making it free in x86 asm. (Each core's accesses to coherent cache happen in program order, except for a store buffer with store forwarding.)

    But x86 atomic RMW operations always get "promoted" to seq_cst because the x86 asm lock prefix is a full memory barrier. Other ISAs can do relaxed or acq_rel RMWs in asm, with the store side being able to do limited reordering with later stores or loads on other objects. (But not in ways that would make the RMW appear non-atomic: For purposes of ordering, is atomic read-modify-write one operation or two?)


https://preshing.com/20120515/memory-reordering-caught-in-the-act is an instructive example of the difference between a seq_cst store and a plain release store. (It's actually mov + mfence vs. plain mov in x86 asm. In practice xchg is a more efficient way to do a seq_cst store on most x86 CPUs, but GCC does use mov+mfence)


Fun fact: AArch64's LDAR acquire-load instruction is actually a sequential-acquire, having a special interaction with STLR. Not until ARMv8.3 LDAPR can arm64 do plain acquire operations that can reorder with earlier release and seq_cst stores (STLR). (seq_cst loads still use LDAR because they need that interaction with STLR to recover sequential consistency; seq_cst and release stores both use STLR).

With STLR / LDAR you get sequential consistency, but only having to drain the store buffer before the next LDAR, not right away after each seq_cst store before other operations. I think real AArch64 HW does implement it this way, rather than simply draining the store buffer before committing an STLR.

Strengthening rel or acq_rel to seq_cst by using LDAR / STLR doesn't need to be expensive, unless you seq_cst store something, and then seq_cst load something else. Then it's just as bad as x86.

Some other ISAs (like PowerPC) have more choices of barriers and can strengthen up to mo_rel or mo_acq_rel more cheaply than mo_seq_cst, but their seq_cst can't be as cheap as AArch64; seq-cst stores need a full barrier.

So AArch64 is an exception to the rule that seq_cst stores drain the store buffer on the spot, either with a special instruction or a barrier instruction after. It's not a coincidence that ARMv8 was designed after C++11 / Java / etc. basically settled on seq_cst being the default for lockless atomic operations, so making them efficient was important. And after CPU architects had a few years to think about alternatives to providing barrier instructions or just acquire/release vs. relaxed load/store instructions.

18
  • "But x86 atomic RMW operations always get promoted to seq_cst because the x86 asm lock prefix is a full memory barrier." What makes you say they are "promoted"? Also the exec could well speculatively load the value (normally) and do the computation as long as it reloads it safely (locked load) later; if the computation is fast that's probably uninteresting but still possible. (I suppose that these things are documented in a purely descriptive way by Intel for existing designs and not for future ones.)
    – curiousguy
    Nov 28, 2019 at 1:01
  • 1
    @curiousguy: But anyway, if a hypothetical implementation wanted to try loading early to set up for a cheaper atomic exchange to actually implement the RMW, it could only do that speculatively and roll back on mis-speculation (if the line changed before the load was architecturally allowed). Regular loads already work this way, to get performance while preserving strong load ordering. (See the machine_clears.memory_ordering performance counter: Why flush the pipeline for Memory Order Violation caused by other logical processors?) Nov 30, 2019 at 5:18
  • 2
    @PeterCordes - I don't even think it's hypothetical: I think that's how atomic operations are (sometimes) implemented on current Intel x86. That is, that they load the cache line in an optimistic locked state, do the "front end" of the RMW (including the ALU op), and then in the "back end" of the RMW they verify everything was OK in the execute-at-retire op that ensures all the ordering. This works great when the location is not contended. If this fails a lot, a predictor will switch modes to doing the whole thing at retire, which causes a bigger bubble in the pipeline (hence "sometimes").
    – BeeOnRope
    Nov 30, 2019 at 18:16
  • 1
    @DanielNitzan: An RMW is actually a load and a store; no operation to the same location can come between them (giving RMW atomicity), but ops on other locations can actually overlap. The store half has release semantics, and in some cases actually can reorder with a later store to another location. (Or with a later load, but the Q&A I linked shows an experiment using two stores.) May 12 at 16:48
  • 1
    @DanielNitzan: x86 doesn't have this effect; its RMWs are full memory barriers, so the load+store remain fully stuck together in the globally-visible order of the core's operations. (This is somewhat required by the LoadLoad and StoreStore ordering guarantees. If acq_rel RMWs existed on x86, the store side could reorder with later loads but not stores. But that's due to later stores being release ops themselves, the fact that x86 in general only allows StoreLoad reordering. Same for earlier stores but not loads reordering with the load side of a hypothetical acq_rel RMW on x86.) May 12 at 16:52
5

Try to build Dekkers or Petersons algorithm with just acquire/release semantics.

That won't work because acquire/release semantics doesn't provide [StoreLoad] fence.

In case of Dekkers algorithm:

flag[self]=1 <-- STORE
while(true){
    if(flag[other]==0) { <--- LOAD
        break;
    }
    flag[self]=0;
    while(turn==other);
    flag[self]=1        
}

Without [StoreLoad] fence the store could jump in front of the load and then the algorithm would break. 2 threads at the same time would see that the other lock is free, set their own lock and continue. And now you have 2 threads within the critical section.

2
  • "Without [StoreLoad] fence the store could jump in front of the load" In your code, you've marked a STORE that is already in front of a LOAD. Did you mean to say that the LOAD might be executed before the STORE?
    – dyp
    Dec 14, 2022 at 9:20
  • You are right. The load can jump in front of the store.
    – pveentjer
    Dec 14, 2022 at 11:15
4

Still use the definition and example from memory_order. But replace memory_order_seq_cst with memory_order_release in store and memory_order_acquire in load.

Release-Acquire ordering guarantees everything that happened-before a store in one thread becomes a visible side effect in the thread that did a load. But in our example, nothing happens before store in both thread0 and thread1.

x.store(true, std::memory_order_release); // thread0

y.store(true, std::memory_order_release); // thread1

Further more, without memory_order_seq_cst, the sequential ordering of thread2 and thread3 are not guaranteed. You can imagine they becomes:

if (y.load(std::memory_order_acquire)) { ++z; } // thread2, load y first
while (!x.load(std::memory_order_acquire)); // and then, load x

if (x.load(std::memory_order_acquire)) { ++z; } // thread3, load x first
while (!y.load(std::memory_order_acquire)); // and then, load y

So, if thread2 and thread3 are executed before thread0 and thread1, that means both x and y stay false, thus, ++z is never touched, z stay 0 and the assert fires.

However, if memory_order_seq_cst enters the picture, it establishes a single total modification order of all atomic operations that are so tagged. Thus, in thread2, x.load then y.load; in thread3, y.load then x.load are sure things.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.