A toy example of the concurrent stack via atomic variables and CAS pattern

Question

I've written a toy example of the concurrent stack which has only three functions push(), peek(), and length(). I've used atomic variables for synchronization. Is there anything incorrect in terms of synchronization? Could you please review this code?

#include <iostream>
#include <thread>
#include <atomic>
#include <vector>

template <typename T>
struct Node {
    Node<T>* next{};
    T val{};
    Node(const T& v) : val(v) {};
};

template <typename T>
class Stack {
    std::atomic<Node<T>*> top{};
    std::atomic<size_t> size{};
    public:
    void push(const T& data) {
        Node<T>* node = new Node<T>(data);
        size_t length = size.load(std::memory_order_relaxed);
        node->next = top.load(std::memory_order_relaxed);
        while(!std::atomic_compare_exchange_weak_explicit(&top, &node->next, node, std::memory_order_release, std::memory_order_relaxed));
        while(!std::atomic_compare_exchange_weak_explicit(&size, &length, size + 1, std::memory_order_release, std::memory_order_relaxed));
    }
    Node<T>* peek() {
        return top.load();
    }
    size_t length() const {
        return size;
    }
};

template <typename T>
class Runner {
    int cnt{};
    Stack<T>* ss{};
    public:
        Runner(const int n, Stack<T>* s) : cnt(n), ss(s) {}
        void operator()() {
            for(int i = 0; i < cnt; ++i) {
                size_t size = ss->length();
                if(size >= cnt) {
                    return;
                }
                ss->push(i);
            }
        }
        Stack<T>* get_stack() const {
            return ss;
        }
};

int main() {
    std::vector<std::thread> threads{};
    Stack<int>* s = new Stack<int>();
    int n = 10;
    Runner<int> r(n, s);
    for(int i = 0; i < 3; ++i) {
        threads.push_back(std::move(std::thread(r)));
    }
    for(int i = 0; i < 3; ++i) {
        threads[i].join();
    }
    Stack<int>* top = r.get_stack();
    Node<int>* head = top->peek();
    while(head) {
        std::cout << head->val << ", ";
        head = head->next;
    }
    size_t size = top->length();
    return 0;
}

Answer 1

Naming

My immediate reaction is that without a pop (or something equivalent) it's not really a stack. Especially given the item below about exposing the implementation details, from a client's viewpoint it's really a linked list that supports only a couple of operations: adding nodes to the beginning, getting the length, and (by knowing the implementation) traversing the list.

Exposing Internal Details

As it stands now, it seems to rely on client code to realize that it's implemented as a linked-list, so access to elements other than the top require client code to use peek to get a pointer to the top element, and then traverse the nodes of the linked list to get to the rest of the elements.

Avoiding Race Conditions

I'd also question (to at least some degree) inclusion of length in the interface. In a multi-threaded environment, almost all possible uses of length are practically guaranteed to introduce race conditions--by the time you actually try to use a length you've read, the length may have changed, so you're using obsolete information.

It can (at least sort of) make some sense to use a length for things like logging, simply to give the user at least some notion of whether the stack is (for example) growing constantly (but in this case, that's pretty much a given, since you've omitted a pop from its interface).

Side Note

It's not immediately apparent whether you're thinking of Runner as part of the Stack itself, or an ancillary class you included to demonstrate/test the actual Stack. At least for now, I've treated it as ancillary, so it shows how the Stack is used, but I haven't really tried to review it in itself.

Answer 2

To add to Jerry Coffin's answer:

Move struct Node into class Stack

A Node is just an implementation detail of a Stack, so move the declaration of the former into the latter. As a bonus you avoid having to repeat <T>. Here is how this looks:

template <typename T>
class Stack {
public:
    struct Node {
        Node* next{};
        T val{};
        Node(const T& v): val(v) {};
    };

private:
    std::atomic<Node*> top{};
    ...
};

While I agree with Jerry Coffin that you should have a proper pop() instead of a peek(), using the latter would now look like this:

Stack<int>::Node* head = top->peek();

Although you should just use auto here:

auto head = top->peek();

Don't forget to clean up memory

I see new in your code but no delete. That means you have a memory leak. Normally I would recommend you use std::unique_ptr<> to manage memory, but since you are using atomic pointers, that doesn't work. So ensure you add destructors to Node and Stack so that the resources are cleaned up correctly.

And in main(), there is no reason to use new to create a new Stack, just declare it on... the stack:

Stack<int> s;
Runner<int> r(n, &s);

Use emplace_back()

In the following line, the move() is unnecessary:

threads.push_back(std::move(std::thread(r)));

This is because std::thread(r) is a temporary, and thus the overload of push_back() that takes an r-value reference will be chosen. However, even better is to use emplace_back(), as then you can simply write:

threads.emplace_back(r);