Concurrent SkipList

A concurrent SkipList version 1.4

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 250X on NUMA architecture and on multicores, 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 up to 150 millions of transactions per a reponse time of 10 seconds on a NUMA architecture with 0.1% to 0.2% of writes, that is acceptable for many applications , so hope that you will be happy with my concurrent SkipList with its beautiful and complete interface.

I have spoken about my new distributed reader-writer mutex and i have told you that i have done a simulation that have given me the following true fact: my scalable distributed reader-writer mutex can scale up to 40X with 0.1% to 0.2% of writes, you will say that it's not fully scalable, but i think that we have to reason also from a different point of view , i mean that you have for example to look at the response time and the throughput and see if that is acceptable for many applications, and notice with me that as i have showed you before with my concurrent SkipList that is using my scalable reader-writer mutex that it can scale up to 150 millions of transactions per a response time of 10 seconds with 0.1% to 0.2% of writes, and you can also lower the throughput and higher the percentage of writes, so the important question to ask is if this response time of 10 seconds for a throughput of 150 millions of read's and write's transactions is acceptable for many application ? the answer is yes, so then the conclusion is that my scalable reader-writer mutex even if it can scale up to 40X is still useful, other than that you can easily configure it to be energy efficient.

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

Operating Systems: Windows, Mac OSX , Linux...

Required FPC switches: -O3 -Sd -dFPC -dFreePascal

-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

Please click on the small arrow on the right of the zip file bellow to download...