Understand std::atomic::compare_exchange_weak() in C++11

This originates from an SO question.

Background

compare-and-swap (CAS) is an atomic instruction used in multithreading which serves as one of the building blocks to achieve synchronization. C++11 supports this atomic operation on language level to help us write portable multithreaded code that run on all platforms that are standard-compliant.

For what CAS is, wikipedia has a good article on it. In short, it loads the value from memory, compares it with an expected value, and if equal, store a predefined desired value to that memory location. The important thing is that all these are performed in an atomic way, in the sense that if the value has been changed in the meanwhile by another thread, CAS will fail.

CAS in C++11

// memory ordering is irrelevant to our discussion here
bool compare_exchange_weak (T& expected, T desired, ..);
bool compare_exchange_strong (T& expected, T desired, ..);

When expected equals to the real value that object holds, it returns true and desired value is written to memory. Otherwise, expected will be overwritten by the actual value in memory and false is returned. This is almost true except for one exception: the weak version will return false even if the value of the object is equal to expected, which won’t be synced with the value in memory in this case.

Spurious Failure

This is due to spurious failure on some platforms where a sequence of instructions (instead of one as on x86) are used to implement it. On such platforms, context switch, reloading of the same address (or cache line) by another thread, etc. can fail the primitive. It’s spurious as it’s not the value of the object (not equal to expected) that fails the operation. Instead, it’s kind of timing issue. On the contrary, the strong version conceptually wraps this around and tries in case of any spurious failure.

Why does compare_exchange_weak() have to be in a Loop in Nearly All Uses?

C++11 § 29.6.5
A consequence of spurious failure is that nearly all uses of weak compare-and-exchange will be in a loop.

Typical Pattern A

You need achieve an atomic update based on the value in the atomic variable. A failure indicates that the variable is not updated with our desired value and we want to retry it. Note that we don’t really care about whether it fails due to concurrent write or spurious failure. But we do care that it is we that make this change.

expected = current.load();
do desired = function(expected);
while (!current.compare_exchange_weak(expected, desired));

A real-world example is for several threads to add an element to a singly linked list concurrently. Each thread first loads the head pointer, allocates a new node and appends the head to this new node. Finally, it tries to swap the new node with the head.

Another example is to implement mutex using std::atomic<bool>. At most, one thread can enter the critical section at a time, depending on which thread first set current to true and exit the loop.

Typical Pattern B

This is actually the pattern mentioned in Anthony’s book. Contrary to pattern A, you want the atomic variable to be updated once, but you don’t care who does it. As long as it’s not updated, you try it again. This is typically used with boolean variables. E.g., you need implement a trigger for a state machine to move on. Which thread pulls the trigger is regardless.

expected = false;
// !expected: if expected is set to true by another thread, done!
// Otherwise, it fails spuriously and we should try again.
while (!current.compare_exchange_weak(expected, true)
       && !expected);

Note that we generally cannot use this pattern to implement a mutex. Otherwise, multiple threads may be inside the critical section at the same time.

That said, it should be rare to use compare_exchange_weak() outside a loop. On the contrary, there are cases that the strong version is in use. E.g.,

bool criticalSection_tryEnter(lock)
{
  bool flag = false;
  return lock.compare_exchange_strong(flag, true);
}

compare_exchange_weak() is improper here because when it returns due to spurious failure, it’s likely that no one occupies the critical section yet.

Starving Thread?

One point worth mentioning is that what happens if spurious failures continue to happen thus starving the thread? Theoretically, it could happen on platforms when compare_exchange_XXX() is implemented as a sequence of instructions (e.g., LL/SC). Frequent access of the same cache line between LL and SC will produce continuous spurious failures. A more realistic example is due to a dumb scheduling where all concurrent threads are interleaved in the following way.

Time
 |  thread 1 (LL)
 |  thread 2 (LL)
 |  thread 1 (compare, SC), fails spuriously due to thread 2's LL
 |  thread 1 (LL)
 |  thread 2 (compare, SC), fails spuriously due to thread 1's LL
 |  thread 2 (LL)
 v  ..

Can it happen?

It won’t happen forever, fortunately, thanks to what C++11 requires:

§ 29.6.5
Implementations should ensure that weak compare-and-exchange operations do not consistently return false unless either the atomic object has value different from expected or there are concurrent modifications to the atomic object.

Why Bother to Use compare_exchange_weak() and Write the Loop Ourselves? Why Not Compare_exchange_strong()?

It depends.

Case 1: When both need to be used inside a loop. C++11 says:

§ 29.6.5
When a compare-and-exchange is in a loop, the weak version will yield better performance on some platforms.

On x86 (at least currently). Maybe it’ll resort to a similar scheme as LL/SC one day for performance when more cores are introduced), the weak and strong version are essentially the same because they both boil down to the single instruction cmpxchg. On some other platforms where compare_exchange_XXX() isn’t implemented atomically (here meaning no single hardware primitive exists), the weak version inside the loop may win the battle because the strong one will have to handle the spurious failures and retry accordingly.

But,

rarely, we may prefer compare_exchange_strong() over compare_exchange_weak() even in a loop. E.g., when there are a lot of things to do between atomic variable is loaded and a calculated new value is exchanged out (see function() above). If the atomic variable itself doesn’t change frequently, we don’t need repeat the costly calculation for every spurious failure. Instead, we may hope that compare_exchange_strong() “absorb” such failures and we only repeat calculation when it fails due to a real value change.

Case 2: When only compare_exchange_weak() need to be used inside a loop. C++11 also says:

§ 29.6.5
When a weak compare-and-exchange would require a loop and a strong one would not, the strong one is preferable.

This is typically the case when you loop just to eliminate spurious failures from the weak version. You retry until exchange is either successful or failed because of concurrent write.

expected = false;
// !expected: if it fails spuriously, we should try again.
while (!current.compare_exchange_weak(expected, true)
       && !expected);

At best, it’s reinventing the wheels and perform the same as compare_exchange_strong(). Worse? This approach fails to take full advantage of machines that provide non-spurious compare-and-exchange in hardware.

Last, if you loop for other things (e.g., see “Typical Pattern A” above), then there is a good chance that compare_exchange_strong() shall also be put in a loop, which brings us back to the previous case.