Intel® Moderncode for Parallel Architectures
Support for developing parallel programming applications on Intel® Architecture.
1694 Discussions

About concurrent hashtable and Dmitry distributed rwlock...



Sorry for my english i will try to explain;

I have read the following:

Nicola wrote:

"Hi sunqxj,

hash tables are data structures that wok well with concurrent access.
If you have too much collisions probably you are using a wrong sized
table or the hash function is not working properly on your data set.
In addition, for space locality, you might consider a vector instead
of a list of collisions, especially if the values to be stored are
small enough.

From the concurrency point of view, please don't forget to avoid false
sharing and do not consider reader-writer mutex that, as shown in
Dmitriy site, prevent also readers from scaling linearly on a
multi-core architecture.


Ad as you have noticed i  have wrote parallelhashlist (a parallel hashtable),
you can find parallelhashlist here:
It's a parallel Hashtable 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. and parallelhashlist in scaling very well,  but since
it is a parallel hashtable so the possibility of contention is low so why do
i need the distributed reader-writer lock of Dmitry Vyukov inside my parallel hashslit ?
other than that I have done some tests with the lightweight MREW that i am
using inside my parallelhashlist and i have done also some tests with my lockfree mpmc
fifo queue and what i think is that the CAS is generating a lot of contention this is is why 
the lightweight MREW and my lockfree_mpmc is not scaling , but parallelhashlist is
scaling very well cause i am using lock-striping that is lowering contention.

What are doing Dmitry Vyukov in his distributed rwlock is lowering
the contention using the same method as lock striping that i am using inside
parallelhashlist it is why it is scaling, but there is still a possibility of contention
in his distributed rwlock that can cause a problem to the scalability if there is
too many threads and not a sufficient number of rwlocks in the Dmitry distributed 
rwlock to be able to lower the contention.

Thank you,
Amine Moulay Ramdane.
0 Kudos
0 Replies