Concurrent FIFO Queue version 1.0

[aminer]

Hello,

I have implemented a concurrent FIFO Queue that satifies
many requirements such us: it is FIFO fair, it minimizes efficiently the cache-coherence traffic and it is energy efficient on the pop() side: when there is no items in the queue it will not spin-wait , but it will wait on a portable manual event object, it is not as fast
as lockfree algorithms, cause if you want to satisfy the FIFO fairness
and to minimize efficiently the cache-coherence traffic and to be
energy efficient you have to pay a price: this will lower the speed
of the concurrent FIFO queue, but the speed of my concurrent FIFO Queue
is good i think , cause i have benchmarked on the Quad core processor
each running at 1.6 GHz, with 4 threads pushing and 4 threads poping and it gives 1 million transaction(push and pop) per second, and that's also good.

You can download my concurrent FIFO Queue from:

http://pages.videotron.com/aminer/



Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,


I have come to an interresting subject, i have compared
a FIFO queue that uses two spinlocks with an exponentaial backoff
and a lockfree FIFO queue that does not use an exponential backoff, i have come to the conclusion
that the Spinlock with a backoff is 6.5X times faster than
the lockfree version without a backoff, and you have to be smart and understand why.. i will explain it to you, if you take a look at a Spinlock with an exponentaial backoff , you will read this in the Enter() method:

---
procedure TSpinLock.Enter;

var t:integer;
   
begin

backoff.reset;
repeat

if CAS(@FCount2^.FCount2,0,1)then break;
t:=backoff.delay;
sleep(t);
until false;
end;

---

As you have noticed  if for example 4 threads will execute the CAS
one of them will succeed and 3 of them will backoff , but what
is very important to know, is that the thread that have succeeded
will have the opportunity to reenter many times the locked region
and modifying FCount2^.FCount2 in its local cache, so this will make
it very fast, in fact 6.5X times faster than the lockfree version without backoff, cause in lockfree algorithms every thread must have a
cache miss and reload the cache line from the memory and this
is slower than a Spinlock with a backoff,  so this is why the Spinlock with a backoff is very much faster and it minimizes also the cache-coherence traffic under contention, so what is the solution then? i think that the lockfree FIFO queue algorithms must use an exponential backoff mechanism to be much faster and to be able to minimize the cache-coherence traffic.



Hope you have undertood what i mean in this post..



Thank you,
Amine Moulay Ramdane.







   

[aminer]

I mean 6.5X times faster under contention of course.



Thank youm
Amine Moulay Ramdane.

[aminer]

Hello,

I have come to an interresting subject, and you have
to be smart to understand it more...

If you take a look at the following FIFO queue that is
waitfree on the push() side and lockfree on the pop()
side, here it's:

http://pastebin.com/f72cc3cc1

as i said before , there is a weaknesses with this FIFO queue, first
the lockfree side on the pop() is not FIFO fair , so it's not starvation-free on the pop() side, and there is a second weakness:
it doesn't minimizes the cache-coherence traffic ,
but there is also a third  weakness with this algorithm: since
you can not use an exponential backoff on the waitfree pop() side
you can not make it 4 times or 6 times faster under contention on the push() side,
the Spinlock() with an exponential backoff mechanism on the pop()
and the push() is 4 times to 6 times faster than the lockfree
version and the waitfree version without a backoff mechanism and
i have just explain it to you,
but you can add an exponential backoff on the pop() lockfree side of
this FIFO que,
and this will make it 6 times faster under contention on the pop() side.


So in my opinion , since the Spinlock with an exponential backoff is
6 times faster under contention ,  so the risk of a stavartion will
be lowered, and since it minimizes the cache-coherence traffic, so this will make the Spinlock with an exponential backoff
a better alternative if you want better speed and to minimize cache-coherence traffic.


 
Thank you,
Amine Moulay Ramdane.

[aminer]

Hello,


This 6X times faster is just for the pop() method, but
for the push() the Spinlock with backoff gives the same
performance as the lockfree, so this is why they both have
the same performance under contention.



Thank you,
Amine Moulay Ramdane.