river-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Gregg Wonderly <gr...@wonderly.org>
Subject Re: datastructure classes
Date Tue, 14 Dec 2010 16:53:46 GMT
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
>


Mime
View raw message