About concurrent hashtable and Dmitry distributed rwlock...

aminer10 — Sun, 26 Aug 2012 00:48:18 GMT

Hello,

Sorry for my english i will try to explain;

I have read the following:

http://groups.google.com/group/lock-free/browse_thread/thread/3e5c4ab767fac7f8

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.

Nicola"

Ad as you have noticed i have wrote parallelhashlist (a parallel hashtable),
you can find parallelhashlist here:

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

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.

topic About concurrent hashtable and Dmitry distributed rwlock... in Intel® Moderncode for Parallel Architectures

About concurrent hashtable and Dmitry distributed rwlock...