C ++ 26: A lock-free stack with nuclear smart pointer

In my previous blog post, I showed the complete implementation of a lock-free stack, which still had a memory leak. This time I show the approach to remove it.

Advertisement

Nuclear smart indicator

There are two ways to get atomic operations on one std::shared_ptr Apply: C ++ in 11, can do free nuclear function std::shared_ptr used. With C ++ 20, atomic smart pointers can be used.

C ++ 11

Use of nuclear operations std::shared_ptr Tired and prone to errors. You can easily forget nuclear operations and everything is possible. The following example shows a lock-free stack that is available std::shared_ptr based.

// lockFreeStackWithSharedPtr.cpp

#include 
#include 
#include 
#include 
#include 

template
class LockFreeStack {
 public:
    struct Node {
        T data;
        std::shared_ptr next;
    };
    std::shared_ptr head;
 public:
    LockFreeStack() = default;
    LockFreeStack(const LockFreeStack&) = delete;
    LockFreeStack& operator= (const LockFreeStack&) = delete;
   
    void push(T val) {
        auto newNode = std::make_shared();
        newNode->data = val;
        newNode->next = std::atomic_load(&head);                                       // 1
        while( !std::atomic_compare_exchange_strong(&head, &newNode->next, newNode) ); // 2
    }

    T topAndPop() {
        auto oldHead = std::atomic_load(&head);                                       // 3
        while( oldHead && !std::atomic_compare_exchange_strong(&head, &oldHead, std::atomic_load(&oldHead->next)) ) {     // 4
            if ( !oldHead ) throw std::out_of_range("The stack is empty!");
        }
        return oldHead->data;
    }
};
   
int main(){

    LockFreeStack lockFreeStack;
    
    auto fut = std::async((&lockFreeStack){ lockFreeStack.push(2011); });
    auto fut1 = std::async((&lockFreeStack){ lockFreeStack.push(2014); });
    auto fut2 = std::async((&lockFreeStack){ lockFreeStack.push(2017); });
    
    auto fut3 = std::async((&lockFreeStack){ return lockFreeStack.topAndPop(); });
    auto fut4 = std::async((&lockFreeStack){ return lockFreeStack.topAndPop(); });
    auto fut5 = std::async((&lockFreeStack){ return lockFreeStack.topAndPop(); });
    
    fut.get(), fut1.get(), fut2.get();
    
    std::cout << fut3.get() << '\n';
    std::cout << fut4.get() << '\n';
    std::cout << fut5.get() << '\n';

}

Webframework: Astro accelerates the rendering of 5.3 websites

This implementation of the lock-free stack is similar to the previous implementation without storage recovery. The main difference is that data type nodes std::shared_ptr Are. All operations std::shared_ptr Become a atom using free atomic operations std::load (1) And (4) and std::atomic_compare_exchange_strong (2) and (3). Atomic operation requires an indicator. I would like to emphasize that in the reading operation of the next node oldHead->next (4) There should be a atom, there oldHead->next Can be used by other threads.

Finally, the program follows here.

Let’s jump in future for nine years and use C ++ 20.

C ++ 20

C ++ 20 supports partial expertise std::atomic For std::shared_ptr And std::weak_ptrThe following implementation connects the nodes of lock-free stack into one std::atomic<:shared_ptr>> One.

// lockFreeStackWithAtomicSharedPtr.cpp

#include 
#include 
#include 
#include 
#include 

template
class LockFreeStack {
 private:
    struct Node {
        T data;
        std::shared_ptr next;
    };
    std::atomic<:shared_ptr>> head;           // 1
 public:
    LockFreeStack() = default;
    LockFreeStack(const LockFreeStack&) = delete;
    LockFreeStack& operator= (const LockFreeStack&) = delete;
   
    void push(T val) {                              // 2
        auto newNode = std::make_shared();
        newNode->data = val;
        newNode->next = head;
        while( !head.compare_exchange_strong(newNode->next, newNode) );
    }

    T topAndPop() {
        auto oldHead = head.load();
        while( oldHead && !head.compare_exchange_strong(oldHead, oldHead->next) ) {
            if ( !oldHead ) throw std::out_of_range("The stack is empty!");
        }
        return oldHead->data;
    }
};
   
int main(){

    LockFreeStack lockFreeStack;
    
    auto fut = std::async((&lockFreeStack){ lockFreeStack.push(2011); });
    auto fut1 = std::async((&lockFreeStack){ lockFreeStack.push(2014); });
    auto fut2 = std::async((&lockFreeStack){ lockFreeStack.push(2017); });
    
    auto fut3 = std::async((&lockFreeStack){ return lockFreeStack.topAndPop(); });
    auto fut4 = std::async((&lockFreeStack){ return lockFreeStack.topAndPop(); });
    auto fut5 = std::async((&lockFreeStack){ return lockFreeStack.topAndPop(); });
    
    fut.get(), fut1.get(), fut2.get();
    
    std::cout << fut3.get() << '\n';
    std::cout << fut4.get() << '\n';
    std::cout << fut5.get() << '\n';

}

The main difference between the previous and this implementation is that the node in one std::atomic<:shared_ptr>> Is embedded (1). As a result, the member creates function push (2) one std::shared_ptr And call head.load() In the member ceremony topAndPop Gives one to one std::atomic<:shared_ptr>> Back.

Here is the version of the program:

std::atomic<:shared_ptr/> Not a lock-free

I stood openly with nuclear operation on one in previous programs std::shared_ptr And one std::atomic Cheated. These atomic operations on one std::shared_ptr Currently there are no lock-free. In addition, implementation std::atomic Use a winding mechanism to use all partial and complete expertise std::atomic For support.

Celebration atom.lock_free() For one std::atomic<:shared_ptr>> Gives false Back.

 // atomicSmartPointer.cpp
 
#include 
#include 
#include 

template 
struct Node {
    T data;
    std::shared_ptr next;   
};

int main() {    

    std::cout << '\n';

    std::cout << std::boolalpha;

    std::atomic<:shared_ptr>>> node;
    std::cout << "node.is_lock_free(): "  << node.is_lock_free() << '\n';

    std::cout << '\n';

}

What will happen next?

So we are back in the beginning and take care of storage management in our next article.

(RME)