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

Groups > comp.programming > #2048

Re: Parallel Hashlist was updated to version 1.43

Cross-posted to 2 groups.

Show all headers | View raw

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