Recent

Author Topic: ParallelHashList and ParallelQueue  (Read 5679 times)

aminer

  • Hero Member
  • *****
  • Posts: 956
ParallelHashList and ParallelQueue
« on: March 01, 2010, 05:46:01 pm »
Hello,

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.

---------------------------------------------------------------------------­----------------

 

Regards,
Amine Moulay Ramdane.



« Last Edit: March 02, 2010, 09:58:23 am by Vincent Snijders »

aminer

  • Hero Member
  • *****
  • Posts: 956
Parallel Queue en Parallel Hashlist
« Reply #1 on: March 01, 2010, 05:47:19 pm »
Hello,

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/

 

Sincerely,
Amine Moulay Ramdane.




aminer

  • Hero Member
  • *****
  • Posts: 956
Re: Parallel Queue en Parallel Hashlist
« Reply #2 on: March 02, 2010, 03:55:44 am »

Hello,

Please don't forget to compie with -Sd (delphi mode)
when using FPC.


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


Regards,
Amine.


 

TinyPortal © 2005-2018