Re: [GD-General] cross platform 64bit lock free FIFO?

[George W. <ge...@ap...>]

On Wed, 09 Aug 2006 09:26:20 -0700, Jon Watte <hp...@mi...> wrote:
> Here is the implementation, an all its simplicity:
>
> // Lock-free FIFO by Jon Watte.
> // Size must be power of 2.

This restriction could be removed by using a modulus operation instead of
the AND. (Probably a safe assumption that this restriction was done as a
compromise to speed (Not necessary on PPC)). At the least I'd add an assert
to verify that Size is a power of 2.

assert( !(Size & ( Size - 1 ) );    // only zero for exact powers of 2

Other than that this code is really only useful for a single provider &
consumer. There's a race condition between the full/empty tests and the
tail/head increments that wouldn't work with multiple writers/readers.

(Yes, validating race conditions acerbates my schizophrenia. ;-)

I'd also add code to optionally block on the failure cases (read-empty &
write-full) and when a thread is blocked signal a wakeup when the failure
case is invalidated (queue goes non-empty when a reader is blocked or queue
goes non-full when a writer is blocked).

For the single provider/consumer case you still wouldn't need the lock; Just
a condition variable for signaling.

-- 
Enjoy,
George Warner,
Schizophrenic Optimization Scientist
Apple Developer Technical Support (DTS)