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

Groups > comp.programming > #2050

Re: Parallel Hashlist was updated to version 1.43

Cross-posted to 2 groups.

Show all headers | View raw

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.
>>
>>
>>
>>
>
> 

Back to comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

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

csiph-web