Concurrent SkipList

A concurrent SkipList version 1.6

Authors: Amine Moulay Ramdane (Based on Duncan Murdoch's sequential Skiplist)

Now i think that my concurrent SkipList is working perfectly and it is complete, i have just corrected something inside the search() and searchnode() methods, now if you want to do a search of for example an item of type integer between 50<=item<=100 , you have to call first the searchnode() on the item 50 and if the skiplist contains the item, the searchnode() will return it and you have to use next() to iterate inside the concurrent skiplist to return the items, but if the item 50 is not contained inside the skiplist, the searchnode() will return false, but you have to test for the returned node and if it's not equal to nil , you have after that to iterate to the next nodes with the next() method and to test if they are comprised between 50<=item<=100 and after that return the items.

I have enhanced my concurrent Skiplist more and its interface is very flexible and complete, and now i have added a third boolean parameter to the constructor, when this parameter is true the concurrent Skiplist will insert elements that are duplicated, when it's false it will not duplicate, also the size of the concurrent Skiplist is now an unsigned 64 bit integer, and now when you want to call next() method to get a sorted list, please call the Enter() method before getting the sorted list with the next() method and call the Leave() method after you get the sorted list, i have also corrected a bug, and i have thoroughly tested it and it is now working well, i have also included a new test example called test_all.pas in the zip file , please look at it and learn from it..

Description:

I propose a new concurrent skip list algorithm distinguished by a combination of simplicity and scalability. This parallel algorithm makes the search() method scalable and it makes the insert() method of a decent throughput. This parallel algorithm employs one distributed reader-writer mutex that makes the search() method scales to 1333x on NUMA architecture and on multicores with 0.1% of writes, unlike some other concurrent skip list algorithms, this algorithm preserves the skiplist properties at all times, which facilitates reasoning about its correctness. Experimental evidence shows that this parallel algorithm performs well.

As you have noticed i am using my scalable distributed reader-writer mutex inside my concurrent SkipList to make it scalable on the reader side, i have just benchmarked it and i have noticed that my concurrent Skiplist can scale to 1333x on a NUMA architecture with 0.1% of writes, that is powerful , so hope that you will be happy with my concurrent SkipList with its beautiful and complete interface, other than that you can easily configure it to be energy efficient.

You can go to download the zip files by clicking on the following web link:

https://drive.google.com/drive/folders/1GdXAizIGwjXbvtrAzGnrnc9HK5ZZePVq?usp=sharing

Language: FPC Pascal v2.2.0+ / Delphi 7+: http://www.freepascal.org/

Operating Systems: Windows, Mac OSX , Linux (x86)...

Required FPC switches: -O3 -Sd

-Sd for delphi mode....

Required Delphi switches: -$H+ -DDelphi

For Delphi XE-XE7 use the -DXE switch

The defines options inside defines1.inc are:

{$DEFINE CPU32} and {$DEFINE Windows32} for 32 bit systems

{$DEFINE CPU64} and {$DEFINE Windows64} for 64 bit systems