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

Martin Buchholz martinrb at google.com
Wed Mar 24 11:48:08 EDT 2010


Hi Michael,

Welcome to the lock-free data structure designers club.

I won't have time to do an in-depth review of your data structure,
but I do have some high-level comments:

I like very much the idea of mixing arrays and linked lists.
Java tends to have data structures implemented purely
using one or the other.

My own specialty is linked lists (we're still learning how to
implement them in the best way!).  Take a look at
our latest concurrent collections in Doug's CVS,
e.g. ConcurrentLinkedQueue and LinkedTransferQueue.
Or the ConcurrentLinkedDeque I am working on
http://cr.openjdk.java.net/~martin/CLD/

Is your data structure "GC-robust" as defined by Boehm?

Martin

On Wed, Mar 24, 2010 at 07:23, Michael Spiegel
<michael.m.spiegel at gmail.com> wrote:
> 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
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>



More information about the Concurrency-interest mailing list