ParallelHashList and ParallelQueue...

[aminer]

Hello,

Welcome to:http://www.lazarus.freepascal.org/
and http://www.freepascal.org/

Description

A parallel HashList with O(1) (best case) and O(log(n))(worst case)
access that use a hash based method with an array of MREWs. This
will allow to parallelize the writes and reads in separate chains ,
and also to parallelize the reads in the same chain.

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

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

For benchmarks and a capacity planning example look here:

http://pages.videotron.com/aminer/parallelhashlist/queue.htm

You will find the zipfile in:

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

And here is a small example on how to use ParallelHashlist:
(I have included it inside the zipfile)
---------------------------------------------------------------------------­­-----------
program test;
uses {$IFDEF Delphi}cmem,{$ENDIF}
Parallelhashlist,windows,syncobjs,sysutils,classes;
var

hndlArr : Array[0..19] of THandle;
AId:DWORD;
event:TSimpleEvent;
hash1:TParallelHashList;
j:integer;
trait:TCaseinsensitiveTraits;
obj:pointer;

function StartFunc1(InVal:pointer):longword;
var i,j:integer;
obj:pointer;

begin
event.waitfor(INFINITE);
for i:=0 to 1000000 //800000
do
begin
hash1.find('amine moulay
ramdane'+inttostr(random(5000000)),pointer(obj));
end;
end;

function StartFunc2(InVal:pointer):longword;
var i:integer;
a:integer;
obj:pointer;

begin
event.waitfor(INFINITE);
for i:=0 to 1000000
do
begin
hash1.find('amine moulay
ramdane'+inttostr(random(5000000)),pointer(obj));
end;
end;

function StartFunc3(InVal:pointer):longword;
var i:integer;
obj:pointer;

begin
event.waitfor(INFINITE);
for i:=0 to 1000000
do
begin
hash1.find('amine moulay
ramdane'+inttostr(random(5000000)),pointer(obj));
end;
end;

function StartFunc4(InVal:pointer):longword;
var i:integer;
obj:pointer;

begin
event.waitfor(INFINITE);
for i:=0 to 1000000
do
begin
hash1.find('amine moulay
ramdane'+inttostr(random(5000000)),pointer(obj));
end;
end;


begin
randomize;
trait:=TCaseinsensitiveTraits.create;;
hash1:=TParallelHashList.create(trait,6000000);
for j:=0 to 5000000
do
begin
obj:=pointer(j);
hash1.Add('amine moulay ramdane'+inttostr(j),obj);
end;
event:=TSimpleEvent.create;
hndlArr[0]:=BeginThread(nil,0,@StartFunc1,pointer(1),0,AId);
hndlArr[1]:=BeginThread(nil,0,@StartFunc2,pointer(1),0,AId);
hndlArr[2]:=BeginThread(nil,0,@StartFunc3,pointer(1),0,AId);
hndlArr[3]:=BeginThread(nil,0,@StartFunc4,pointer(1),0,AId);
event.setevent;
WaitForMultipleObjects(4, @hndlArr, True, INFINITE);
event.free;
hash1.free;
end.
---------------------------------------------------------------------------­­----------------

and

Description:

Parallel algorithm to handle queue FIFO that reduce contention
and enhance the parallel throuput of the lockfree_mpmc pop() method,
it can go now up to 7.037 Millions of transactions per second
on an Intel Core 2 Quad Q6600

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

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

For ParallelQueue benchmarks on an Intel Core 2 Quad Q6600 look at:

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

I have tested 3 lockfree queue algorithms:

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

RingBuffer at: http://www.odsrv.com/RingBuffer/RingBuffer.htm

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

Welcome:http://www.lazarus.freepascal.org/

and

http://www.freepascal.org/


Regards,
Amine Moulay Ramdane.

[aminer]

Hello gain,

The Freepascal memory manager does scale linearly when using
threads..

But the Delphi memory manager does not scale linearly, so i have
used the TBB memory manager (look into cmem.pas inside the
ParallelHashList.zip

And as you have noticed my Threadpool, see:
http://pages.videotron.com/aminer/

use something like

procedure TThreadPoolThread.Execute;
begin
while not Terminated do
begin
end;
end;

Next step i will enhance my Threadpool to use an event object
to not consume any CPU if there is no objects in the queue.
And also i will add another enhancement , you will be able to call
any method with the execute(pointer(obj),method);

and also threadpool will use ParallelQueue (a lockfree mpmc) or
lockfree_mpmc.

Also, look carefully inside the lockfree_spmc zipfile at:
http://pages.videotron.com/aminer/

In the POP method i am doing this:
1-function TLockfree_SPMC.pop(var obj:tNodeQueue):boolean;
2- var
3- lastHead : longword;
4- begin
5- repeat
6- if tail[0]<>head[0]
7- then
8- begin
9- lastHead:=head[0];
10- obj:=getObject(integer(lastHead));
11- if CAS(head[0],lasthead,lasthead+1)
12- then
13- begin
14- result:=true;
15- exit;
16- end;

If you have noticed at line 6 i am testing if
tail[0]<>head[0] and after that i am copying
head[0] to the local variable lasthead, so, if
between line 6 and 9 head[0] has changed and is
equal to tail[0] , that means that the queue is empty
and the thread must *NOT* pop the object from the queue !
Hence, the correct logic is: we have to copy head[0] to the
local variable and AFTER that we test if tail[0]<>head[0]

So, here is my patch to the pop method:

-----------------------------------------------------­­-----
function TLockfree_MPMC.pop(var obj:tNodeQueue):boolean;
var lastHead : longword;
begin
repeat
lastHead:=head[0];
if tail[0]<>head[0]
then
begin
obj:=getObject(integer(lastHead));
if CAS(head[0],lasthead,lasthead+1)
then
begin
result:=true;
exit;
end;
end
else
begin
result:=false;
exit;
end;
until false;
end;
-------------------------------------------------------

And also if you have noticed, there is a test with a
CAS(head[0],lasthead,lasthead+1) , so, if head[0] have
changed the CAS will fail.. hence, there is no such
thing that ressemble the ABA problem...
And the logic is correct.

Please patch and change the pop() method in lockfree_spmc.pas
inside the threadpool zipfile

I will soon patch the algorithm and upload the zipfile to my
website...

Note also in lockfree_mpmc.pas that i am aligning head and tail
with:

typecache1 = array[0..15] of longword;

to avoid false sharing of course...



Sincerely,
Amine Moulay Ramdane.