# One reader / one writer no-memory-allocation lock-free ring-buffer

I have two threads - one thread queues items another thread dequeues. dequeue is fast enough and so we can assume that queue is never contains more than 65536 items.

C++ doesn't contain "ring-buffer." Boost has one, but it doesn't allow "reuse" of elements. So I wrote my own ring-buffer, which I think is very fast and requires no memory allocation. The code below has not been tested but it should show the general idea.

Do you find my code fine? Can you suggest how I can improve it or if there's something I can use instead of it? #include #include #include

#include <chrono>

template<class T> class ArrayPool
{
public:
ArrayPool() {
};

~ArrayPool(void) {
};

bool IsEmpty() {
}

T* TryGet()
{
{
return NULL;
}
return result;
}

T* Obtain() {
}

void Commit()
{
// Ensure storage is written before mask is incremented ?
// insert memory barrier ?
++curWriteNum;
if (curWriteNum - curReadNum > length)
{
std::cout <<
"ArrayPool curWriteNum - curReadNum > length! " <<
curWriteNum << " - " << curReadNum << " > " << length << std::endl;
}
}

void ObtainAndCommit(T* val) {
// copy constructor will likely be slower cause every field is copied
// storage[curWriteNum & MASK] = *val;
Commit();
}

private:
static const uint32_t length = 65536;
static const uint32_t MASK = length - 1;
T storage[length];

// curWriteNum must be volatile because access from both
// curReadNum don't need to be volatile because accessed
volatile uint32_t curWriteNum;
};

struct myStruct {
int value;
};

ArrayPool<myStruct> pool;

myStruct* entry;
while(true) {
while ((entry = pool.TryGet()) != NULL) {
std::cout << entry->value << std::endl;
}
}
}

std::chrono::milliseconds dura(1000 * id);

myStruct* storage = pool.Obtain();
storage->value = id;
pool.Commit();
std::cout << "Commited value! " << id << std::endl;
}

int main( void )
{
for (int i = 0; i < 100; i++) {
}
return 0;
}

• because of currWriteNum/curReadNum overflow you have a dependency on the ring size being a power of 2. You should write length in those terms or add a comment about the dependency. – Martin York Jan 8 '14 at 21:39
• Should an answer assume that you don't want to detect buffer overruns, because they're "impossible" or "undefined" or "not supported", for example because of scheduling or data-flow constraints in the threads which use this class? – ChrisW Jan 13 '14 at 14:13
• @ChrisW of course. question is not about "rare" conditions. When someone will be wrong I can dig and fix. Question about "general scenario". Let's make this code working under "normal, assumed" conditions. – Oleg Vazhnev Jan 13 '14 at 15:39
• I'd #include <cstdint> instead of stdint.h. Second, I'm not 100% sure about that one, but your c'tor and d'tor of ArrayPool are empty, and you don't define copy/move c'tors, so I think it's better practice to omit the c'tor/d'tor and just let the compiler generate the code. – Ela782 Jun 13 '14 at 0:58
• I am appalled by the number of people telling you to "just use locks." Yes, using a wait-free ringbuffer is overkill if your locks aren't contended or you don't need near-realtime performance. But if you're ever writing code that can't block--signal handlers and audio callbacks come to mind--then you need something like a ringbuffer. Telling you not to write one doesn't help at all with your understanding of how to write one. – Ian Ni-Lewis Jul 15 '15 at 22:43

The Boost Single-Producer Single-Consumer Queue should meet your needs. If you're trying to use this for production code and you don't understand why your completely unsynchronized code is a bad idea, don't try to roll your own based on advice from well-meaning passersby.

• spsc_queue doesn't allow to reuse elements. I believe my implementation is VERY simple so at least for education it would be interesting to make it CORRECT. – Oleg Vazhnev Jan 17 '14 at 1:58
• i will check spsc_queue but i'm afraid it's a little bit slow too. it's using copy-constructor which must be slower than just one call to memcpy. But probably i can live with this. Another problem is that it doesn't allow to "reconfigure" elements. I like my Obtain Commit semantic because it allows me to put element even if I don't have anything to put. – Oleg Vazhnev Jan 17 '14 at 2:01
• also probably I can learn boost.org/doc/libs/1_53_0/boost/lockfree/spsc_queue.hpp and copy "synchronization" code from spsc_queue to my queue – Oleg Vazhnev Jan 17 '14 at 2:07
• Almost certainly next_index as implemented is better. The unlikely macro is used to give a hint to the branch prediction circuits in the processor (stackoverflow.com/questions/109710/…). So you get one missed branch prediction every (in this case) 65k pushes/pops, and in return you're saving at least two instructions (and possibly a memory load for MASK) on every push/pop. – ruds Jan 17 '14 at 2:43
• copy constructor turns into a call to memcpy if the class is a pod type on most optimizers unless there is a faster way (which is the case with small classes). – odinthenerd Jan 17 '14 at 8:18
• there is absolutely no thread safety constructs, this means that you'll see a lot of interesting race conditions and memory inconsistencies

• just assuming dequeues happen fast enough does not mean they will in production

• you return T by value in Obtain(), instead of by reference so you can't actually write into it

• Obtain is a bad name, it sounds like it gets the next value like TryGet does

• memcpy is a bad idea to use to store the values if there is ever a custom copy constructor and a destructor

• that said Obtain->store->Commit can be put into a single Put(T*) member function

• eventually curReadNum and curWriteNum will overflow, it's not a real problem here because your length is a power of 2 and they are unsigned

• Thanks. Yes, I think Obtain() must return T* so i can memcpy to internal storage. Note I store only "simple" things, simple structures. I don't need a code that works for any kind of data. I need maximum performance on my data. The question is if my code is good "in general" or if "design and idea good in general". Or you can suggest another approach. – Oleg Vazhnev Jan 8 '14 at 13:16
• @javapowered you should at least fix points 1 and 2, which deals with memory consistency (a.k.a. flush the written value out to the shared memory instead of the cache) and should dequeuing ever be delayed for whatever reason you must be able to handle that cleanly – ratchet freak Jan 8 '14 at 13:39
• "flush the written value out to the shared memory instead of the cache" how can I do that? can you give an example which demonstrates such kind of problem? – Oleg Vazhnev Jan 8 '14 at 13:43
• Obtain->store->Commit can be put into a single Put(T*) how? note I do not want to allocate memory at runtime. – Oleg Vazhnev Jan 13 '14 at 1:30
• @javapowered the Put will then do exactly as your Obtain -> store -> Commit does now, and you just pass a pointer or reference into Put – ratchet freak Jan 13 '14 at 1:35

# Use assignment instead of memcpy

A better implementation of Obtain can return a non-const reference which you can assign to:

T& Obtain() {
}


Used like this:

void Processor::EnqueueFutOrderbook(orders* param)
{
storageItem = *param;
}


That deals with the "use the copy constructor instead of memcpy" suggested by @ratchetfreak.

If you use memcpy instead of assignment then your code is incorrect for all types of T which have a non-trivial (e.g. user-defined) copy constructor.

Copy-construct will be slower than memcpy, isn't it?

The reason for using assignment is if T has a non-trivial copy-constructor (more accurately, an 'assignment operator'): for example if T is a std::auto_ptr<> or if it contains a std::string: if T has a non-trivial user-defined assignment operator, memcpy avoids calling it: which, may be faster but is incorrect behaviour!

In your example though your T is myStruct, which has a default (or non-existent) assignment operator. In that case the assignment is done by the compiler as an intrinsic, which is likely to be at least as fast as the run-time-library's memcpy function.

Which of the following do you think is faster:

void test()
{
T source, target;
// test the speed of memcpy
for (int i = 0; i; i < 100000)
memcpy(&target,&source,sizeof(T));
// test the speed of compiler-generated assignment with copy-constructor
for (int i = 0; i; i < 100000)
target = source;
}


# An implementation which locks each method could be safe

One ('atomic') Store function would be easier to use than separate Obtain and Commit methods:

void Store(const T& newValue) {
++curWriteNum;
if (curWriteNum - curReadNum > length)
{
std::cout <<
"ArrayPool curWriteNum - curReadNum > length! " <<
curWriteNum << " - " << curReadNum << " > " << length << std::endl;
}
}


Instead of trying "lock-free" code, adding locks as follows would make it safe.

#pragma once

#include <stdint.h>
#include <iostream>
#include <mutex>

template<class T> class ArrayPool
{
public:
bool IsEmpty() {
std::lock_guard<std::mutex> lck (mtx);
}

bool TryGet(T& output)
{
std::lock_guard<std::mutex> lck (mtx);
{
return false;
}
return true;
}

void Store(const T& newValue) {
std::lock_guard<std::mutex> lck (mtx);
{
std::cout <<
"ArrayPool curWriteNum - curReadNum > length! " <<
curWriteNum << " - " << curReadNum << " > " << length << std::endl;
throw std::exception();
}
}

private:
static const uint32_t length = 1 << 4;
static const uint32_t MASK = length - 1;
T storage[length];
uint32_t curWriteNum;
std::mutex mtx;
};


Modify your client functions to call it like this:

void ReadThread() {
myStruct entry;
while(true) {
if (pool.TryGet(entry)) {
std::cout << entry.value << std::endl;
}
}
}

std::chrono::milliseconds dura(1000 * id);

myStruct storage;
storage.value = id;
pool.Store(storage);
std::cout << "Commited value! " << id << std::endl;
}


My primary requirement is latency. That's why I don't want to use lock, only memory barrier if absolutely required. And you don't ansered main question - if reader is guaranteed to see latest value. Should I insert memory barrier somewhere or something?

When I write code my primary requirement is always 'correctness' first. Usually the cost of a lock is:

• Trivial (unnoticeable) compared to whatever other processing the program is doing (for example, in your program, writing to std::out).

# Your buffer overrun detection is broken

I marked the following with <strike> because it is not relevent if you are not trying to detect a buffer overrun.

This statement won't work after you store 2^32 items:

if (curWriteNum - curReadNum > length) { ... }


Instead use something like this, before you write to storage and increment curWriteNum:

if (((curWriteNum+1) & MASK) == (curReadNum & MASK))
{
std::cout <<
"ArrayPool curWriteNum - curReadNum > length! " <<
curWriteNum << " - " << curReadNum << " > " << length << std::endl;
throw std::exception(); // or, return false;
}


The following is very unsafe, because you return a pointer to memory which (because you've incremented ++curReadNum) you now think it is already safe to overwrite:

T* TryGet()
{
{
return NULL;
}
return result;
}


bool TryGet(T& output)
{
{
return false;
}
return true;
}


I not always have object which I can copy so I have to use Obtain.

In that case you can modify TryGet to return a pointer, however in that case you should delay incrementing curReadNum until after you have finished using the pointer:

    T* TryPeek()
{
std::lock_guard<std::mutex> lck (mtx);
{
return NULL; // or 'return 0;'
}
}

// Call this after TryPeek() to discard most recently peeked
void Pop()
{
std::lock_guard<std::mutex> lck (mtx);
}


Which you can call like this:

void ReadThread() {
myStruct* entry;
while(true) {
if (entry = pool.TryPeek()) {
// Use the entry
std::cout << entry->value << std::endl;
// Discard the entry after finished using it
pool.Pop();
}
}
}


Thanks, I think no need to declare CurReadNum as volatile - buffer is never "overflow" so CurReadNum is actually read from one thread only.

That's true if (only if) you don't care about detecting buffer overruns.

So declaring CurReadNum as volatile is absolutely useless ...

If you have code to detect buffer overruns (and you did write some such code in your OP) then it's not "absolutely useless": it may be required, to make that code work correctly. A problem with multi-threaded code is that testing cannot prove that it's correct: testing can only prove that it's incorrect. Correctness needs to built-in, by design and code inspection.

... but will likely add some latency.

I doubt whether you can devise a performance test which, in practice, can detect any difference in latency.

# Attempting a lock-free implementation

And main question still not answered - if declaring curWriteNum as volatile is enough on modern Intel Xeon processor? I'm using 2 phisical processors server BTW. Is volatile enough and mandatory? Or memory barrier must/can be better?

If it were my code and I wanted it to be thread-safe, then I would use some kind of lock.

I surely don't want to use lock as they are extremmely slow.

I think it's sufficient to put a memory fence at the start and end of every method, to emulate the memory fences which are implied by the lock_guard statements.

of course I can "guard" every method, but I want to find certain places where memory barrier is REQUIRED but not more? I do not want to use more barriers than required.

I think the worry is that a compiler and CPU are allowed to reorder statements, and could theoretically write an incremented value to curWriteNum before writing to storage.

If you remove the unwanted overrun-detection code from my Store method then, as you say, the only memory that's used by both threads are curWriteNum and storage; so:

#pragma once

#include <stdint.h>
#include <iostream>

template<class T> class ArrayPool
{
public:
bool IsEmpty() {
// 'data dependency' memory barrier here
// or not because we don't mind if this return 'false positive' because we'll check again later
}

bool TryGet(T& output)
{
if (IsEmpty())
{
return false;
}
return true;
}

T* TryPeek() // Unlike TryGet this leaves the element in Storage
{
if (IsEmpty())
{
return 0;
}
}

void Pop() // Call this after a successful TryPeek
{
}

void Store(const T& newValue) {
// Ensure storage is written before mask is incremented
_MemoryBarrier();
++curWriteNum;
}

private:
static const uint32_t length = 1 << 4;
static const uint32_t MASK = length - 1;
T storage[length];
volatile uint32_t curWriteNum;
};


The reason why I also declared curWriteNum as volatile is that, for some compilers, volatile is is a hint that the variable should not be enregistered.

For example, without volatile, a test like while (curReadNum == curWriteNum) might be translated to:

mov eax,[curReadNum] ; move memory value to a CPU register
mov ebx,[curWriteNum] ; move other memory value to a different CPU register
label_loop_top:
cmp eax,ebc ; compare the two values-in-registers
je label_loop_top ; loop while the in-register values are equal


This code (caused by not declaring that curWriteNum is volatile) will never detect a subsequent write to curWriteNum.

With volatile, the same compiler might translate while (curReadNum == curWriteNum) to:

mov eax,[curReadNum] ; move memory value to a CPU register
label_loop_top:
cmp eax,[curWriteNum] ; compare with the in-memory value
je label_loop_top ; loop while it matches the in-memory value


This code (caused by declaring that curWriteNum is volatile) should eventually detect a subsequent write to curWriteNum.

If you don't trust that volatile is sufficient to do this job, then theoretically you should have a memory barrier in the IsEmpty function above (to ensure that it will read curWriteNum from memory and not from a register), as well as having one in Store (to ensure that storage is written before curWriteNum).

If you don't have this second memory barrier then theoretically a compiler or machine (perhaps a smarter one than the one you're using now) will read curWriteNum from memory on its first loop through IsEmpty(), notice that your ReadThread() code never modifies curWriteNum, and therefore assume it can thereafter reuse its old, cached, enregistered value of curWriteNum instead of reading it from memory again.

• i not always have object which I can copy so I have to use Obtain. I can add method Put(T*) in addition. Copy-construct will be slower than memcpy, isn't it? My primary requirement is latency. That's why I don't want to use lock, only memory barrier if absolutely required. And you don't ansered main question - if reader is guaranteed to see latest value. Should I insert memory barrier somewhere or something? – Oleg Vazhnev Jan 13 '14 at 6:26
• I edited my answer. – ChrisW Jan 13 '14 at 10:56
• Thanks, I think no need to declare CurReadNum as volatile - buffer is never "overflow" so CurReadNum is actually read from one thread only. So declaring CurReadNum as volatile is absolutely useless but will likely add some latency. I guess nothing can be faster than memcpy so I prefer to keep using it even loosing readability. And main question still not answered - if declaring curWriteNum as volatile is enough on modern Intel Xeon processor? I'm using 2 phisical processors server BTW. Is volatile enough and mandatory? Or memory barrier must/can be better? – Oleg Vazhnev Jan 13 '14 at 11:52
• @javapowered And edited again. – ChrisW Jan 13 '14 at 13:38
• thanks. compiler-generated assignment is probably faster than memcpy - how is that possible?. I surely don't want to use lock as they are extremmely slow. Let's wait probably someone can suggest how to modify code to be lock-free and valid. I need as much synchronization as required, but not more. lock would be overkill. – Oleg Vazhnev Jan 13 '14 at 13:46

just as an example of possible race conditions consider the function:

void WriteThread(int id) {
std::chrono::milliseconds dura(1000 * id);

myStruct* storage = pool.Obtain();
storage->value = id;
pool.Commit();
std::cout << "Commited value! " << id << std::endl;
}


then inline all called functions (which the compiler is allowed to do) (note this is pseudo code roughly representing what could happen).

void WriteThread(int id) {
std::chrono::milliseconds dura(1000 * id);

myStruct* storage = pool.storage[pool.curWriteNum & MASK];
storage->value = id;
++pool.curWriteNum; //ignoring the if and output because it is not relevant for this evample
std::cout << "Commited value! " << id << std::endl;
}


now remember that volatile is not a fence but only stops the compiler from reordering with regard to other volatiles. The compiler is also allowed to store variables in temperaries whenever needed (as long as the "as if" rule stands for a single threadded program). So this reordering is leagal:

void WriteThread(int id) {
std::chrono::milliseconds dura(1000 * id);

auto temp = pool.curWriteNum & MASK;
++pool.curWriteNum;
//starting here the other thread can start reading causing a race condition
myStruct* storage = pool.storage[temp];
storage->value = id;
std::cout << "Commited value! " << id << std::endl;
}


It should also be noted that volatile does not stop load and store reordering on hardware that supports this so even if the optimizer doesn't shoot you in the foot the hardware still may. It is also important to understand that what reordering happens where is very hard to predict so it is best to expect the worst. It may not be reordered the first time you look at the assembler but then you change something somewhere months later, maybe even in a completely different header which does not even use and you can't imagine the optimizer will change its behavior but it does and its allowed to and your code breaks, not on your machine but on your most important customers. Honestly you can't tell me with a straight face that you want to inspect every single spot these functions get inlined with -O3 optimization in assembler every time you recompile your project.

I would suggest using c++11 std::atomic variables for curWriteNum and curReadNum. This would at least solve the stated race condition.

It is also not a good idea to not handle an overflow. No matter how fast the consumer thread is it is next to impossible to prove that it will never have to wait for a lock for too long. As soon as it allocates memory (through new or otherwise) or even uses a function which could throw an exception derived from std::exception (which almost all exceptions are) then there is chance chance it will wait for the heap lock which literally take minutes in a worst case scenario where RAM has been swapped to an old, slow HD. Bottom line is that it probably will never happen on your machine but it probably will to some of your customers and they will then likely not remain your customers after that.

• +1 That's an example why it's better (i.e. "more correct" even if not "proven necessary via testing") to have a fence after writing to storage and before incrementing curWriteNum. – ChrisW Jan 16 '14 at 14:28
• If this may happen then it would be very interesting to reproduce it. I believe you, but if this issue is so hard to reproduce probably it just will never happen? Also it would be nice to see "proposed fix". Should I have memory barrier AND volatile variable or it's enough to have just volatile variable? – Oleg Vazhnev Jan 16 '14 at 15:05
• also MSDN states that C# "MemoryBarrier is required only on multiprocessor systems with weak memory ordering (for example, a system employing multiple Intel Itanium processors).". So if C# MemoryBarrier and C++ MemoryBarrier are similar, then C++ MemoryBarrier is useless on Intel Xeon? – Oleg Vazhnev Jan 16 '14 at 15:13
• @javapowered to be honest my memory barrier experience with production code comes from embedded ARM hardware so I'm not so sure about Intel. I would strongly suggest never ever using code in production which theoretically has a bug but is hard to reproduce in practice, it will bite you. – odinthenerd Jan 16 '14 at 17:05
• The one time you could 'prove' there will be no overrun is when the system/protocol is throttled somehow, e.g. if the producer never creates more than 'n' unprocessed/outstanding requests. – ChrisW Jan 16 '14 at 17:38

As a general rule, if you don't have a strong grasp of the content in [intro.multithread] of the C++ standard, it's a bad idea to write or maintain lock-free code. In nearly all cases, the costs due to more difficult maintenance, data corruption, etc of lock-free code will exceed the small additional CPU cost of just using locks.

Thus, my preferred implementation is this:

template <typename T> class ArrayPool {
public:
ArrayPool() = default;
bool IsEmpty() const {
std::lock_guard<std::mutex> lock(mu);
return IsEmptyLocked();
}
T* TryGet() {
std::lock_guard<std::mutex> lock(mu);
if (IsEmptyLocked()) return nullptr;
return GetLocked();
}
// Waits until this ArrayPool contains entries, then
// returns an entry.
T* WaitAndGet() {
std::unique_lock<std::mutex> lock(mu);
nonempty.wait(lock, std::bind(&ArrayPool::IsNonEmpty, this));
return GetLocked();
}
T* Obtain() {
std::lock_guard<std::mutex> lock(mu);
return ObtainLocked();
}
void Commit() {
std::lock_guard<std::mutex> lock(mu);
++curWriteNum;
}
void ObtainAndCommit(T&& t) {
std::lock_guard<std::mutex> lock(mu);
*ObtainLocked() = std::move(t);
++curWriteNum;
}
void ObtainAndCommit(const T& t) {
std::lock_guard<std::mutex> lock(mu);
// Using the copy constructor is always correct, and for PODs
// should be just as fast as memcpy.
*ObtainLocked() = t;
++curWriteNum;
}

private:
// Precondition: mu is held
bool IsEmptyLocked() const {
}
// Preconditions: mu is held, !IsEmptyLocked()
T* GetLocked() {
}
// Precondition: mu is held
T* ObtainLocked() {
// optional but recommended error checking
// The producer has outrun the consumer
throw std::runtime_error("Queue full");
}
}

static const std::size_t length = 1ul << 16;
static const std::size_t MASK = length - 1;

T storage[length];

mutable std::mutex mu;
// All members declared below are mu-guarded.
std::condition_variable nonempty;
std::size_t curWriteNum;
};


Note WaitAndGet; you should modify ReadThread to call that and avoid busy-waiting:

void ReadThread() {
while (true) {
auto* entry = pool.WaitAndGet();
std::cout << entry->value() << std::endl;
}
}


It appears that you'll be unable to do better than locking in this situation. You need to be sure of two things:

1. Modifications to curReadNum and curWriteNum are immediately visible to the reader and writer thread (both threads observe both variables).
2. Modifications to storage[i] made by the writer thread are visible to the reader thread before reading.

Because writes to curWriteNum don't depend on storage[i], this requires release-acquire semantics (for example, see the discussion of happens-before at http://en.cppreference.com/w/cpp/atomic/memory_order). That is essentially what mutex's lock/unlock give you.

• locking is very expensive. so far it seems this code works withoug locking (i'm using it). is it so diffucult to make it lock-free? I have just one thread that write (and never read) and one thread that read (and never write). This is simple thing! – Oleg Vazhnev Jan 17 '14 at 0:41
• You're spending money with the output of this thing and you're cool with opening yourself up to memory corruption due to data races? If you're only using one reader and one writer, why not just use one thread for the whole process? – ruds Jan 17 '14 at 1:28