Ramine
3/17/2015 10:10:00 PM
Hello,
We must think more...
I have just done a scalability prediction for this StringList
datastructure using my SeqlockX on read-mostly scenarios
and i have found that it doesn't scale at all, because
StringList is an array using binary search, and for an array
of 1000000 elements , in the average case time complexity, let say
it for each insert() it will move 500000 elements, on
an x64 architecture this will generate 62500 cache-misses,
because on every 8 pointers we will have a cache-miss, and
those cache misses are expensive, on the search() side
you will have a log(n) time complexity so this will be much much less
expensive than the insert() and the delete() sides, so from
the Amdhal's law this will not scale because the serial part
is much much expensive than the parallel part. So this StringList
will not scale on read-mostly scenarios. So the only alternative
is to use the Distributed reader-writer mutex with an AVL tree
or Red-black tree or a Skiplist this will give you 50X scalability on
multicore for smaller data corresponding to each key, and this will give
you much more than 50X scalability on multicores for bigger data
corresponding to each key, or you can use RCU.
Thank you,
Amine Moulay Ramdane.