8
\$\begingroup\$

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;
};
\$\endgroup\$
4
\$\begingroup\$

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}
{
    // ...
}
\$\endgroup\$
  • 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 Mar 21 '14 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 Mar 21 '14 at 18:22

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.