commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael A. Smith" <...@apache.org>
Subject Re: [SUBMIT] OptimizedFastArrayList
Date Wed, 17 Apr 2002 05:02:34 GMT
On Tue, 16 Apr 2002, Jack, Paul wrote:
> Attached is a new List implementation inspired by 
> but faster than FastArrayList.  From the javadoc:

Is there any external behavior difference between FastArrayList and your
OptimizedFastArrayList (other than performance)?  If so, can you
explicitly specify the differences and why?  If not, is there a reason not 
to just replace the existing FastArrayList with the faster implementation?

> Read access to this list is not synchronized, but write
> access is.  To pull this trick off, the state of the list
> is cloned during a write, the changes are applied to the
> clone, and then the clone replaces the list's state.  Read
> operations use a local reference to the old state, and are
> not adversely affected by a write.  This is similar to 
> org.apache.commons.collections.FastArrayList.

is it me, or does this behavior suffer from the double checked locking
problem?  While this isn't the exact same scenario (i.e. the double
checking of a variable one in and one outside a synchronized block), I
believe the situation is the same:  it is possible that a non-synchronized
read can see the cloned object before that cloned object is fully created.

For more information on the double checked locking, see this excellent 
writeup: 
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html

Other writeups:
http://www.javaworld.com/javaworld/jw-02-2001/jw-0209-double.html
http://www.javaworld.com/javaworld/jw-05-2001/jw-0525-double.html

The JSR for "fixing" the Java memory model:
http://jcp.org/jsr/detail/133.jsp

[Paul, I don't mean to pick on you about this.  The existing Fast* classes 
suffer from the exact same problem]

> However, since the list is backed by a dynamic array, *many
> of the algorithms that alter the list already require that 
> the state be cloned*.  For instance, to remove an element, 
> a new array must be allocated, and the elements from the old
> array (minus the removed object) must be copied to the new 
> array.  FastArrayList essentially performed the cloning twice:
> It first clones the entire list, and then performs the costly
> remove() operation on the copy.  This implementation is 
> optimized such that a new array is only allocated once.  
> Assuming no monitor contention, this class should perform 
> similarly to java.util.ArrayList, except for the add(Object)
> and set(int, Object) methods, which now perform in linear time.

Actually, if the ArrayList implementeds were smart, they aren't "cloning"  
the array each time, they are just adding the element in an existing, but
empty, slot in the array.  That is, the underlying array is possibly
larger than ArrayList.size().  An add(Object) only needs to duplicate the
array if the existing array is full.  An add(int, Object) may need to
"move" elements, but shouldn't need to clone the entire array.  The actual
cloning of the array (to grow or shrink the size) can have an amortized
constant time operation if the the array is doubled when a grow is
required (and if you add in the shirnking, which I don't think the JDK
impl does, you would halve the size of the array when it is 1/4 full).

In your version, you may even be able to get rid of the single clone using
a similar technique.  For example, if you are adding to the end
(add(Object)), if the array already has room for one more element, you
could just increase the size and create a new State rather than a new
State *and* a new array.  When removing the last element, use the same
array, but create a new State with the smaller size.  I'm not sure if that
really buys much though, as it requires excess memory for the empty array
elements that are only used if an add operation occurs sometime in the
future.  Considering that the underlying ArrayList impl uses that memory 
anyway, I'm not sure this is that big of a deal when considered as a 
replacement of FastArrayList. 

regards,
michael


--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message