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.
The WeakHashmap role, looks strange. It is used only for a isEmpty()
function, and i hope that this is only used for not to add an extra
reference. Because when it depends on removal by losing a reference
because it has gone weakly reachable, there is no garanteed minimal
timing for the isEmpty() = true to catch up. JDK6 has a much directer
relation between a reference going out of scope and going weakly then JDK4.
The WeakHashmap, I believe, is to do with a thread losing interest in a
scan. As far as I can tell, the objective is to allow a node that has
been marked as guard node for a thread to lose that property after the
Thread object is garbage collected. Of course, that may be hours, days,
weeks, or months after the last time the thread touched the FastList,
but a simple AtomicInteger would never get to zero after an abandoned scan.
I believe the code should be optimized for abandoned scans. In the
JavaSpaces implementation, finding the oldest item in the space matching
a template turns into a FastList search that stops at the first node
matching the template.
If the guard node business is really needed, it would be better done
based on an Iterator that is implemented in a FastList member class.
This might even be a case for a finalizer, though they have their own
problems. The Iterator's finalizer would unguard the Iterator's guard
node. An Iterator is much less likely than a Thread to remain reachable
after the iteration has been abandoned. Alternatively, we could provide
a close method that would pro-actively shut down the iteration, and
unguard the guard node. FastList is package access only, so all uses are
under our control.
I don't know whether the guard node implements required functionality or
is an outgrowth of synchronization confusion. It marks a node that was
at the tail of the list when the scan started, and stops the scan
immediately after showing that node, even if more nodes have been added
since then. Without the guard nodes, there would be no guarantee that a
search would ever finish, as long as new nodes are being added at the
end of the list.
Patricia
