C++11 lock free stack

Question

I'm reading C++ Concurrency in Action by Anthony Williams, and don't understand its push implementation of the lock_free_stack class.

Why on earth the atomic load is not in the while loop ? The reason he gave is:

You therefore don’t have to reload head each time through the loop, because the compiler does that for you.

But I don't get the picture. Can someone shed some light on this?

template<typename T>
class lock_free_stack
{
private:
 struct node
 {
   T data;
   node* next;
   node(T const& data_) : 
     data(data_)
   {}
 };
 std::atomic<node*> head;
public:
 void push(T const& data)
 {
   node* const new_node=new node(data); 
   new_node->next=head.load(); 
   while(!head.compare_exchange_weak(new_node->next,new_node)); 
 }
};

Mcgannon

Answer 1

The key is in the interface to compare_exchange_weak, which in this case takes 2 arguments. The first is a reference to the expected value, and the second is the desired. If the current value of the atomic is not equal to the expected input, it will return false and the expected input is set to the current value.

So in this case, what it's doing is setting new_node->next = head. Then, it's saying if head is still equal to new_node->next, swap it into head. If it's no longer that value, it uses the reference to new_node->next to assign it the current value of head. Since every iteration of the loop that fails also replaces new_node->next with the current value of head, there is no read to duplicate that in the body of the loop.

Situate

Yes, it makes perfect sense now. Thanks! – Mcgannon

Answer 2

From the documentation of compare_exchange_weak:

Atomically compares the value stored in *this with the value of expected, and if those are equal, replaces the former with desired (performs read-modify-write operation). Otherwise, loads the actual value stored in *this into expected (performs load operation).

As you see, otherwise the actual value of head is loaded into expected.

Impeller