Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.pascal.misc > #2444

My concurrent SkipList version 1.51 is here..

Show all headers | View raw

Hello,


My concurrent SkipList version 1.51 is here..

Now i have done a scalability prediction calculation for my concurrent 
Skiplist and the search() method scales to 1333x with 0.1% of writes.


You can read about it and download it from:

https://sites.google.com/site/scalable68/concurrent-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.

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

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

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



Thank you,
Amine Moulay Ramdane.

Back to comp.lang.pascal.misc | Previous | Next | Find similar

Thread

My concurrent SkipList version 1.51 is here.. Wisdom20 <wisdom20@wisdom20.com> - 2019-08-03 15:31 -0500

csiph-web