Lockless Queue Multiple-Reader Singler-Writer in C++

Question

I wrote a lockless queue for sending small objects from a single thread to a random worker thread.

Assumptions:

• x86/x86_64 compiled with GCC
• one thread may Write(), multiple threads may Read()
• notifying a thread that data is available is done elsewhere
• T is copy assignable and sizeof(T) is small
• N is a power of two

Any suggestions welcome.

//RnW1FifoFixed.h
#pragma once
#include <memory>
//multiple reader single writer first in first out fixed length ring buffer queue
//compatible with x86/x86_64 GCC
template<typename T,uint32_t N> class RnW1FifoFixed
{
private:
 const uint32_t MASK = 2*N-1;
public:
 RnW1FifoFixed()
 :m_array(new T[N]),m_read(0),m_write(0)
 {
 static_assert(std::is_default_constructible<T>::value,"T does not have a default constructor.");
 static_assert(std::is_copy_assignable<T>::value,"T does not support copy assignment.");
 static_assert(N!=0,"N is too small.");
 static_assert(N!=0x80000000,"N is too large.");
 static_assert((N&(N-1))==0,"N is not a power of two.");
 }
 //one thread
 bool Write(T t)
 {
 //full
 if(m_write-m_read==N)
 return false;
 m_array[m_write&MASK] = t;
 //CPU does not reorder writes
 //prevent compiler from reordering writes
 asm volatile("":::"memory");
 m_write++;
 return true;
 }
 //multiple threads
 bool Read(T& t)
 {
 while(true)
 {
 //use a constant m_read each loop
 uint32_t read = m_read;
 //empty
 if(read==m_write)
 return false;
 t = m_array[read&MASK];
 if(__sync_bool_compare_and_swap(&m_read,read,read+1))
 return true;
 }
 }
private:
 std::unique_ptr<T[]> m_array;
 uint32_t m_read;
 uint32_t m_write;
};

Answer 1

This line seems really strange to me:

static_assert(N!=0x80000000,"N is too large.");

Technically, it is rather odd to just compare for equality with one big number where there could be numbers even bigger. Didn't you mean:

static_assert(N >= 0x80000000, "N is too large.");

---

const uint32_t MASK = 2*N-1;

Since all the values in this line are known at compile time and MASK is apparently not meant to be changed, you should consider making it both static and constexpr:

static constexpr uin32_t MASK = 2*N-1;

---

That's kind of trivial, but you can also use curly braces instead of parenthesis in your constructor initialization list:

RnW1FifoFixed():
 m_array{new T[N]},
 m_read{0},
 m_write{0}
{
 // ...
}

• Bob65536: I chose N!=0x80000000 because it is the largest power of two that can fit in a uint32. Larger values will fail the power of two test. I agree though that N>=0x80000000 is much more clear. Thanks for the suggestions.
• Morwenn: @Bob65536 But now you say it, it makes sense. And it's true that you already check for a power of 2 :)

Answer 2

Two comments. First you can move the assignment down a bit to save some work.

while(true)
{
 //use a constant m_read each loop
 uint32_t read = m_read;
 //empty
 if(read==m_write)
 return false;
 if(__sync_bool_compare_and_swap(&m_read,read,read+1)) 
 {
 t = m_array[read&MASK]; 
 return true;
 }
}

Second, if you declare m_read as volatile, or std::atomic, the first read in the while loop

uint32_t read = m_read;

would not be optimized with cached value, before the barrier in the CAS.