One of the primary types of data structures that I'm thinking about is a skip
list as defined by Bill Pugh's (http://www.cs.umd.edu/~pugh/) paper:
ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
The upshot is that a skip list provides compartmentalization/segmentation of
data which might provide the right segmentation for a persistence layer around
the same code.
Gregg Wonderly
On 12/14/2010 2:41 AM, Patricia Shanahan wrote:
On 12/13/2010 11:48 PM, Peter wrote:
Pats, I think James is talking about my classes. James, thanks for
the links, much appreciated, I hope you'll find time to participate
more often.
I have the utmost faith in Pats ability.
Cheers,
Peter.
...
I've got some concurrent utilities in pepe you may pinch /
improve if you like:
org.apache.river.impl.util.*
ConcurrentCollections ConcurrentSoftMap
ConcurrentWeakIdentityMap ConcurrentWeakMap
ConcurrentCollections is a multi read single write lock based
collection wrapper. It defensively copies for Iterators but
still allows performing removals from the underlying
collection.
The ConcurrentMap's are based on ConcurrentHashMap, using a
ReferenceQueue to remove stale entries prior to every method
call. Cheers,
Peter.
I'll take a look at the code, and mine it for ideas, but just based on
the descriptions, I think I can do better for the specifics of FastList.
The fact that it is tail insertion only creates some opportunities that
would not be present in a more general data structure.
In particular, I am currently thinking about moving the unlinking of
removed entries from being done as a side effect of each scan to being a
separate TaskManager task. Each FastList would have at most one thread
unlinking at a time, which would make it much simpler. I believe I can
do that, in the 1.5 memory model, with volatile next pointers, and have
very simple, fast synchronization-free iterators without copying.
One trick that may make it easier and faster is to never delete the last
node, including possibly inserting a dummy node. A list that always has
at least one node can be simpler than one that may be empty. Of course,
the dummy node would be invisible to callers.
I am seriously considering synchronizing the tail insertions, depending
on what I find out about the relative performance of blocking and
non-blocking for that type of job.
Patricia
