Lockfree_mpmc version 1.1 .... -

[aminer]

Hello,


I have added an exponential backoff both in the push() and the pop()
of the algorithm, and now it's giving a good performance under contention.


Description


Lock-free MPMC algorithm to handle queue FIFO based on a cicular
buffer, proposed by Dariusz Mazur and modified and enhanced by
Amine Moulay Ramdane, use only single CAS on pop and single CAS on push.

You can download lockfee_mpmc from:


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


Please look at the benchmarks here:


http://pages.videotron.com/aminer/parallelqueue/parallelqueue1.htm


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


Operating Systems: Win , Linux and Mac (x86).


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


-Sd for delphi mode....


Required Delphi switches: -DMSWINDOWS -$H+ -DDelphi


Thank you.


Amine Moulay Ramdane.

[aminer]

Hello,


Look at: http://www.emadar.com/fpc/lockfree.htm


In the pop side we have:


--------------


function gFLQueue.pop(var tm:_R):boolean;


var newhead, lastHead : integer;
begin
repeat lastHead:=head;
if tail<>head then begin
pointer(newHead):=interlockedCompareExchange(pointer(head),pointer(lastHead
+1),pointer(lasthead));
if newHead=lastHead
then
  begin tm:=getObject(lastHead);
  result:=true; exit;
end; end
else
begin result:=false; exit;
end; until false; end;
{$ENDIF} end.


----


If you have noticed, after he is incrementing head with in
interlockedCompareExchange(), he is doing a tm:=getObject(lastHead);
and this is an error i think, cause  if the thread is preempted and another
thread have put another value in the same place as lashead, the value will
be invalid and corrupted.


I have corrected this problem in my lockfree_mpmc fifo queue version
1.1.


So, becarefull with those lockfree algorithms.


thank you.


Amine Moulay Ramdane.

[aminer]

Hello,

I have updated lockfree_mpmc to version 1.11 , you can download it from:

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


thank you.

Amine Moulay Ramdane.

[aminer]

Hello,

Lockfree_mpmc 1.11 and lockfree flqueue 0.6 are still inefficient on the push
side under contention,

If you have took a look at lockfree_mpmc 1.11 and lockfree flqueue 0.6 ,
with this algorithm you can not include an exponential backoff like this in the push side:

----

function TLockfree_MPMC.push(tm : tNodeQueue):boolean;
var lasttail,newtemp:longword;
begin

 if getlength >= fsize
  then
      begin
          result:=false;
          exit;
      end;
result:=true;
//newTemp:=windows.interlockedincrement(temp);
newTemp:=LockedIncLong(temp);

lastTail:=newTemp-1;
setObject(lastTail,tm);
repeat
  if CAS(tail,lasttail,newtemp)
   then
      begin
       exit;
    end;
backoff1.delay; // the backoff is not possible with this algorithm ,
                   

 until false;


end;

----


Unfortunatly. as the algorithm is wrote, it is inefficient on the push side under contention.




Amine Moulay Ramdane.