Compare and swap C++0x

Question

From the C++0x proposal on C++ Atomic Types and Operations:

29.1 Order and Consistency [atomics.order]

Add a new sub-clause with the following paragraphs.

The enumeration memory_order specifies the detailed regular (non-atomic) memory synchronization order as defined in [the new section added by N2334 or its adopted successor] and may provide for operation ordering. Its enumerated values and their meanings are as follows.

• memory_order_relaxed

The operation does not order memory.

• memory_order_release

Performs a release operation on the affected memory locations, thus making regular memory writes visible to other threads through the atomic variable to which it is applied.

• memory_order_acquire

Performs an acquire operation on the affected memory locations, thus making regular memory writes in other threads released through the atomic variable to which it is applied, visible to the current thread.

• memory_order_acq_rel

The operation has both acquire and release semantics.

• memory_order_seq_cst

The operation has both acquire and release semantics, and in addition, has sequentially-consistent operation ordering.

Lower in the proposal:

bool A::compare_swap( C& expected, C desired,
        memory_order success, memory_order failure ) volatile

where one can specify memory order for the CAS.

---

My understanding is that “memory_order_acq_rel” will only necessarily synchronize those memory locations which are needed for the operation, while other memory locations may remain unsynchronized (it will not behave as a memory fence).

Now, my question is - if I choose “memory_order_acq_rel” and apply compare_swap to integral types, for instance, integers, how is this typically translated into machine code on modern consumer processors such as a multicore Intel i7? What about the other commonly used architectures (x64, SPARC, ppc, arm)?

In particular (assuming a concrete compiler, say gcc):

1. How to compare-and-swap an integer location with the above operation?
2. What instruction sequence will such a code produce?
3. Is the operation lock-free on i7?
4. Will such an operation run a full cache coherence protocol, synchronizing caches of different processor cores as if it were a memory fence on i7? Or will it just synchronize the memory locations needed by this operation?
5. Related to previous question - is there any performance advantage to using acq_rel semantics on i7? What about the other architectures?

Thanks for all the answers.

Answer 1

The answer here is not trivial. Exactly what happens and what is meant is dependent on many things. For basic understanding of cache coherence/memory perhaps my recent blog entries might be helpful:

• CPU Reordering – What is actually being reordered?
• CPU Memory – Why do I need a mutex?

But that aside, let me try to answer a few questions. First off the below instruction is being very hopeful as to what is supported.

compare_swap( C& expected, C desired,
        memory_order success, memory_order failure )

Architectures won't all be able to implement this exactly as you requested. When you specify memory_order you are specifying how reordering may work. To use intel's terms you will be specifying what type of fence you want, there are three of them, the full fence, load fence, and store fence. Just because you want a particular fence on that operation won't mean it is supported, in which I'd hope it always falls back to a full fence.

The compiler will likely use the CMPXCHG instructuion to implement the call. If you have specified something other than relaxed it will mark this with lock to indicate the function should be atomic. Whether this is "lock-free" depends very much on what you are thinking about in terms of a "lock.

In terms of memory sync you need to understand how cache-coherence works (my blog may help a bit). New CPUs use a ccNUMA architecture (previously SMP). Essentially the "view" on the memory never gets out-of-sync. The fences used in the code don't actually force any flushing to happen per-se. If two cores both have the same memory location cached in a cache-line, one will get marked dirty and the other will reload as necessary. A very simple explanation for a very complex process

To answer your last question you should always use the memory semantics that you logically need to be correct. Most architectures won't support all the combinations you use in your program. However, in many cases you'll get great optimizations, especially in cases where the order you requested is guaranteed without a fence (which is quite common).

-- Answers to some comments:

You have to distinguish between what it means to execute a write instruction and write to a memory location. This is what I attempt to explain in my blog post. By the time the "0" is committed to 0x100, all cores see that zero. Writing integers is also atomic, that is even without a lock, when you write to a location all cores will immediately have that value if they wish to use it.

The trouble is that to use the value you have likely loaded it into a register first, any changes to the location after that obviously won't touch the register. This is why one needs mutexes despite a cache coherent memory.

As to contradictory claims, generally you'll see all sorts of claims. Whether they are contradictory comes right down to exactly what "see" "load" "execute" mean in the context. If you write "1" to 0x100, does that mean you executed the write instruction or did the CPU actually commit that value. The difference comes from the reordering. The CPU can delay writing the "1", but you can be sure that the moment it does finally commit that "1" all cores see it. The fences control this ordering.