Re: [GD-General] Totally Safe lock-free FIFO for arbitrary-sized items.

[Jon W. <hp...@mi...>]

Andras Balogh wrote:
> Hmm, I have one more question regarding your implementation: You put  
> barrier() after the increments, because otherwise get() might think that  
> the FIFO is empty, when it's not, and put() might think that the FIFO is  
> full, when it's not. I believe that putting in these memory barriers won't  
> solve the problem, because what if the threads get switched after the  
> increment, but before executing the barrier()?? Even using  
> interlocked_increment won't help, because only one thread is changing the  
> value, and again, what if the thread switch occurs after the store and  
> before the increment?
>
> Of course, none of this really matters, because it should not result in  
> corrupt data in any way, I just think that those barriers are unnecessary.
>   

If you get switched out before the barrier, that's no different (really) 
from being switched out before the put operation -- you'll be switched 
back in and perform the barrier in the next time-slice.

The barriers are not necessary on Intel machines, because the data 
caches are guaranteed to be consistent. They use snooping to make 
read-after-write always return the consistent value.

Some more esoteric hardware may have caches that don't have this nice 
property, and a read from a word that's already in cache may return the 
old cache value, rather than the updated value living in some other cache.

The barriers may also be needed on machines with out-of-order 
speculative memory, where the  write to update the FIFO contents may be 
re-ordered to happen after the write to update the queue size. There may 
be some chance of this happening under certain circumstances on certain 
Intel chips, AFAICT, so an SFENCE wouldn't hurt (although I believe the 
"common, plain" cases don't actually have this problem).

Cheers,

             / h+