Lock and Lockfree...

[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.