What does this compare_exchange_weak example loop do, on atomic boolean, from a talk about the difference between weak and strong?

Question

This is referencing the slide at 37:00 in this CppCon lecture here: https://youtu.be/DS2m7T6NKZQ

While the presenter is talking about the difference between compare_exchange_swap_strong and compare_exchange_swap_weak in the case of spurious failures, the following code is provided as an example use case. The question might be a bit frivolous because it isn't really about the main talking point, but I am trying to understand lock-free algorithms better.

bool expected = false;
extern atomic_bool b; // set somewhere else
while(!b.compare_exchange_weak(expected, true) && !expected);

I don't understand the use case with compare exchange swap here. If the atomic boolean b is false when we enter the while loop, the compare_exchange_swap_weak will return true and set b to be true, and then we break out of the while loop (assuming the cas_weak does not fail spuriously here).

If the atomic boolean b is true when we enter the while loop, the compare_exchange_swap_weak will return false and set expected to true. Then !expected will be false, and we break out of the while loop.

However, if the value of b is false when we enter the while loop, and the cas operation DOES fail spuriously, then we keep looping.

So it seems like the purpose of this code is to set the value of b to true if it is false in a lock_free manner. Unless I am misunderstanding something, couldn't we just do something like b.store(true) in practice?

Answer 1

I think this is as a try_lock() function, where b is the spinlock. Exit after taking the lock, or after one non-spurious failure. Or it's an emulation of compare_exchange_strong (which you should use instead for cases like this.)

It's simplified / compacted for the purpose of cramming it into a slide; in real cases you'd probably use different code that could distinguish success from non-spurious failure more easily and clearly! But I think in this code, we can just return !expected as the lock-taking success status.

 extern atomic_bool b; // set somewhere else 

  bool expected = false;
  while(!b.compare_exchange_weak(expected, true) && !expected);

The three cases are:

• CAS succeeds, loop exits without checking the value of expected. while(false && ...).
  This is success in acquiring ownership of the loop, we can enter the critical section.
• CAS fails, expected = true. Loop exits; while(!false && !true);
  This is non-spurious failure: the CAS saw a value other than false as the current value of b.
• CAS fails, expected = false. Loop keeps looping; while(!false && !false);
  This is spurious failure: keep retrying (with expected = false) until either of the above conditions.

The loop can only keep looping while expected = false because of the second condition, which also avoids the problem of doing a CAS(true,true) and "succeeding" when another thread holds the lock. You couldn't use this loop for a plain lock() function that kept spinning until getting the lock (without the !expected check); you'd have to reset expected = false inside a do{}while() loop.

---

An unconditional store of b = true; wouldn't tell us about the old state. We could use tmp = b.exchange(true).

.exchange() also requires a loop in asm for LL/SC machines (the same ones where CAS_weak is different from CAS_strong), and it's an unconditional store. So does .fetch_add and every other RMW atomic.

The reason compare_exchange_weak exists is that CAS itself is often used in retry loops, e.g. to synthesize arbitrary atomic RMW operations, like atomically right-shifting. If you are going to retry the loop any time CAS fails, it doesn't matter whether it was spurious or not, so using CAS_weak lets the compiler make simpler code.

But if you only want to make one CAS attempt, like in some algorithms such as try_lock() or various other cases, you should use compare_exchange_strong instead of writing your own loop.