[concurrency-interest] cache-conscious alternative to ConcurrentSkipList[Set|Map]

Michael Spiegel michael.m.spiegel at gmail.com
Wed Mar 24 10:23:37 EDT 2010


Hello,

I have been investigating a lock-free multiway search tree algorithm
for concurrent applications with large working set sizes.  The result
is a lock-free skip tree data structure.  Skip trees are randomized
search trees that share properties with B-trees and skip lists.
Similar to a skip list, a random number is selected on the
introduction of a key into the structure.  The random number
determines the level in the interior of the tree to place a key. In
the lock-free implementation, optimal paths through the tree are
temporarily violated by mutation operations, and eventually restored
using online node compaction.

I've placed skip-tree concurrent Set and Map implementations on
github: http://github.com/mspiegel/lockfreeskiptree.  They implement
the same interfaces as j.u.c.ConcurrentSkipList[Set|Map].  Any
feedback from the mailing list would be of tremendous value.
Preprints of the paper describing the algorithm are available on
request.

Cheers,
--Michael


More information about the Concurrency-interest mailing list