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

Groups > comp.programming.threads > #988 > unrolled thread

Parallel Hashlist was updated to version 1.43

Back to article view | Back to comp.programming.threads

Contents

  Parallel Hashlist  was updated to version 1.43 "aminer" <aminer@videotron.ca> - 2012-08-09 19:55 -0500
    Re: Parallel Hashlist  was updated to version 1.43 "aminer" <aminer@videotron.ca> - 2012-08-10 09:21 -0500
      Re: Parallel Hashlist  was updated to version 1.43 "aminer" <aminer@videotron.ca> - 2012-08-10 12:36 -0500

#988 — Parallel Hashlist was updated to version 1.43

Hello all,


Parallel Hashlist was updated to version 1.43

In the previous version i have set the number of lightweight 
MREWs(multiple-readers-exclusive-writer)
to 128 but i have decided to change that in version 1.43  so that you can 
give a variable
number of MREWS, this will scale better and now the constructor will look 
like this:

 hash1:=TParallelHashList.create(trait, Hashnize, number_of_MREWS);

and the number_of_MREWS must be less or equal to the Hashsize

also i have given you  two examples inside the zipfile, but please note that
the IntToStr() that i am using insode the test files don't scale well, but 
in reality
and in fact parallel hashlist does scale very well if you don't use 
IntToStr()..

Description:

A parallel HashList with O(1) best case and O(log(n)) worst case access that
uses lock striping and lightweight MREWs(multiple-readers-exclusive-writer) 
,
this allows multiple threads to write and read concurently. also 
parallelhashlist
maintains an independant counter , that counts the number of entries , for 
each
segment of the hashtable and uses a lock for each counter, this is also for 
better scalability.

Note: When i have done those benchmarks , there was not enough/much items
organized as a self-balancing tree in the individual chains of the 
hashtable, so ,
almost all the items was found and inserted in O(1) , so the parallel part 
in the
Amdahl equation was not much bigger compared to to the serial part. But you
will notice in pratice that as soon as you will have more items on the 
chains of
the Hash table , organized as self-balancing tree, with a worst case log(n) 
, the
parallel part will become bigger in the Amdahl equation and you will have 
better
performance and scalability than the numbers in the graph of the benchmarks 
...
Please pass a hashsize and the number of mrews in power of 2 to the 
constructor
by using the shl operation for example like this

trait:=TCaseinsensitiveTraits.create;;
hash1:=TParallelHashList.create(trait,1 shl 25,1 shl 25);

Why do you have to use a power of 2 ?

Please read this:

"Power-of-Two Hash Table Size

Any data structures 101 book will say choose a prime for the number of 
buckets,
so that the bucket's index can easily be computed by h(k) = k mod m, where k 
is
the key value and m is the bucket size. While this approach is 
straight-forward,
there are a number of issues with it, including slow modulo performance.
ConcurrentHashMap instead uses a power-of-two rule

http://work.tinou.com/2008/09/performance-optimization-in-concurrenthashmap.html "

I am using modulo functions inside parallelhashlist, and using a number of 
locks in power of 2,
so you have to use hashsize in power of 2 ,  this will make the modulo 
function of the delphi
and freepascal compilers 10X faster.


You can download parallel hashlist from:


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



Sincerely,
Amine Moulay Ramdane.

[toc] | [next] | [standalone]

#990

Hello,

Parallel Hashlist was updated to version 1.44


You can download parallelhashlist from:


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



Sincerely,
Amine Moulay Ramdane.



"aminer" <aminer@videotron.ca> wrote in message 
news:k01m6q$a3u$5@dont-email.me...
>
> Hello all,
>
>
> Parallel Hashlist was updated to version 1.43
>
> In the previous version i have set the number of lightweight 
> MREWs(multiple-readers-exclusive-writer)
> to 128 but i have decided to change that in version 1.43  so that you can 
> give a variable
> number of MREWS, this will scale better and now the constructor will look 
> like this:
>
> hash1:=TParallelHashList.create(trait, Hashnize, number_of_MREWS);
>
> and the number_of_MREWS must be less or equal to the Hashsize
>
> also i have given you  two examples inside the zipfile, but please note 
> that
> the IntToStr() that i am using insode the test files don't scale well, but 
> in reality
> and in fact parallel hashlist does scale very well if you don't use 
> IntToStr()..
>
> Description:
>
> A parallel HashList with O(1) best case and O(log(n)) worst case access 
> that
> uses lock striping and lightweight 
> MREWs(multiple-readers-exclusive-writer) ,
> this allows multiple threads to write and read concurently. also 
> parallelhashlist
> maintains an independant counter , that counts the number of entries , for 
> each
> segment of the hashtable and uses a lock for each counter, this is also 
> for better scalability.
>
> Note: When i have done those benchmarks , there was not enough/much items
> organized as a self-balancing tree in the individual chains of the 
> hashtable, so ,
> almost all the items was found and inserted in O(1) , so the parallel part 
> in the
> Amdahl equation was not much bigger compared to to the serial part. But 
> you
> will notice in pratice that as soon as you will have more items on the 
> chains of
> the Hash table , organized as self-balancing tree, with a worst case 
> log(n) , the
> parallel part will become bigger in the Amdahl equation and you will have 
> better
> performance and scalability than the numbers in the graph of the 
> benchmarks ...
> Please pass a hashsize and the number of mrews in power of 2 to the 
> constructor
> by using the shl operation for example like this
>
> trait:=TCaseinsensitiveTraits.create;;
> hash1:=TParallelHashList.create(trait,1 shl 25,1 shl 25);
>
> Why do you have to use a power of 2 ?
>
> Please read this:
>
> "Power-of-Two Hash Table Size
>
> Any data structures 101 book will say choose a prime for the number of 
> buckets,
> so that the bucket's index can easily be computed by h(k) = k mod m, where 
> k is
> the key value and m is the bucket size. While this approach is 
> straight-forward,
> there are a number of issues with it, including slow modulo performance.
> ConcurrentHashMap instead uses a power-of-two rule
>
> http://work.tinou.com/2008/09/performance-optimization-in-concurrenthashmap.html "
>
> I am using modulo functions inside parallelhashlist, and using a number of 
> locks in power of 2,
> so you have to use hashsize in power of 2 ,  this will make the modulo 
> function of the delphi
> and freepascal compilers 10X faster.
>
>
> You can download parallel hashlist from:
>
>
> http://pages.videotron.com/aminer/
>
>
>
> Sincerely,
> Amine Moulay Ramdane.
>
>
>
> 

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

#992

Hello,


I have updated parallelhashlist to version 1.44

What have changed in version 1.44 ?

I have corrected a bug in the constructor,

Before, it was:

if (AHashSize mod size2) <> 0 then size2:=size2+1;

In version 1.44 i have corrected the bug by changing size2 to size1:

if (AHashSize mod size1) <> 0 then size2:=size2+1;


And after that i am setting correctly the array fcount1(the independant 
counters ,
that count the number of entries , for each segment of the hashtable) and 
the
array mrew((multiple-readers-exclusive-writer locks)  like this:

setlength(fcount1,size2);
for i:=0 to size2-1  do fcount1[i]:=0;
 for i:=0 to size2-1  do mrew[i]:=TOmniMREW.create;


Sincerely,
Amine Moulay Ramdane















Sincerely,
Amine Moulay Ramdane.












"aminer" <aminer@videotron.ca> wrote in message 
news:k031tr$qrh$8@dont-email.me...
>
>
> Hello,
>
> Parallel Hashlist was updated to version 1.44
>
>
> You can download parallelhashlist from:
>
>
> http://pages.videotron.com/aminer/
>
>
>
> Sincerely,
> Amine Moulay Ramdane.
>
>
>
> "aminer" <aminer@videotron.ca> wrote in message 
> news:k01m6q$a3u$5@dont-email.me...
>>
>> Hello all,
>>
>>
>> Parallel Hashlist was updated to version 1.43
>>
>> In the previous version i have set the number of lightweight 
>> MREWs(multiple-readers-exclusive-writer)
>> to 128 but i have decided to change that in version 1.43  so that you can 
>> give a variable
>> number of MREWS, this will scale better and now the constructor will look 
>> like this:
>>
>> hash1:=TParallelHashList.create(trait, Hashnize, number_of_MREWS);
>>
>> and the number_of_MREWS must be less or equal to the Hashsize
>>
>> also i have given you  two examples inside the zipfile, but please note 
>> that
>> the IntToStr() that i am using insode the test files don't scale well, 
>> but in reality
>> and in fact parallel hashlist does scale very well if you don't use 
>> IntToStr()..
>>
>> Description:
>>
>> A parallel HashList with O(1) best case and O(log(n)) worst case access 
>> that
>> uses lock striping and lightweight 
>> MREWs(multiple-readers-exclusive-writer) ,
>> this allows multiple threads to write and read concurently. also 
>> parallelhashlist
>> maintains an independant counter , that counts the number of entries , 
>> for each
>> segment of the hashtable and uses a lock for each counter, this is also 
>> for better scalability.
>>
>> Note: When i have done those benchmarks , there was not enough/much items
>> organized as a self-balancing tree in the individual chains of the 
>> hashtable, so ,
>> almost all the items was found and inserted in O(1) , so the parallel 
>> part in the
>> Amdahl equation was not much bigger compared to to the serial part. But 
>> you
>> will notice in pratice that as soon as you will have more items on the 
>> chains of
>> the Hash table , organized as self-balancing tree, with a worst case 
>> log(n) , the
>> parallel part will become bigger in the Amdahl equation and you will have 
>> better
>> performance and scalability than the numbers in the graph of the 
>> benchmarks ...
>> Please pass a hashsize and the number of mrews in power of 2 to the 
>> constructor
>> by using the shl operation for example like this
>>
>> trait:=TCaseinsensitiveTraits.create;;
>> hash1:=TParallelHashList.create(trait,1 shl 25,1 shl 25);
>>
>> Why do you have to use a power of 2 ?
>>
>> Please read this:
>>
>> "Power-of-Two Hash Table Size
>>
>> Any data structures 101 book will say choose a prime for the number of 
>> buckets,
>> so that the bucket's index can easily be computed by h(k) = k mod m, 
>> where k is
>> the key value and m is the bucket size. While this approach is 
>> straight-forward,
>> there are a number of issues with it, including slow modulo performance.
>> ConcurrentHashMap instead uses a power-of-two rule
>>
>> http://work.tinou.com/2008/09/performance-optimization-in-concurrenthashmap.html "
>>
>> I am using modulo functions inside parallelhashlist, and using a number 
>> of locks in power of 2,
>> so you have to use hashsize in power of 2 ,  this will make the modulo 
>> function of the delphi
>> and freepascal compilers 10X faster.
>>
>>
>> You can download parallel hashlist from:
>>
>>
>> http://pages.videotron.com/aminer/
>>
>>
>>
>> Sincerely,
>> Amine Moulay Ramdane.
>>
>>
>>
>>
>
> 

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web