Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #1923

Lock and Lockfree...

Cross-posted to 2 groups.

Show all headers | View raw

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.

Back to comp.programming.threads | Previous | Next — Next in thread | Find similar

Thread

Lock and Lockfree... aminer <aminer@toto.net> - 2013-10-15 19:30 -0700
  Re: Lock and Lockfree... aminer <aminer@toto.net> - 2013-10-15 19:38 -0700

csiph-web