- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

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.

Link Copied

1 Reply

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content

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, itwas:

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

for i:=0 to size2-1 do fcount1

*:=0;*for i:=0 to size2-1 do mrew

*:=TOmniMREW.create;*Sincerely,

Amine Moulay Ramdane

Topic Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page