[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 
linking?

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 
(note:
concurrent skip lists can scale only if the insertions/deletions are 
distributed.
If everyone is trying to insert at the beginning of the list, scaling 
will be
limited).

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

	Bill