Don't really get the logic of std::atomic::compare_exchange_weak and compare_exchange_strong

Question

I've read https://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange

Atomically compares the object representation (until C++20)value representation (since C++20) of *this with that of expected, and if those are bitwise-equal, replaces the former with desired (performs read-modify-write operation). Otherwise, loads the actual value stored in *this into expected (performs load operation).

So as I understand the code like

bool expected=true;
extern atomic<bool> b = false; 
void foo ()
{
//
    while(!b.compare_exchange_weak(expected, false));
//
}

after the loop will run once(ignoring spurious failure) it will fail, and will write to expected false, so on the second iteration compare_exchange_weak will return success, though b hasn't been changes to true. But what's the point of all this? I though I could use this as a lock for synchronization, waiting for other thread to change b, but now I can't think of a usage of this.

Example from the cppreference also shows that after two calls compare_exchange_strong will succeed.

#include <atomic>
#include <iostream>
 
std::atomic<int>  ai;
 
int  tst_val= 4;
int  new_val= 5;
bool exchanged= false;
 
void valsout()
{
    std::cout << "ai= " << ai
          << "  tst_val= " << tst_val
          << "  new_val= " << new_val
          << "  exchanged= " << std::boolalpha << exchanged
          << "\n";
}
 
int main()
{
    ai= 3;
    valsout();
 
    // tst_val != ai   ==>  tst_val is modified
    exchanged= ai.compare_exchange_strong( tst_val, new_val );
    valsout();
 
    // tst_val == ai   ==>  ai is modified
    exchanged= ai.compare_exchange_strong( tst_val, new_val );
    valsout();
}

Result:

ai= 3  tst_val= 4  new_val= 5  exchanged= false
ai= 3  tst_val= 3  new_val= 5  exchanged= false
ai= 5  tst_val= 3  new_val= 5  exchanged= true

Deaton

Does this answer your question? Understanding std::atomic::compare_exchange_weak() in C++11 – Banditry

compare_exchange gives you transaction style of synchronization. If transaction fails recalculate result and try submit it again. – Fimbria

@Banditry no, there is no explanation where and for what it std::atomic::compare_exchange should be used – Deaton

"I really don't get [it] ... what's the point of all this?" may be too broad a question to get the particular answer you are looking for. Are you asking for a real-world example? – Yellow

@DrewDormann yes, I don't really understand for now what's the usage and point of his – Deaton

The non-matched value is returned to you in case you're interested to know, but apparently you are not. So just ignore it. while(!b.compare_exchange_weak(expected = true, false));. – Banditry

That's not a particularly helpful example -- it's pointless when there's only a single thread modifying the value. When you have multiple threads you can use this to avoid data races. – Jereme

Best explanation of difference between those two I know. – Fimbria

Answer 1

I will give an example where I did used that, since it is very simple one.

I had atomic which describes available size of something. There was a danger of integer overflow, so I had do checking first before subtracting a value.

Not exact copy paste of my production code:

class LockFreeCuncuretSizeLimit {
public:
    explicit LockFreeCuncuretSizeLimit(size_t available) : mSize{available}
    {}

    bool tryAcuqire(size_t s) {
        size_t lastSize = mSize;
        size_t newSize;
        do
        {
            if (lastSize >= s)
            {
                newSize = lastSize - s;
            }
            else
            {
                return false;
            }

        }
        while (!mSize.compare_exchange_weak(lastSize, newSize));
        return true;
    }

    void release(size_t s) {
        mSize += s; // here I do not have worry about integer overflow
    }
private:
    std::atomic<size_t> mSize;
};

Now try image do that without compare_exchange_strong and not having a race condition.

There is a change that condition is meet, but when subtraction is done on atomic some other thread already subtracted a value so when I do actual subtraction it is possible to overflow integer. So this cant be done without compare_exchange_strong.

Now difference between compare_exchange_strong and compare_exchange_weak is hard to explain. Even Herb Sutter on some cppcon talk give up explaining that and provided simple rule: "if you need loop use compare_exchange_weak otherwise use compare_exchange_strong".

Fimbria

So imagine other thread have changed mSize after in current thread lastSize was initialized. When we reach while (!mSize.compare_exchange_strong(lastSize, newSize)); it will fail, lastSize will be updated with the new, changed from other thread value of mSize and on the next iteration will assign mSize with newSize. I still don't understand the meaning of this :( – Deaton

This is transaction synchronization. Like in databases, but on small objects. compare_exchange_strong is attempt to commit transaction. If commit fails since input value was changed this code loops again, recalculates new result and then tries to commit updated value. – Fimbria

Try imagine two threads running in parallel same lines of code. All values will be same until mSize.compare_exchange_strong is reached. In this place those two threads will fork thier behavior since compare_exchange_strong will return true only for one thread. – Fimbria

so for me it seems that in the end one of this thread's newSize will override another's one – Deaton

compare_exchange_strong will return true only for one thread. - but you have a loop, and on the second loop iteration it will return true – Deaton

@Deaton Did you miss that it is a do{...} while loop, not just a while loop? If the exchange fails then a new value for newSize is calculated based on what lastSize actually is before trying again. – Poussin

oh, yes, sorry! Now it makes sense! – Deaton

@Deaton in described scenario yes, in second iteration of loop second thread will calculate new value and next call of compare_exchange_strong will succeeds since there is no competing thread. – Fimbria

I'm really confused by your last line. Surely within a loop is the time to use weak. And outside of a loop you must use strong. Can you link me to the Herb talk?! – Guarino

@MikeVine probably it's a typo and it should be vice versa – Deaton

@Deaton thats what I would expect, but his actual example uses a loop and strong, so I was worried he'd (or I'd) misunderstood something. – Guarino

@MikeVine Not sure if this is correct talk youtu.be/c1gO9aB9nbs but this comes to my mind first when I think about this. – Fimbria

@MikeVine Ok I've found it youtu.be/CmxkPChOcvw?t=477 you were right should be vice versa so I corrected my answer. – Fimbria

CAS_weak vs. _strong is easy to explain if you know about hardware that provides atomics via an LL/SC primitive, unlike x86. CAS_weak can be implemented as one LL/SC attempt, that can spuriously fail if another thread writes or maybe even reads anything in the same cache line (or larger region monitored) between the LL and SC. CAS_strong requires an LL/SC retry loop. That's the practical difference on real-world ISAs. – Aubry

The spelling errors in your code are distracting. tryAcuqire should be tryAcquire. LockFreeCuncuretSizeLimit should be LockFreeConcurrentSizeLimit – Aubry

This is a fetch_sub but only if it won't wrap past zero. Yeah, that's a useful application for CAS, rather than actually over-shooting and correcting, because this avoids other threads ever seeing a negative (or huge unsigned) value. – Aubry

Answer 2

std::atomic::compare_exchange_weak performs this English-language task, in a thread-aware way:

Because the variable holds expected, it should now hold desired.

As a trivial task, imagine that the value of your std::atomic<int> x should be squared. But other threads may be modifying it, so you can't simply read the value, square it and write the new value back. The value may have changed after you read it!

Here is a thread-safe way to perform this task. You are guaranteed that the stored value will be replaced with its square.

int expected = x;
while( !x.compare_exchange_weak(expected, expected*expected) ) {}

This code will atomically replace expected with its square unless the value has changed.

If the value has changed, expected is now updated with the new value and the code tries again.

Yellow

Thank you for your great example! I wish I could mark two answers as accepted :( – Deaton