[concurrency-interest] Skip Lists, Concurrent Skip Lists and Concurrent Sorted Maps

Bill Pugh pugh@cs.umd.edu
Fri, 18 Jun 2004 14:42:13 -0400

On Jun 18, 2004, at 2:15 PM, Brian Goetz wrote:

> Use case: In the JSR 107 (JCache) group, we'd love to have a 
> concurrent version of LinkedHashMap for building caches, so that LRU 
> falls out for free.  It sounds like this could be accomdated 
> relatively easily by a concurrent sorted map with a little extra work.

So you want a concurrent version of LinkedHashMap with access-order 

That won't scale to lots of concurrent accesses. You will need a list, 
and each
access to the LinkedHashMap will need to move the accessed element to 
the head
of that list. You can't make that scale beyond some small fixed number 
of concurrent
accesses. Perhaps 4-16, so not too bad. But it will not be able to 
scale to an
unbounded number of concurrent accesses, like concurrent skip lists can 
concurrent skip lists can scale only if the insertions/deletions are 
If everyone is trying to insert at the beginning of the list, scaling 
will be

So this is doable, but you probably don't want a skip list; just a 
that internally uses a concurrent linked list implementation. As I 
mentioned, this will have
some scaling limits, but may suffice for your purposes.