   is this thread safe?
  Hi,i'm trying to understand and implement some lock free data structures using atomic operations.First i've implemented a stack. It's meant to be used with one thread pushing and one popping.I think i came up with a simple implentation but i've had some problems during some tests, but i'm not sure if they're caused by the stack. So i've thought i'd better post my code here and see what the experts say:void push(const T& item){if(count == size) return;items[count++] = item;}bool pop(T* item){if(!count) return false;*item = items[--count];return true;}Any comments would be appreciated.Edit: sorry, some bugs on first post. shouldnt program in a textbox.Oh god, i can already sense that count won't be in sync after the if comparisons...[Edited by - froop on July 26, 2010 8:22:59 PM]
  No.Same code expanded for clarity:void push(const T& item){if(count == size) return;items[count] = item;count += 1;}bool pop(T* item){if(!count) return false;count -= 1;//what happens if push is called now//*item will be whatever was just pushed, not what was there before*item = items[count];return true;};Quote:Original post by PalidineNo.Same code expanded for clarity:*** Source Snippet Removed ***Yeah I almost suspected a problem there :/ I was just trying to edit my original post with a solution but i quickly realised that it's not that easy(?)   ;Quote:i'm trying to understand and implement some lock free data structures using atomic operations.For starters, you dont have any atomic operations in your stack, so it isn't thread safe at all.You need to use the OS and processor specific commands to preform atomic increments, decrements, and compare-and-swaps to properly create your lock free structure.;  The above isn't correct. Ignoring off-by-one problem, the pop() semantics are incorrect.count = 4T1: reserves front = count + 1 = 5T2: pop() count-- = 3T2: pop() count-- = 2T1: items[5] = x, count = 5What are the values of items[3] and items[4]?The proper versions would be:void push(T & item) {  for (;;) {    if (count == size) return;    oldcount = count;    front = count+1;    items[front] = item;    if (CAS(&count, front, oldcount)) return;  }}CAS is the compare-and-swap. It sets count to front only if count hasn't changed in between. On Windows that is the InterlockedCompareExchange.bool pop(T & item) {  for (;;) {    if (count == 0) return false;    oldcount = count;    item = items[oldcount];    newcount = oldcount-1;    if (CAS(&count, newcount, oldcount)) return true;  }}Same here.Both of these are spin loops, which will likely hang a single-core machine. Even on multi-core they might cause poor performance in cases of very high contention.   ;Quote:Original post by KulSeranQuote:i'm trying to understand and implement some lock free data structures using atomic operations.For starters, you dont have any atomic operations in your stack, so it isn't thread safe at all.You need to use the OS and processor specific commands to preform atomic increments, decrements, and compare-and-swaps to properly create your lock free structure.My bad, i had a misconception about atomic operations. I need to read up on them again.   ;  On Windows you can use the Interlocked* family of functions. The CAS operation demonstrated by Antheus above is called InterlockedCompareExchange on Windows.Also, a queue makes a lot more sense than a stack for a lock-free strucuture ;)   ;Quote:Original post by AntheusThe above isn't correct. Ignoring off-by-one problem, the pop() semantics are incorrect.count = 4T1: reserves front = count + 1 = 5T2: pop() count-- = 3T2: pop() count-- = 2T1: items[5] = x, count = 5What are the values of items[3] and items[4]?The proper versions would be:*** Source Snippet Removed ***Thanks for the proper solution, Antheus. Makes sense to me now. Hoped i could get away with a little less operations. But if you say it causes poor performance then maybe a stack isn't the most suitable structure for multithreading.Quote:Original post by HodgmanOn Windows you can use the Interlocked* family of functions. The CAS operation demonstrated by Antheus above is called InterlockedCompareExchange on Windows.Also, a queue makes a lot more sense than a stack for a lock-free strucuture ;)Thanks for that link Hodgman. Do you mean that a queue can be implemented more efficiently? It seems to be, because i studied the lock free queue posted here lockless-queue-revision.html and hoped i could come up with a similarly simple stack implementation, but i guess euphoria was bigger than ability.   ;  Yeah a queue has less contention than a stack.The problem is with determining which 'slot' you're going to write to or read from.With a queue, you've got a read-pointer and a write-pointer (the head & tail of the queue). With a stack, you've just got one read-write-pointer (the top of the stack).With a queue, the writer-thread is solely responsible for moving the write-pointer forward (and same for the read thread & pointer), but with a stack, both threads are sharing the top-of-stack pointer. This leads to the spin-loop shown by Antheus where after reading/writing a slot, you've got to validate that the other thread didn't interrupt you.[edit]Also, that lockless queue that you've linked to is unsafe.It's trying to do the right thing -- it writes the message to the queue, and then only after the message has been written does it store the new head pointer (which allows the other thread to pop that message):  head = mHead;//read head pointer  mBuffer[head++] = msg;//write data and increment the copy of pointer  mHead = head;//store the incremented pointerHowever, it's valid for both the compiler (at compile-time) and the CPU (at runtime) to re-order those instructions as it sees fit, e.g. the above code could possibly be executed as this:  head = mHead;//read head pointer  head++;//increment the copy of pointer  mHead = head;//store the incremented pointer  mBuffer[head] = msg;//write data...and if that happened, then the read-thread might try to pop the message before it's been written!To stop this kind of re-ordering from happening, you need to use memory barriers. All of the Interlocked functions on Windows act as memory barriers, which is another reason why they're essential.So yeah, that mooproductions queue is not at all safe. This happens all the time... Check out these articles instead:Lock-Free Code: A False Sense of SecurityWriting Lock-Free Code: A Corrected Queue[Edited by - Hodgman on July 26, 2010 8:33:03 PM];Quote:Original post by HodgmanYeah a queue has less contention than a stack.The problem is with determining which 'slot' you're going to write to or read from.With a queue, you've got a read-pointer and a write-pointer (the head & tail of the queue). With a stack, you've just got one read-write-pointer (the top of the stack).With a queue, the writer-thread is solely responsible for moving the write-pointer forward (and same for the read thread & pointer), but with a stack, both threads are sharing the top-of-stack pointer. This leads to the spin-loop shown by Antheus where after reading/writing a slot, you've got to validate that the other thread didn't interrupt you.[edit]Also, that lockless queue that you've linked to is unsafe.It's trying to do the right thing -- it writes the message to the queue, and then only after the message has been written does it store the new head pointer (which allows the other thread to pop that message):  head = mHead;//read head pointer  mBuffer[head++] = msg;//write data and increment the copy of pointer  mHead = head;//store the incremented pointerHowever, it's valid for both the compiler (at compile-time) and the CPU (at runtime) to re-order those instructions as it sees fit, e.g. the above code could possibly be executed as this:  head = mHead;//read head pointer  head++;//increment the copy of pointer  mHead = head;//store the incremented pointer  mBuffer[head] = msg;//write data...and if that happened, then the read-thread might try to pop the message before it's been written!To stop this kind of re-ordering from happening, you need to use memory barriers. All of the Interlocked functions on Windows act as memory barriers, which is another reason why they're essential.So yeah, that mooproductions queue is not at all safe. This happens all the time... Check out these articles instead:Lock-Free Code: A False Sense of SecurityWriting Lock-Free Code: A Corrected QueueThanks a lot for warning me about mooproductions queue. i blindly believed it was thread safe :) i didn't know about the compiler and CPU re-ordering instructions, although it makes sense because that would be required for optimization.Anyways, before i work through the DrDobbs articles, i altered my code a little bit so that the count is only modified after read and write are completed, but that would be pointless if the compiler re-orders the instructions. Well, here it is and i bet the thread safety issues will come to my mind in the next moments.void push(const T& item){if(count == size) return;UINT front = count;items[front] = item;++count;}bool pop(T& item){if(!count) return false;UINT front = count - 1;item = items[front];--count;return true;}hmm would this by any chance be thread safe if i declared count as volatile?   