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

Groups > comp.programming > #1583

ParallelHashList was updated to version 1.3 ...

Cross-posted to 2 groups.

Show all headers | View raw

Hello,


In my previous version of ParallelHashList even if i have used
lock striping for the hash chains, synchronizing access to the counter
that computes the number of entries in the hashmap was reintroducing
the scalability problem of exclusive locking, this counter was  called
a hot field because every mutative operation needs to access it.
In this new version 1.3 of parallelhashlist i have splited the global
counter to many counters to enhance the scalability... also i have  changed
parallelhashlist to use only 100 lightweight  MREWs 
(multiple-readers -exclusive-writer)
this will lower the memory consumption  and this will allow to parallelize
the writes and reads in separate chains , and also to parallelize the reads
in the same chain of the hashmap , so this will give a good performance
and a good scalability .

Description:

A Parallel HashList with O(1) (best case) and O(log(n)(worst case)
access that use a hash based method that uses lock striping and
100 lightweight  MREWs (multiple-readers -exclusive-writer).
This will allow to parallelize the writes and reads in separate chains , and
also to parallelize the reads in the same chain.


You can download parallelhashlist from:

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


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


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

and please take a look at the benchmarks here:

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

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



Thank you.

Amine Moulay Ramdane.

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

Thread

ParallelHashList was updated to version 1.3 ... "aminer" <aminer@videotron.ca> - 2012-05-17 17:30 -0500
  Re: ParallelHashList was updated to version 1.3 ... "aminer" <aminer@videotron.ca> - 2012-05-17 18:00 -0500
    Re: ParallelHashList was updated to version 1.3 ... "aminer" <aminer@videotron.ca> - 2012-05-17 18:28 -0500
    Re: ParallelHashList was updated to version 1.3 ... "aminer" <aminer@videotron.ca> - 2012-05-17 19:17 -0500
  Re: ParallelHashList was updated to version 1.3 ... "aminer" <aminer@videotron.ca> - 2012-05-17 19:21 -0500
  Re: ParallelHashList was updated to version 1.3 ... "aminer" <aminer@videotron.ca> - 2012-05-17 19:58 -0500
    Re: ParallelHashList was updated to version 1.3 ... "aminer" <aminer@videotron.ca> - 2012-05-17 20:02 -0500
  Re: ParallelHashList was updated to version 1.3 ... "aminer" <aminer@videotron.ca> - 2012-05-17 21:01 -0500
  Re: ParallelHashList was updated to version 1.3 ... "aminer" <aminer@videotron.ca> - 2012-05-17 21:23 -0500

csiph-web