river-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Patricia Shanahan <p...@acm.org>
Subject Re: Progress, and a problem
Date Mon, 13 Dec 2010 16:57:19 GMT
Sim IJskes - QCG wrote:
> On 13-12-10 16:27, Patricia Shanahan wrote:
>> Sim IJskes - QCG wrote:
>>> On 13-12-10 07:16, Patricia Shanahan wrote:
>>>> On 12/12/2010 5:48 PM, Peter Firmstone wrote:
>>>>> Patricia Shanahan wrote:
>>>>>> On 12/3/2010 7:15 AM, Gregg Wonderly wrote:
>>>>>> ...
>>>>>> > The important issue in FastList is that it was written with
the
>>>>>> JDK1.4
>>>>>> > memory model. After moving River to Java 1.5, we'd have the
 
>>>>>> JSR166
>>>>>> work
>>>>>> > and the new, consistent memory model where volatile has a true
>>>>>> meaning.
>>>>>> > However, this code in particular is quite complex as you have
>>>>>> noted, so
>>>>>> > even adjusting to the new memory model could be problematic.
>>>>>>
>>>
>>> I dont get it. What is the role of FastList. If it is only a very  
>>> fast
>>> concurrent single linked list, with an iterator, i can be  
>>> implemented
>>> much easier.
>>
>> As far as I can tell it is intended to be a concurrent linked list  
>> with
>> add at tail, forwards iteration starting at head (not currently  
>> done as
>> an Iterator, but I think it should be) and removal. I am not yet sure
>> whether removal is always done in the context of an iteration or not.
>>
>>>
>>> It i only has a iterator and add,remove operations, only the list
>>> stitching needs to be guarded. As long as no garantuees are given in
>>> timing relations.
>>
>> Having studied it closely for many hours, the code appears to me to  
>> be
>> complicated out of all proportion to its function.
> This scan is only meant to shorten the time to remove is it? Would a  
> double-linked list, with the forward link used for iterator and the  
> backward only to find the unstitch point not be a lot easier to  
> build? Would a stitch of the 2 links back and forward separately  
> guarded cost so much more time? I have to find some literature on  
> this i think.

Yup. I think it may be time for some reading about concurrent data  
structures. There are several options, and there is no point doing our  
own research on which is best if the data has already been published.

For example, I think it could be made a lot simpler by using a single  
static TaskManager for all FastList unlinking (or, if we commit to 1.5  
and later, the equivalent java.util structure). Each FastList instance  
could monitor statistics such as the number of unlinkable nodes as a  
percentage of nodes. If some criteria are met, and the FastList has no  
outstanding reap task, it would create a reap task and add it to the  
TaskManager.

That way, the unlinking would be removed from the normal scans, making  
them much simpler and faster. The specialized reap task would do  
nothing else, and there would be at most one reap task at a time for a  
given FastList, making the reap operation faster and simpler.

I'm not sure of the relative merits of this approach and doubly  
linking to allow the remove call to unlink. If we keep the guard node  
idea, we would still need delayed unlinking because a removed node may  
also be a guard.

I also need to read the FastList user code, to collect all the use  
cases.

Patricia


Mime
View raw message