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

Groups > comp.programming > #3708 > unrolled thread

Scalable RWLock version 1.0

Back to article view | Back to comp.programming

Contents

  Scalable RWLock version 1.0 aminer <aminer@toto.net> - 2013-09-08 14:08 -0700
    Re: Scalable RWLock version 1.0 aminer <aminer@toto.net> - 2013-09-09 15:58 -0700
      Re: Scalable RWLock version 1.0 "Chris M. Thomasson" <no@spam.invalid> - 2013-09-09 13:23 -0700
    Re: Scalable RWLock version 1.0 aminer <aminer@toto.net> - 2013-09-09 16:48 -0700
    Re: Scalable RWLock version 1.0 aminer <aminer@toto.net> - 2013-09-13 08:44 -0700
    Re: Scalable RWLock version 1.0 aminer <aminer@toto.net> - 2013-09-13 09:16 -0700

#3708 — Scalable RWLock version 1.0

Scalable RWLock 1.0 is here...


Author: Amine Moulay Ramdane.


Description:

Description: A fast and scalable Multiple-Readers-Exclusive-Writer Lock 
that works across processes and threads.

A Read/Write Lock is a performance improvement over a standard mutex for 
cases where reads outnumber writes. with a Read/Write Lock multiple 
simultaneous read locks may be held, but write locks are exclusively held.

The exclusive writing lock ensures that race conditions do not occur, 
since if one client is writing to the data no other client may read or 
write. Also, the allowance for multiple simultaneous read locks 
decreases  resource contention since multiple readers can safely use the 
shared data.  This increases performance over a standard mutex for the 
assumed usage pattern of frequent simultaneous reads and infrequent writes.


Click here to see the explanation of my RWLock algorithm:

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


You can download my scalable RWLock from:

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


Please take a look a the test.pas Object Pascal demo inside the zipfile, 
compile and run it...

Language: FPC Pascal v2.2.0+ / Delphi 7+: http://www.freepascal.org/

Operating Systems: Windows, Mac OSX , Linux , Unix...


Required FPC switches: -O3 -Sd -dFPC -dFreePascal

-Sd for delphi mode....

{$DEFINE CPU32} and {$DEFINE Win32} for 32 bits systems

{$DEFINE CPU64} and {$DEFINE Win64} for 64 bits systems



Thank you,
Amine Moulay Ramdane.

[toc] | [next] | [standalone]

#3711

Hello,

You will notice that my Scalable RWLock algorithm eliminates cache line 
transfers
between cores on the readers side when there is no writers present and 
there is
continually simultaneous readers threads runnning, it's why it's 
scalable on this case, but when the writers
modifies continually FCount3^.fcount3 my scalable RWLock will not be 
scalable on
the reader sides, so be smart please and here is the explanation of my 
RWLock
algorithm:

You will read this inside the RLock() method:

//==============================================================================
procedure TRWLOCK.RLock(var myid:integer);


begin

myid:=GetCurrentProcessorNumber;

repeat

while (FCount3^.fcount3 = 1)
do if mysleep=0 then sleep(0)
else sleep(1);

LockedExchangeAdd(FCount1^[myid].fcount1,1);

if (FCount3^.fcount3 = 0)
then break
else
  begin
    LockedExchangeAdd(FCount1^[myid].fcount1,-1);
  end;

until false;

end;
//==============================================================================

procedure TRWLOCK.RUnlock(myid:integer);

begin

LockedExchangeAdd(FCount1^[myid].fcount1,-1);

end;

//==============================================================================

First take a look at the source code inside the construtor you will 
notice that  the fcount1^ array is 64 byte aligned, and each element on 
the fcount1^ array resides in a cache line , so that it makes my RWLock 
scalable, and there is as much elements as the number of cores inside 
fcount1^ array .

As you have noticed i am testing with an: if (FCount3^.fcount3 = 0), to 
see if there is no writers threads that entered the WLock() method and 
incremented FCount3^.fcount3, if the thread that entered WLock() have 
not yet incremented FCount3^.fcount3 the threads on the RLock() side 
will proceed and the thread that entered WLock() will wait until all the 
FCount1^[i].fcount1 will equal to 0  so as you have noticed with my 
algorithm the writers will not be starved. And as you have noticed there 
is an:  if (FCount3^.fcount3 =  1) just after 
LockedExchangeAdd(FCount1^[myid].fcount1,-1) to test if the writer have 
entered and incremented FCount3^.fcount3 by 1, so that the readers will 
not spin by incrementing and decrementing FCount1^[myid].fcount1 by 1 , 
but they will spin on a sleep(0) until FCount3^.fcount3 will equal to 0, 
so my new algorithm is efficient.

Notice carefully that my RWLock is scalable cause each element of the 
FCount1^ array resides in a  seperate cache line , hence when i am 
incrementing  with  LockedExchangeAdd(FCount1^[myid].fcount1,1) it's 
scaling, notice also that i am using the following: 
myid:=GetCurrentProcessorNumber
so i am puting the processor number inside myid variable.

On the WLock() and WUnlock() side you will read this:

//==============================================================================

procedure TRWLOCK.WLock;

var i:integer;

begin

while not CAS(FCount2^.FCount2,0,1)
do
  begin
   if mysleep=0 then sleep(0)
   else sleep(1);
  end;

FCount3^.fcount3:=1;

for i:=0 to GetSystemThreadCount-1 do
  begin
    while (FCount1^[i].fcount1<>0)
     do
      begin
       if mysleep=0 then sleep(0)
       else sleep(1);
      end;
  end;

end;

//==============================================================================

procedure TRWLOCK.WUnlock;
var i:integer;
begin

FCount3^.fcount3:=0;
//switchtothread;
sleep(0);
FCount2^.FCount2:=0;
end;
end.
//==============================================================================


As you have noticed i am using a CAS() as a critical section cause only one
thread must enter the WLock(), after that assigning 1 to 
FCount3^.fcount3 to
block the new readers threads entering the RLock() method, after that i am
waiting for all FCount1^[i].fcount1 to equal 0 that means i am waiting 
for all
the threads that entered the RLock() to exit with a WUnlock(), and in 
RUnlock()
i am assigning 0 to FCount3^.fcount3  to unblock the readers threads and 
i am
using also a sleep(0) so that to give a chance to the readers to run, 
so i think
my algorithm is efficient and correct.


Click here to return to my homepage: http://pages.videotron.com/aminer/


Thank you,
Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#3712

"aminer"  wrote in message news:l0l98q$rpj$1@news.albasani.net... 
[...]

> so be smart please

lol.

[toc] | [prev] | [next] | [standalone]

#3713

Hello,

I have updated my scalable RWLock to version 1.01, if you want to 
compile it on Linux or Mac OSX just comment the WIN32
define option inside defines2.inc and don't use the timer component 
inside test.pas example cause it is only compatible with Win32 and 
Win64, and of course my scalable RWLock is compatible with Delphi 7 to 
Delphi XE5.



You can download my scalable RWLock from:

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



Thank you,
Amine Moulay Ramdane.

[toc] | [prev] | [next] | [standalone]

#3718

Hello,

Scalable RWLock was updated to version 1.02, now it works
correctly on both 32 bits and 64 bits.

You can download scalable RWLock from:

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


Thank you,
Amine Moulay Ramdane/

[toc] | [prev] | [next] | [standalone]

#3719

Hello,

Scalable RWLock was updated to version 1.02, now it works
correctly on both 32 bit and 64 bit.

You can download scalable RWLock from:

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


Thank you,
Amine Moulay Ramdane.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web