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

[Ola O. <ola...@gm...>]

Hello there.

Just a question here, in the weakly ordered cache scenario (guss the 
platform :), isnt the real danger that you may end up with the
++head
arriving at the cache before the (or part of)
fifo_[head & (Size-1)] = in
Leading to an opportunity for the reader to get totally bogus data? Thus the 
barrier is needed to ensure the the data gets to cache before the increment, 
i.e. it needs to go before the increment on head (your comment seem to 
indicate they should go after)?
Having just started looking into this myself, this kind of discussion is 
great.
Another thing that was bothering me is whether its "common knowledge" or 
universally guaranteed that the whole of any given 32bit write end up 
arriving at the cache together, I guess more generally if any store 
operation is kept together, although 32bits is plenty for a fifo length I 
imagine.

cheers
.ola

----- Original Message ----- 
From: "Jon Watte" <hp...@mi...>
To: <gam...@li...>
Sent: Wednesday, August 09, 2006 6:26 PM
Subject: Re: [GD-General] cross platform 64bit lock free FIFO?


>
>
> Andras Balogh wrote:
>> Yes, I only need one writer and one reader thread, but I'm not sure that 
>> I
>> understand the solution you propose. Could you elaborate a bit? Thanks,
>>
>
> Here is the implementation, an all its simplicity:
>
> // Lock-free FIFO by Jon Watte.
> // Size must be power of 2.
> // This FIFO is correct on systems with strongly ordered caches (such as
> Intel
> // and desktop PPC). It may require write barriers on systems with
> weakly ordered
> // caches, at the points marked /* 1 */ and /* 2 */.
> template<typename Stored, size_t Size>
> class LockFreeFifo {
>  public:
>    LockFreeFifo() { head = 0; tail = 0; }
>
>    /* get an item from the FIFO, return true if an item was gotten,
> else return false */
>    bool get(Stored & out) {
>      if (head - tail > 0) {
>        out = fifo_[tail & (Size-1)];
>        ++tail; /* 1 */
>        return true;
>      }
>      return false;
>    }
>
>    /* put an item into the FIFO, return true if it fit, false if it's
> full */
>    bool put(Stored & in) {
>      if (head - tail < Size) {
>        fifo_[head & (Size-1)] = in;
>        ++head; /* 2 */
>        return true;
>      }
>      return false;
>    }
>  private:
>    unsigned int head;
>    unsigned int tail;
>    Stored fifo_[Size];
> };
>
>
> Because it's non-blocking, it returns FALSE when there's nothing to do
> (FIFO full or empty). Because there's a single reader and a single
> writer, there is no thread contention on "head" vs "tail". Because it's
> using unsigned math, and the Size is a power of two (important!), the
> two's complement wrapping arithmetic makes for no special cases. (Note
> the comparison of head-tail > 0 !)
>
> On Intel, and other machines with strongly ordered caches, this doesn't
> need any kind of memory barrier or interlocked operation at all.
>
> On some more exotic systems with weakly ordered caches (where you may
> get "old" data when reading), there is a chance of get() returning false
> when there is actually one item in the cache; similarly, there's a
> chance of put() returning false when there is actually space. When the
> "head" and "tail" share a cache line, the maximum difference can be one
> item. However, for absolute correctness in these cases, you want to
> insert a cheap memory barrier at the points marked /* 1 */ and /* 2 */
> -- or, alternately, use the platform's atomic intrinsics (atomic_add(),
> InterlockedIncrement(), etc). On PPC, the memory barrier is
> traditionally the EIEIO instruction, on Intel (where it's not needed,
> unless you're writing to un-cached memory) it's the SFENCE instruction.
> I don't know if the new console PPC cores have a cheaper instruction
> than EIEIO.
>
> Cheers,
>
>                       / h+
>
>
> -------------------------------------------------------------------------
> Using Tomcat but need to do more? Need to support web services, security?
> Get stuff done quickly with pre-integrated technology to make your job 
> easier
> Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
> http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
> _______________________________________________
> Gamedevlists-general mailing list
> Gam...@li...
> https://lists.sourceforge.net/lists/listinfo/gamedevlists-general
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=557
>