Asp Forum - A new concurrent SkipList algorithm

Ramine

8/8/2015 12:26:00 AM

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/scalabl...

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 has 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.

comp.programming

A new concurrent SkipList algorithm

Ramine

x Login to ForumsZone