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;
};

Morwenn · Accepted Answer · 2014-03-21 15:39:58Z

4

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}
{
    // ...
}

edited Mar 21, 2014 at 15:39

answered Mar 21, 2014 at 14:05

Morwenn

20.2k3 gold badges69 silver badges132 bronze badges

1

\$\begingroup\$ 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. \$\endgroup\$

Bob65536
– Bob65536

2014-03-21 18:13:54 +00:00
Commented Mar 21, 2014 at 18:13
\$\begingroup\$ @Bob65536 But now you say it, it makes sense. And it's true that you already check for a power of 2 :) \$\endgroup\$

Morwenn
– Morwenn

2014-03-21 18:22:16 +00:00
Commented Mar 21, 2014 at 18:22

Add a comment |

BillFu · Accepted Answer · 2020-09-17 14:12:40Z

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.

edited Sep 17, 2020 at 14:12

answered Sep 17, 2020 at 13:49

BillFu

212 bronze badges

Add a comment |

Stack Exchange Network

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

2 Answers 2

You must log in to answer this question.

Hot Network Questions

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

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions