[concurrency-interest] cache-conscious alternative to ConcurrentSkipList[Set|Map]
michael.m.spiegel at gmail.com
Wed Mar 24 10:23:37 EDT 2010
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
More information about the Concurrency-interest