Scalable Parallel HashList

Parallel Hashlist 1.66

Authors: Amine Moulay Ramdane(Parallel parts) and Barry Kelly (HashList).

Description:

A parallel HashList with O(1) best case and O(log(n)) worst case access that uses lock striping and my scalable RWLock in each bucket of the parallel hashtable , 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.

I have tested ParallelHashlist with four threads on a quad core and it's giving a perfect scaling on both reads and writes.

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

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

Operating Systems: Windows, Mac OSX , Linux...

Required FPC switches: -O3 -Sd -dFPC -dFreePascal

-Sd for delphi mode....

Required Delphi switches: -$H+ -DDelphi

For Delphi XE-XE7 use the -DXE switch

{$DEFINE CPU32} and {$DEFINE Windows32} for 32 bit systems

{$DEFINE CPU64} and {$DEFINE Windows64} for 64 bit systems