Talk:cpp/atomic/atomic/compare exchange

atomic stack push discussion

Original example (based on chapter 7 of C++ Concurrency in Action and common knowledge):

node<T>* new_node = new node<T>(data);
new_node->next = head.load(std::memory_order_relaxed);
while(!head.compare_exchange_weak(new_node->next,
                                  new_node,
                                  std::memory_order_release,
                                  std::memory_order_relaxed));

Per User:Duncan.forster, "Using newNode->next is bad because if another thread is removing items then newNode is now being shared between threads." Proposed example:

node<T>* new_node = new node<T>(data);
node<T>* old_head = (new_node->next = head.load(std::memory_order_relaxed));
while(!head.compare_exchange_weak( old_head
                                 , new_node
                                 , std::memory_order_release
                                 , std::memory_order_relaxed))
{
      new_node->next = old_head;
}

Leaving this discussion open for analysis, I don't see how the canonical push() fails regardless of how badly pop() is written (incidentally, we should post a pop() since that's a good use case for compare_exchange_strong) --Cubbi (talk) 08:20, 15 February 2014 (PST)

The important thing to remember is that the hardware implementation of CAS only returns 1 value (the old value) not two (old plus boolean). The boolean result that C++ returns is calculated after the CAS has occurred and is outside the atomic zone (which is where races live). IMHO the C++ interface is broken by design. Here's some code to try and explain:

#include <stdio.h>
#include <thread>
 
template<typename _T>
bool atomic_bool_compare_and_swap(_T *value, _T& expected, _T new_value)
{
    _T old_value;
 
    // Here be atomic
    {
        old_value = *value;
        if(old_value == expected)
            *value = new_value;
    }
 
    // Here be race conditions
    return (old_value == expected);
}
 
// Implementation not important (completely atomic)
template<typename _T>
_T atomic_exchange(_T *value, _T new_value) 
{ 
    _T old_value; 
 
    // Here be atomic
    {
        old_value = *value;
        *value = new_value;
    }
 
    return old_value;
} 
 
template<typename _T>
struct Node
{
    _T data;
    Node* next;
};
 
 
template<typename _T>
class Queue
{
    Node<_T>* head = nullptr;
 
public:
    void push(const _T& data)
    {
        Node<_T>* new_node = new Node<_T>;
        new_node->data = data;
        new_node->next = head;
        while(!atomic_bool_compare_and_swap(&head, new_node->next, new_node))
                ;
        printf("Push[%d]\n", data);
    }
    Node<_T>* pop_all_reversed()
    {
        Node<_T>* old_head = atomic_exchange(&head, (Node<_T>*)0);
        return old_head;
    }
};
 
int main(int argc, char** argv)
{
    Queue<int> queue;
 
    auto push = [&queue]()
    {
        queue.push(1);
        queue.push(2);
        queue.push(3);
        queue.push(4);
    };
    auto pop = [&queue]()
    {
        Node<int>* next = queue.pop_all_reversed();
        while(next)
        {
            Node<int>* current = next;
            printf("Pop[%d]\n", current->data);
            next = current->next;
 
            // Here be race conditions 
            current->next = nullptr;
            delete current;
        }
    };
 
 
    //Note: If these threads run concurrently bad things may happen
    std::thread push_thread(push);     
    push_thread.join();
 
    std::thread pop_thread(pop); 
    pop_thread.join();
 
    return 0;
}

--Duncan.Forster (talk) 21:15, 15 February 2014 (PST)

I see what you mean now. Looks like an implementation bug to me. Brought up at Stackoverflow for exposure --Cubbi (talk) 03:38, 19 February 2014 (PST)

I believe a good exposition would be to post the classic example (which shows how it is intended to work), but commented out, and accompanied by a comment saying that due to implementation bugs such as clang bug 18899 and GCC bug 60272, workaround is needed. And when those are fixed, perhaps switch the example.--Cubbi (talk) 06:39, 20 February 2014 (PST)

Seems reasonable to me. --Nate (talk) 16:14, 20 February 2014 (PST)

confusing / incorrect wording in the return value section

This:

"true if the underlying atomic value was changed, false otherwise."

if false for the return value. It returns true if the expected value is equal to the underlying atomic value - i.e. the return value is:

"false if the underlying atomic value was changed, true otherwise."

...or I misinterpret what is meant by "the underlying atomic value was changed"

Either way this is either wrong or confusing.

92.231.33.37 14:06, 10 November 2015 (PST) Thomas Gahr

See the second example. The underlying atomic variable is ai. It gets changed only when tst_val == ai, and that's when true is returned. --Bear (talk) 14:30, 10 November 2015 (PST)

'expected' is updated if changed

In the documentation of 'expected', please add a note saying that it will be updated in case the value did not match. 95.35.214.34 22:22, 23 April 2020 (PDT)

Done. — Radix (talk) 15:12, 24 April 2020 (PDT)

Explanation is way too complicated to understand

Thank goodness for Cplusplus.com's easy explanation (https://cplusplus.com/reference/atomic/atomic/compare_exchange_strong/):

> Compares the contents of the contained value with expected:

> - if true, it replaces the contained value with val (like store).

> - if false, it replaces expected with the contained value .

Or I would never understand what this means:

> 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).

Please consider de-obfuscating overly-complex explanations so cppreference.com can be more-understandable, like cplusplus.com is.

ERCaGuy (Gabriel Staples) (talk) 16:36, 30 August 2022 (PDT)