Namespaces
Variants
Views
Actions

Talk:cpp/atomic/atomic/compare exchange

From cppreference.com

[edit] 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)