Sorry for my english i will try to explain;
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
of a list of collisions, especially if the values to be stored are
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
Ad as you have noticed i have wrote parallelhashlist (a parallel
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
also parallelhashlist maintains an independant counter , that counts the
of entries , for each segment of the hashtable and uses a lock for each
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
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
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
What are doing Dmitry Vyukov in his distributed rwlock is
the contention using the same method as lock striping that i am
parallelhashlist it is why it is scaling, but there is still a possibility
in his distributed rwlock that can cause a problem to the scalability if
too many threads and not a sufficient number of rwlocks in the Dmitry
rwlock to be able to lower the contention.
Amine Moulay Ramdane.