Lockfree MPMC FIFO queue

Benchmarks on an Intel Core 2 Quad Q6600:

I have tested 3 lockfree fifo queue algorithms against lockfree_mpmc fifo queue that is based on a circular buffer and used 4 threads under contention and the results follows on the graphs bellow:

Lock-free flqueue at: http://www.emadar.com/fpc/lockfree.htm

Lock-free RingBuffer at: http://www.odsrv.com/RingBuffer/RingBuffer.htm

GpLockfreequeue at: http://17slon.com/gp/gp/gplockfreequeue.htm

and my lockfree_mpmc at: http://pages.videotron.com/aminer/

Efficiency:

There are three ways to reduce lock contention:

1- Reduce the duration for which locks are held
2- Reduce the frequency with which locks are requested

or

3- Replace exclusive locks with coordination mechanisms that
   permit greater concurrency.

With low , moderate AND high contention, lockfree MPMC algorithm offers better scalability - and i am using it inside my Thread Pool Engine -

Correctness:

To not make the correctness verification longer, i will concentrate on the more important parts. If you take a look at the lockfree_mpmc source code you will read this:

if getlength >= fsize then begin result:=false; exit; end;

So, let's say the size of the bounded queue is 1000 , and imagine that the threads are executing the "if getlength >= fsize " all at the same time, and imagine that the getlength returns 999, so, the "if getlength >= fsize" will returns false , and since we have a fSize:=(1 shl aPower) - margin , with a margin of 1000 (margin must be >= to the number threads) , there will be no problem(overflow..)...

Now in the pop side, you will read this:

So, as you have noticed, there is a test like this: if CAS(head,lasthead,lasthead+1) , and this test avoids something like the ABA problem, cause if head have changed , the CAS() will fail.

Please click here to return to my homepage: homepage.

Regards,
Amine Moulay Ramdane.
http://pages.videotron.com/aminer/