6
\$\begingroup\$

Here is a classical attempt to implement a lock-free stack (based on this article). I rewrote it in C++11 and also tried to add memory orders which I would like to confirm to be correct.

template<typename T>
class stack 
{
    struct node_t final 
    {
        T value;
        node_t *next;
    };

    struct head_t final 
    {
        uintptr_t aba;
        node_t *node;
        head_t() noexcept :aba(0),node(nullptr)
        {}
        head_t(node_t* ptr) noexcept :aba(0),node(ptr)
        {}
    };

    static_assert(sizeof(head_t) == 2*sizeof(uintptr_t), "Stack head should be 2 pointers size.");

    typedef typename std::aligned_storage<sizeof(node_t), std::alignment_of<node_t>::value>::type aligned_node_t;

    std::unique_ptr<aligned_node_t[]> buffer_ptr;
    node_t *node_buffer;
    char cache_padding_1_[64 - sizeof(node_t*)];
    std::atomic<head_t> head;
    char cache_padding_2_[64 - sizeof(std::atomic<head_t>)];
    std::atomic<head_t> free_nodes;
    char cache_padding_3_[64 - sizeof(std::atomic<head_t>)];

public:

    stack(size_t capacity)
    {
        head.store( head_t(), std::memory_order_relaxed );
        // preallocate nodes
        buffer_ptr.reset(new aligned_node_t[capacity]);
        node_buffer = reinterpret_cast<node_t*>(buffer_ptr.get());
        for(size_t i = 0; i < capacity - 1; ++i)
        {
            node_buffer[i].next = &node_buffer[i + 1];
        }
        node_buffer[capacity-1].next = nullptr;
        free_nodes.store( head_t(node_buffer), std::memory_order_relaxed );
    }

    template<class U>
    bool push(U && data)
    {
        node_t *node = _pop(free_nodes);
        if (node == nullptr)
            return false;
        node->value = std::forward<U>(data);
        _push(head, node);
        return true;
    }

    bool pop(T& data)
    {
        node_t *node = _pop(head);
        if (node == nullptr)
            return false;
        data = std::move(node->value);
        _push(free_nodes, node);
        return true;
    }

private:
    node_t* _pop(std::atomic<head_t>& h)
    {
        head_t next, orig = h.load(std::memory_order_relaxed);
        do {
            if (orig.node == nullptr)
                return nullptr;
            next.aba = orig.aba + 1;
            next.node = orig.node->next;
        } while (!h.compare_exchange_weak(orig, next,
                                        std::memory_order_acq_rel,
                                        std::memory_order_acquire));
        return orig.node;
    }

    void _push(std::atomic<head_t>& h, node_t* node)
    {
        head_t next, orig = h.load(std::memory_order_relaxed);
        do {
            node->next = orig.node;
            next.aba = orig.aba + 1;
            next.node = node;
        } while (!h.compare_exchange_weak(orig, next,
                                        std::memory_order_acq_rel,
                                        std::memory_order_acquire));
    }
};
\$\endgroup\$
  • \$\begingroup\$ This implementation looks good to me so far. The 2*ptr atomic swaps with the aba field should prevent the problems you were having with the first version. I still wonder if you really need all this complicated code vs either a lock/mutex version or a non-LIFO version. \$\endgroup\$ – JS1 Jun 19 '15 at 23:40
  • \$\begingroup\$ @JS1 yeah this is definitely overhead :) would be great if you could look at unordered version i posted in old question with Gist link. thanx. \$\endgroup\$ – inspirit Jun 19 '15 at 23:43
  • \$\begingroup\$ I just looked at your unordered version on Gist. That one seems correct and a lot simpler than these other versions. \$\endgroup\$ – JS1 Jun 20 '15 at 0:00
  • \$\begingroup\$ Whats the source for those memory order specifiiers? Not saying they are wrong, just wonder whether they have to be analysed too, or if we just have to check whether they are correctly copied from a correct source. \$\endgroup\$ – MikeMB Jun 20 '15 at 20:23
  • \$\begingroup\$ @MikeMB if you look into original article the author did not use any memory orders. I tried to figure out them myself. but since here we use Double Width CAS operation most likely it doesnt matter what order we specify it will always be full memory barrier \$\endgroup\$ – inspirit Jun 20 '15 at 22:20
1
\$\begingroup\$

The general push/pop logic of the stack looks fine. The memory management however is somewhat flawed:

Missing Destructor

From the perspective of the unique ptr, the stack doesn't contain Nodes, but uninitialized memory (effectively a char array). So at destruction of the stack object, it won't call the destructor of the individual nodes, which in turn won't call the destructor of value.

In order to correct that, one could write a destructor for stack that traverses the nodes and manually calls the destructor on them.

Assignment into uninitialized variables

node->value = std::forward<U>(data);

Upon construction, no actual nodes are created, but only properly aligned memory is reserved, on which you later call the assignment operator. I believe (although I'm not sure) this is OK if T is a POD, but if not, then (move) assigning values to them is definitively not allowed, because custom move assignment operators usually assume that this points to a valid, initialized object.

So in general, I see two possibilities:

  1. You default construct all nodes upon construction of the stack and destruct them when stack is destructed, in which case std::aligned_storage is unnecessary. One can just use an array of nodes and pass it to the unique_ptr. In this case you also don't need a destructor for stack. Obviously that only works with default constructable T's and makes only sense, if T doesn't hold any resources after it has been moved from.

  2. You actually create and delete objects upon calls to push and pop, in which case you have to use placement new (new(&node->value)T(std::forward<U>(data));) and manually call the destructor node->value.~T() (not delete &node->value)

Padding
I just want to point out that aside from the false sharing between head and free_nodes, which is avoided via padding, any thread calling push or pop will access both variables anyway and afterwards you still have false sharing between the actual nodes.

Performance
This code contains a lot of micro optimizations, which might or might not be worth the effort if the code gets reused in different contexts (its definitively not worth for handling a worker pool). However, I'd suggest, to write at least few small benchmarks to ensure that those optimizations are in fact improving and not hurting performance.

Also I want to repeat my warning from the comments that for some reason, VS2013 (and also 2015RT) seems to be unable to implement std::atomic<head_t> in a lock-free manner, in which case the whole structure is probably much slower than a normal stack with a mutex.

\$\endgroup\$
  • \$\begingroup\$ agree about memory management: it is now do not support non POD types. regarding Padding -- it is totally required, without padding performance drops by 30%. really surprised MSVC still can't interpret head_t as 128Bit number :( \$\endgroup\$ – inspirit Jul 1 '15 at 20:41
  • \$\begingroup\$ 30% in your application or 30% in a benchmark that does nothing but push and pop on the stack? Anyway, I didn't think it would have that much of an impact. Good you checked. Concerning VS I'm pretty disappointed myself. I wonder if this is a bug, a misconfiguration on my side, or if there are actual technical challenges to overcome. \$\endgroup\$ – MikeMB Jul 1 '15 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.