A new concurrent SkipList algorithm

[Amine Moulay Ramdane]

Hello,

If you ask me a question like:

Amine, is there any new parallel Skiplist algorithm that is more efficient than 

your  conccurrent algorithm that uses a distributed read-writer mutex  ?

I have thought more, and i have come with a new Parallel Skiplist algorithm

that is scalable on a read mostly workload, this algorithm uses only 

an mfence on the reader side, that's really cool ! and it elevates the weakness 

of the distributed reader-writer mutex that becomes slower and slower on the writer side

with more an more threads, in my new concurrent Skiplist algorithm i am using one  SeqlockX 

between the search() and the insert() methods , you will find my SeqlockX algorithm that avoids 

livelock when there is many writers here:

https://sites.google.com/site/aminer68/scalable-seqlockx

and i am also using one distributed reader-writer mutex between the delete() and the 

search() methods... 

This new algorithm is faster than my previous concurrent SkipList algorthm, but 

i have made a scalability prediction for my new algorithm and i have 

noticed that since the serial part of the Amdahl's law of the writer side 

is a little bit expensive since the average search in a Skiplist can become a little 

bit expensive, so my calculation have proved that you will not get much improvement with 

this new algorithm compared to my previous algorithm, you will get around 3x improvement max,

so i have finally decided to not implement my new concurrent SkipList algorithm, so 

i will stay with my current concurrent SkipList algorithm that gives a decent scalability.

Thank you,

Amine Moulay Ramdane.