Mailing-List: contact commons-dev-help@jakarta.apache.org; run by ezmlm
Precedence: bulk
Reply-To: "Jakarta Commons Developers List" <commons-dev@jakarta.apache.org>
Message-ID: <F4F2EBDF8C16D5118B6500508BD32B4DCB99BC@EARTH>
From: "Jack, Paul" <pjack@sfaf.org>
To: 'Jakarta Commons Developers List' <commons-dev@jakarta.apache.org>
Subject: RE: [SUBMIT] OptimizedFastArrayList
Date: Wed, 17 Apr 2002 09:50:39 -0700
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"

> 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?

Only major difference is that my version has no concept
of "fast" vs. "slow" mode -- no setFast(boolean) method.
It could be added.  The main thing is that the two classes
have different superclasses.  FastArrayList extends from
ArrayList; however, it doesn't use any of ArrayList's state;
it reimplements all the list methods.  So, I thought my 
version would just extend Object and implement List directly.

But conceivably, yes, OptimizedFastArrayList could simply
replace FastArrayList, by adding the fast mode feature and
extending (and also ignoring) ArrayList.


> 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.

Ew, yes, forgot about that.  The State reference can be assigned before
it's initialized with its constructor...

Code can be rewritten, however, so that the constructor is never called
by using clone() to copy it rather than using a constructor...The docs
you provided don't indicate whether clone() would suffer from the same
problem.  Will have to research...

Good catch!  I never would have thought of that...


> [Paul, I don't mean to pick on you about this.  The existing Fast* classes

> suffer from the exact same problem]

Pick away. :)


> 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.  

Correct; the set(int, Object) and add(Object) methods are indeed slower
in my implementation.  However...


> 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).

...however, when you're copying the elements for an add(int, Object)
method, you essentially have to clone the array.  Actually when I say
"clone" I really mean "reallocate".  java.util.ArrayList uses 
System.arraycopy in its add(int, Object) implementation; and the javadoc
for System.arraycopy indicates that if the source and target arrays
are the same, a new array is allocated, the source is copied to the 
new array, and then the contents of the new array replace the original:
Essentially, it's been cloned.

Furthermore, *all* of the write methods in ArrayList except add(Object)
and set(int, Object) need to do this.

So you're reallocating the array, because you have to.  FastArrayList, 
however, can wind up reallocating it 3 times:  Once during the explicit
clone() of the internal ArrayList, once when the internal ArrayList 
ensures its capacity, and once during the internal implementation of
add(int, Object).  My version only allocates the array once.

However, I've just completed the performance tests, and plain vanilla
ArrayList's algorithms are still faster in a singlethreaded context.
(To be expected, since it doesn't have to clone State objects all the
time.)  So the javadoc comment that OptimizedFastArrayList should
perform similarly to ArrayList overexaggerates...ahem.


> 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. 

It's true; I can improve the add(Object) implementation.  Thanks again,
I wouldn't have thought of it.

I'll look into the double-checked locking thing.

-Paul


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