5

int val = memLoc[index++];

or better yet

int val = memLoc[index++ & 0xFF];

Trying to do a threadsafe read from a shared ring buffer where each call gets the next value - and I'd love it to be lock free if at all possible as it happens a TON. No Boost / C++ 11 allowed :(

Michael Dorgan
  • 12,453
  • 3
  • 31
  • 61
  • 3
    You might be interested in reading [this article](http://www.codeproject.com/Articles/43510/Lock-Free-Single-Producer-Single-Consumer-Circular). – Alexey Frunze Apr 13 '12 at 14:36
  • 3
    No C++11 means that you need a pre-standard solution. If Boost is unacceptable then all other libraries (with theire stricter license terms) are presumably out as well, so you can't get anything portable. So, which OS do you need this on? – MSalters Apr 13 '12 at 15:15
  • What type is `memLoc`? Is it a pointer (or array) into `int`? – David Rodríguez - dribeas Apr 13 '12 at 15:20
  • Win32 / Xbox / PS3 / Apple / etc. :) memLoc is an int *, thought that would be inferred. Truth is, my original code had an &= for the index, but I realized that just isn't needed, which led to such a simple solution. I have cross platform fetch_add values so that is where I will go. Thanks all! – Michael Dorgan Apr 13 '12 at 15:58

2 Answers2

7

The only operation here which needs to be synchronized is the increment of the index value. Since this is just a numeric value it can be done without the use of locks via an atomic increment. The rest of the operations you listed are just reads of a shared location and don't need to be synchronized.

On Win32 making the increment synchronized is done with the InterlockedIncrement function

int oldValue = InterlockedIncrement(&index);
int val = memLoc[oldValue & 0xFF];

There are various synchronized increment functions available on Linux. There is a fairly good discussion about the options on this stackoverflow thread

Community
  • 1
  • 1
JaredPar
  • 733,204
  • 149
  • 1,241
  • 1,454
  • 2
    In C++11, there's `std::atomic_fetch_add` which should do the trick. – James Kanze Apr 13 '12 at 14:57
  • Are there any architectures where writing an `int` wouldn't be atomic (where you would have to synchronize the element read)? – Mark B Apr 13 '12 at 15:16
  • @MarkB the problem isn't just the atomic write of the element, it's the atomic write + reading of the old value + ensuring it's seen across all processors. Typically you need a special instruction for that. Looking at my answer I misused atomic in a couple of places. Going to clean that up. – JaredPar Apr 13 '12 at 15:19
  • @MarkB: Yes, there are. For starters *intel* if the `int`s are not aligned. And not only that, but also you need to take care of instruction reordering (the compiler might reorder the `index++` with the rest of the code around, and perform it before hand, it could cache the value and not write the incremented `index` back to memory...) – David Rodríguez - dribeas Apr 13 '12 at 15:22
1

You'd need to increment and read back index in an atomic operation. Unfortunately the ++ operator doesn't guarantee any atomicity.

Most processors have some sort of fetch-increment-store instruction that can be used. You can insert inline assembly to do that. http://en.wikipedia.org/wiki/Fetch-and-add

If you're running on Windows, MS provides an API to access this: http://msdn.microsoft.com/en-us/library/windows/desktop/ms684122(v=vs.85).aspx

If you're on another OS, there's likely similar functionality. In any case though, you'll need OS or lower type access to get an atomic fetch-increment-store.

dragonx
  • 14,963
  • 27
  • 44