# Difference between revisions of "Talk:cpp/atomic/atomic/compare exchange"

m (bug IMO btw) |
m (Reverted edits by Cubbi (talk) to last revision by Duncan.forster) |
||

Line 132: | Line 132: | ||

}} | }} | ||

--[[User:Duncan.forster|Duncan.Forster]] ([[User talk:Duncan.forster|talk]]) 21:15, 15 February 2014 (PST) | --[[User:Duncan.forster|Duncan.Forster]] ([[User talk:Duncan.forster|talk]]) 21:15, 15 February 2014 (PST) | ||

− | |||

− |

## Revision as of 19:08, 19 February 2014

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