C++ lock free, single producer, single consumer queue Assumptions for use:


push() will only ever be called by a single thread.
pop() will only ever be called by a single thread.


Requirements:

push() needs to be as fast as possible. Requirements are stringent enough that I've determined that I can't use std::mutex (at least not in any way I've attempted to) as it is far too slow. (some initial stress tests took 6-8 ms without and 26-60 ms with std::mutex)

Code:

template&lt;typename T&gt;
class PCQueue {
    const size_t size;
    std::unique_ptr&lt;T[]&gt; contents;
    std::atomic&lt;size_t&gt; head;
    std::atomic&lt;size_t&gt; tail;
public:
    explicit PCQueue(size_t s) : size(s), contents(new T[s]), head(0), tail(0) {}

    //num of elements in ringbuffer (size - room())
    size_t count() {
        return (tail + size - head) % size;
    }

    //num of free spaces in ringbuffer (size - count())
    size_t room() {
        return (head + size - tail) % size;
    }

    void push(T t) {
        size_t newTail = (tail + 1) % size;
        if (newTail == head) {
            throw std::runtime_error("Pushing Full PCQueue");
        }
        contents[tail] = t;
        tail = newTail;//std::atomic implicitly memfences, so this op must occur after the "contents[tail] = t;"
    }

    T pop() {
        if (tail == head) {
            throw std::runtime_error("Popping Empty PCQueue");
        }
        T ret = contents[head];
        size_t newHead = (head + 1) % size;
        head = newHead;
        return ret;
    }
};


My testing has implied that this performs correctly (but I'd like to squeeze more speed out of it if possible), but I'm not entirely certain my assumption about the push method is correct (the comment regarding memory barriers), as I'm still getting a handle on those, and I'm not sure I understand how loads and stores can be reordered regarding atomic and non-atomic variables, with the various memory orders.  sequential consistency (the default) should enforce the desired behavior I think?

I'm worried that it's just working by coincidence (as concurrent code has a tendency to do), so a verification that my code is valid would be appreciated, as well as any general tips to improve it both in readability and performance.
Design

The problem with your implementation of pop() is that it can not be implemented in an exception safe manner (for any type of T). This is why the standard implementation implements this as two different methods top() and pop(). The top() function simply returns the value while pop() does not return the value but simply removes the value from head.

So usage would become:

T val = queue.top();
queue.pop();


Code Review

Your code assumes that T has a default constructor.

    std::unique_ptr&lt;T[]&gt; contents;


When you create the content with contents(new T[s]) you are allocating and initializing all the elements in that array using the default constructor.

In addition to this if T is very expensive you have just used a lot of effort to create the items that may never be used (or you wasted resources creating the objects that are just going to be destroyed when overwritten).

I would consider changing this to std::vector&lt;T&gt;. That way you don't create any un-required objects when first created.



This is fine:

    explicit PCQueue(size_t s) : size(s), contents(new T[s]), head(0), tail(0) {}


But you can make it more readable. Remember the point of code is to make the code maintainable.

    explicit PCQueue(size_t s)
        : size(s)
        , contents(new T[s])
        , head(0)
        , tail(0)
    {}




Is this the real definition of the function?

    //num of elements in ringbuffer (size - room())
    size_t count() {
        return (tail + size - head) % size;
    }


I would rename this function to reflect what the function is actually returning. I would also change the formula so it is easy to read. I would call this availableSpace(). The formula is: size - (head - tail).



This would be better named freeSpace().

    //num of free spaces in ringbuffer (size - count())
    size_t room() {
        return (head + size - tail) % size;
    }




You pass the parameter by value.

    void push(T t) {


This causes a copy to be made to pass it to the parameter. You should pass this by const reference (so there is no copy). If you want to get more advanced you could also pass by r-value reference which would allow you to move the object into your buffer rather than copying it.

    void push(T const&amp; t) {   // Pass by const reference
    void push(T&amp;&amp; t) {        // Pass by r-value reference




The problem with the pop() as written you can not guarantee a clean removal. This is because you need to make several copies and if those copies fail you can leave the container in a bad state.

    T pop() {
        T ret = contents[head];              // Here is a copy.
        size_t newHead = (head + 1) % size;  
        head = newHead;
        return ret;                          // Here is another copy. 
    }


You did not define T so you don't have control over the copy assignment constructor. That is why it is usually split into two functions.

    // Return by reference
    // That way we can avoid any un-needed copies.
    T const&amp; top() const {
        return contents[head];
    }
    // Simply remove the head item in the pop.
    void pop() {
        size_t newHead = (head + 1) % size;  
        head = newHead;
    }