# Single producer single consumer command queue

I needed to create commands simply with lambda and execute it in another thread. The following code works fine. Any suggestions about performance are appreciated.

I want to use SSE aligned variables as lambda captures, for instance:

__m128 xmm0;
queue.Enqueue([xmm0](){
//...
});


template<unsigned MaxCommand = 1000> class TCommandQueueSPSC
{
static const unsigned MaxLambdaSize = sizeof(void*) * 7;

struct alignas(16) ICMD
{
virtual ~ICMD() {}
};
struct alignas(16) CMDBase : ICMD
{
char mBuffer[MaxLambdaSize];
};
static_assert(sizeof(CMDBase) % 16 == 0, "should be 16 aligned");
static const unsigned CMDSize = sizeof(CMDBase);

alignas(64) volatile unsigned       mHead = 0;
volatile bool                       mRuning = false;
Event                               mWaitEvent;
alignas(64) volatile unsigned       mTail = 0;
alignas(64) CMDBase                 mElements[MaxCommand];

bool IsEmpty() const { return mHead == mTail; }
bool IsFull() const { return ((mTail + 1) % MaxCommand) == mHead; }

void* BeginEnqueue()
{
UASSERT(!IsFull()); //assert if full
return mElements + mTail;
}
void EndEnqueue()
{
mTail = (mTail + 1) % MaxCommand;
}

ICMD* BeginDequeue()
{
if (mHead == mTail) return nullptr;
}
void EndDequeue()
{
}

public:
TCommandQueueSPSC(const TCommandQueueSPSC&) = delete;
TCommandQueueSPSC& operator = (const TCommandQueueSPSC&) = delete;

TCommandQueueSPSC() : mWaitEvent(false, false) {}

template<typename Lambda> void Enqueue(const Lambda& proc)
{
{
proc();
return;
}

struct NewCMD : public ICMD
{
Lambda mProc;
NewCMD(const Lambda& p) : mProc(p) {}
~NewCMD()
{
mProc();
}
};
static_assert(sizeof(NewCMD) <= CMDSize, "");
static_assert(alignof(NewCMD) <= alignof(ICMD), "");
void* cmd = BeginEnqueue();
new (cmd) NewCMD(proc);
EndEnqueue();
}
template<typename Lambda> void EnqueueAndWait(const Lambda& proc)
{
{
proc();
return;
}

struct NewCMD : public ICMD
{
Lambda mProc;
TCommandQueueSPSC*  mOwner;
NewCMD(const Lambda& p, TCommandQueueSPSC* owner) : mProc(p), mOwner(owner) {}
~NewCMD()
{
mProc();
mOwner->mWaitEvent.SetSignaled();
}
};
static_assert(sizeof(NewCMD) <= CMDSize, "");
static_assert(alignof(NewCMD) <= alignof(ICMD), "");
void* cmd = BeginEnqueue();
new (cmd) NewCMD(proc, this);
EndEnqueue();

mWaitEvent.Wait();
}
void RunTillQuit()
{
mRuning = true;

while (mRuning)
{

if (ICMD* cmd = BeginDequeue())
{
cmd->~ICMD();
EndDequeue();
}
else
{
_mm_pause();
}
}
}
void Quit() { mRuning = false; }
volatile bool IsRuning() const { return mRuning; }
};

• You should note that volatile isn't a replacement for std::atomic, even not with bool values. – πάντα ῥεῖ Jan 10 '17 at 17:59
• yes, but currently that works perfect for me on MSVC. I think atomic has more overhead than volatile, :( however after googling I realized that my code needs some memorybarrier to work fine in other compilers too – UPO33 Jan 10 '17 at 18:44

# Order of public, protected, private

This is a personal preference but one that I find makes code easier to read. I always order my fields as: public then protected then private with the motivation that the person using the class is interested in seeing the public API and this should thus be the first thing you see so that you don't have to search for it.

# Misuse of volatile

C++ (and C) has a thing called the "as-if rule". Which in essence says:

The compiler is allowed to generate ANY code as long as all reads and writes to volatile memory happens in the same order and with the same values as if the program was execute according to the language specification.

This is the only use volatile has in C++, it means that writes and writes to volatile memory will always happen and will happen in the order specified. For example the compiler can, and frequently does re-order stores and writes. The compiler can remove memory writes and reads if it can determine that they will not affect any volatile memory read or write. The compiler can even remove memory allocations if it so pleases (clang does this some times).

For completeness, all inputs and outputs (files, std::cout, std::cin, std::cerr, std::clog, keyboard drivers, graphics display, sound buffers, networks packets) are volatile either directly or transitively. So the compiler cannot remove inputs or outputs of the program, but anything in-between basically.

### When should I use volatile then?

Volatile should be used when you must be certain that a certain write or read is not removed by the compiler as dead. For example when you are writing a hardware driver, you would set control variables that must be written to some bus as volatile.

### But volatile works for synchronising my threads just fine!

That is pure luck that it is working on your compiler. The compiler is allowed to change the order of reads and writes AROUND your volatile accesses as long as they don't affect the values of the volatile accesses. Also the CPU may or may not re-order some stores or loads depending on the CPU (x86 has a conveniently strict memory model which only has one case where memory accesses may complete out of order).

What you need is a memory barrier. A memory barrier forces both the compiler to generate code in such a way that all writes before the barrier happens before the barrier and tells the CPU to make sure all writes before the barrier has happened before the barrier completes. The above is a bit simplified, there are different memory types of barriers which say what must be completed before the barrier completes. If you're interested, see std::memory_order.

### Does volatile affect my performance?

Yes, the compiler can do quite some fancy optimisations with re-ordering stores and loads and instructions so that they will effectively use the CPU's registers and to make sure that multiple issue kicks in on some CPUs. By using volatile you are prohibiting the compiler from doing some of these optimisations as you are forcing it to emit a read or write in a specific order.

In summary, don't use volatile unless you're absolutely sure that you need it.

# Over-aligning basic types

You specify:

alignas(64) volatile unsigned       mHead = 0;
volatile bool                       mRuning = false;
Event                               mWaitEvent;
alignas(64) volatile unsigned       mTail = 0;
alignas(64) CMDBase                 mElements[MaxCommand];


The compiler is required to store members of a struct or class in the order they are specified in the definition. And it is also required to respect the requested alignment. So the above code will form a structure in memory that looks something like this (depending on platform, unsigned is at least 16 bits but most often 32 bits):

Byte offset  Value
4           mRunning
Padding to respect basic alignment of mWaitEvent which believe is 4
8-?         mWaitEvent (I don't know how big it is)
Padding to make sure mTail starts on 64 byte boundary.
64-67       mTail
68-71       mConsumerThreadID (should be 32 bits)
72-127 Padding to make sure mElements start on a 64 byte boundary.
128 - 64127  mElements (assuming 64 bit binary)

Note that as CMDBase has alignas(16) and the structure is MaxLamdaSize = 8*7 = 56 bytes it has to be rounded up to the nearest multiple of 16 which is 64, so each CMDBase will occupy 64 bytes in that array.


Compare the above to the following:

unsigned       mHead = 0;
unsigned       mTail = 0;
Event          mWaitEvent;
bool           mRuning = false;
CMDBase        mElements[MaxCommand];

Byte offset  Value
4-7         mTail
14-21(?)    mWaitEvent (I don't know how big it is, assuming 8 bytes now)
22          mRuning
32 - 6431   mElements (assuming 64 bit binary)


Notice how the struct is 90 bytes shorter just by re-arranging the order of the members and removing the useless padding. Looking at it from a relative point of view 90 bytes out of 64127 is less than 0.2% storage reduction but that is not the point. Typically CPUs have a cache line that is 64 bytes long, i.e. the CPU can cache data in batches of 64 bytes. In this later variation all of the control variables fit in one cache line, where in your original code you needed two cache lines to hold the control variables, leaving less cache lines for the rest of the data.

Further more the alignment of data doesn't affect performance in any way as long as the data is aligned so that the CPU doesn't have to do an unaligned load (as long as you don't get an unaligned load but standard alignment requirements in C++ prevent this automatically).

Alignment is only useful to guarantee that hardware which requires a certain alignment can function and when you want to avoid false sharing. For example SSE instructions require 16 byte alignment on their loads. Don't just go randomly sprinkling alignas in your code. It will HURT your performance.

# Enough about conceptual misunderstandings and on to the code

So it looks like you have implemented a circular buffer. I recommend that you break out the circular buffer into it's own class and then use that in implementing your command queue. This will make your code clearer and easier to read. It will also make it possible to re-use the circular buffer.

Don't use the destructor to run the code like you do here:

       ~NewCMD()
{
mProc();
}


If the lamda throws then you might have problems on your hands as destructors throwing exceptions is kind of a bad situation throwing from destructor. Not to mention that destructors are only for destroying the object, releasing any resources held and cleaning up.

Further since you're not removing the commands from the queue, when your application shuts down the mElements array will be destructed and each of the destructors on the elements will be executed again. Do I need to say this is bad? Not to mention that you never remove the objects from the queue when you're done with them.

I feel that you are overworking this in an effort to make it fast but in practice you're introducing problems and not actually improving speed. If you want your lamda to be 16 byte aligned so that your captures will work then just say so.

alignas(16) struct AlignedFunction{
std::function<void(void)> function;
};

std::queue<AlignedFunction> mElements;

template<typename Callable>
void enqueue(Callable&& callable){
mElements.emplace_back([](){callable();});
}


# Don't preemptively optimise

Have you measured your application and have hard evidence that this command queue is the bottleneck of your application? If not you're just wasting time and creating bugs trying to write this complex class. I recommend that you take a simpler approach using standard library algorithms and functions and model the behaviour you want. If at a later point you get profiling data that points out this class as a bottle neck, then you can optimise.

# In summary

I see that you are trying a lot of tricks that you think will improve performance. In reality these do no improve your performance, in fact I'd be willing to wager that you are in fact hurting your performance instead. Not only that but they are making the code hard to read and hard to work with.

Stop trying to be clever, you are hurting yourself. Write clean, maintainable code instead. The compilers today are pretty darn good when it comes to generating good code. Most likely they are way better than you are.

• thanks a lot for your help especially about mElements, I didn't notice it. I think I care about performance too much. – UPO33 Jan 11 '17 at 17:16
• @UPO33 Performance comes mainly from choosing the right algorithm, the right data structure and paralleling computations (SIMD or threads). Rarely will these kind of tricks (volatile, and alignas) improve your performance. Also if you improve the performance of something that is 2% of your actual run time by 10%, you have only achieved a 0.2% improvement in your total performance... Think about that for a moment. Caring about performance is good, optimising the right place is gold. And how do you know the right spot? You profile, you measure and you analyse. – Emily L. Jan 11 '17 at 18:18

I agree with most of what @Emily L. commented, all good comments. The only exception is for the mHead and mTail padding/false sharing case. If the use scenario is to have two threads on different cores, it makes sense to have them in different cache lines to avoid false sharing in theory. Of course, profile and measurement in real run is the best way to check the performance.