Mailing-List: contact river-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: river-dev@incubator.apache.org
Received-SPF: pass (athena.apache.org: domain of
 SRS0=NDDCvI=TN=wonderly.org=gregg@yourhostingaccount.com designates
 65.254.253.147 as permitted sender)
Message-ID: <4D07A11A.3020106@wonderly.org>
Date: Tue, 14 Dec 2010 10:53:46 -0600
From: Gregg Wonderly <gregg@wonderly.org>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US;
 rv:1.9.2.12) Gecko/20101027 Thunderbird/3.1.6
MIME-Version: 1.0
To: river-dev@incubator.apache.org
CC: Patricia Shanahan <pats@acm.org>
Subject: Re: datastructure classes
References: <4CF89BD3.3030103@acm.org>
 <4CF909A0.5070409@wonderly.org>	 <4D056E41.7020102@acm.org>
 <4D057B73.3090905@zeus.net.au>	 <4D05BA22.4000002@acm.org>
 <4D06672A.10203@wonderly.org>	 <4D066FA2.8050207@wonderly.org>
 <4D069D21.5070908@zeus.net.au>	 <4D06BA8D.4040602@simulexinc.com>
 <4D06C523.5000006@acm.org> <1292312925.2245.5.camel@Nokia-N900-51-1>
 <4D072DCB.1010408@acm.org>
In-Reply-To: <4D072DCB.1010408@acm.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Sender: Gregg Wonderly <gregg@wonderly.org>

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
>