[collections][SUBMIT] A faster version of FastArrayList

[Jeff Varszegi <jv...@yahoo.com>]

This version of FastArrayList looks to be from two to twenty times as fast as the one currently in
Collections.  (Differences are sure to be found on different machines and JVMs, but it does seem
to be much faster.)  I found over a twofold speed gain under the Java 1.4.0 'server' VM, as well
as a twentyfold gain under the 1.4.0 'client' VM, on my machine (a laptop running WinXP Pro, 512M,
1.2 GHz).  I really like the FastArrayList class, I just thought it would be nice if it could be
faster.

I achieved the speed increase mainly by reducing method-call overhead.  Instead of wrapping
instances of ArrayList, I took the code from ArrayList itself and adapted it to the FastArrayList
concept, directly swapping out arrays instead of ArrayList instances.  I preserved the behavior of
FastArrayList wherever appropriate, actually adding more synchronization in a couple of places.
I made a test script that extends TestList.  I had problems with the script, but I really suspect
that it is with the test script this time (and/or the way I have JUnit set up).  At least, I find
statements like the following very puzzling:

1) testEmptyListSerialization(org.apache.commons.collections.TestFastArrayList2)
java.io.NotSerializableException: java.lang.Object
3) testEmptyListCompatibility(org.apache.commons.collections.TestFastArrayList2)
java.io.FileNotFoundException: data\test\FastArrayList2.emptyCollection.version1.obj (The system
cannot find the path specified)

The only serialization code in the class is 'implements Serializable'.  What is an .obj file?  Now
check out the following output statement from the script; for the life of me, I can't understand
it:

1) testListAddByIndex(org.apache.commons.collections.TestFastArrayList2)
junit.framework.AssertionFailedError: List should equal confirmed expected:<[0, , One, 2, Three,
null, 4, One, 5.0, 6.0, Seven, Eight, Nine, 10, 11, 12, Thirteen, 14, 15, 16]> but was:<[0, , One,
2, Three, null, 4, One, 5.0, 6.0, Seven, Eight, Nine, 10, 11, 12, Thirteen, 14, 15, 16]>


The two lists look identical!  This is awfully strange-seeming.

I've thought of a way to speed up writes to the data structure even more while it's in fast mode,
but I haven't put it in yet.  Please take a look at the attached code and see if it looks like it
will be useful.  I spent much of my evening messing around with it, and now I'm going to bed.  The
class is called FastArrayList2, the test class is called TestFastArrayList2, and I also threw in
the test-script results for good measure.  The test script has a method named compareSpeed() that
gives a rudimentary comparison of fast-mode read speed between the two versions.

Thanks,

Jeff

P.S.  I renamed setFast(boolean) and getFast() setFastModeEnabled(boolean) and
isFastModeEnabled(), but I preserved the old signatures too.  JKV


__________________________________________________
Do you Yahoo!?
Yahoo! Web Hosting - Let the expert host your site
http://webhosting.yahoo.com

Re: [collections][SUBMIT] A faster version of FastArrayList

[Stephen Colebourne <sc...@btopenworld.com>]

I am currently uncertain as to whether to commit this. The problem lies with
serialization.

The current FastArrayList holds a reference to an ArrayList, your
replacement holds references to an Object[] and a size (plus some other
things that should be transient). The question is whether we try to maintain
binary compatability for serialised object across releases. Any views ?

Otherwise the basic theory behind the changes seems sound.

Stephen

----- Original Message -----
From: "Jeff Varszegi" <jv...@yahoo.com>
> This version of FastArrayList looks to be from two to twenty times as fast
as the one currently in
> Collections.  (Differences are sure to be found on different machines and
JVMs, but it does seem
> to be much faster.)  I found over a twofold speed gain under the Java
1.4.0 'server' VM, as well
> as a twentyfold gain under the 1.4.0 'client' VM, on my machine (a laptop
running WinXP Pro, 512M,
> 1.2 GHz).  I really like the FastArrayList class, I just thought it would
be nice if it could be
> faster.
>
> I achieved the speed increase mainly by reducing method-call overhead.
Instead of wrapping
> instances of ArrayList, I took the code from ArrayList itself and adapted
it to the FastArrayList
> concept, directly swapping out arrays instead of ArrayList instances.  I
preserved the behavior of
> FastArrayList wherever appropriate, actually adding more synchronization
in a couple of places.
> I made a test script that extends TestList.  I had problems with the
script, but I really suspect
> that it is with the test script this time (and/or the way I have JUnit set
up).  At least, I find
> statements like the following very puzzling:
>
> 1)
testEmptyListSerialization(org.apache.commons.collections.TestFastArrayList2
)
> java.io.NotSerializableException: java.lang.Object
> 3)
testEmptyListCompatibility(org.apache.commons.collections.TestFastArrayList2
)
> java.io.FileNotFoundException:
data\test\FastArrayList2.emptyCollection.version1.obj (The system
> cannot find the path specified)
>
> The only serialization code in the class is 'implements Serializable'.
What is an .obj file?  Now
> check out the following output statement from the script; for the life of
me, I can't understand
> it:
>
> 1) testListAddByIndex(org.apache.commons.collections.TestFastArrayList2)
> junit.framework.AssertionFailedError: List should equal confirmed
expected:<[0, , One, 2, Three,
> null, 4, One, 5.0, 6.0, Seven, Eight, Nine, 10, 11, 12, Thirteen, 14, 15,
16]> but was:<[0, , One,
> 2, Three, null, 4, One, 5.0, 6.0, Seven, Eight, Nine, 10, 11, 12,
Thirteen, 14, 15, 16]>
>
>
> The two lists look identical!  This is awfully strange-seeming.
>
> I've thought of a way to speed up writes to the data structure even more
while it's in fast mode,
> but I haven't put it in yet.  Please take a look at the attached code and
see if it looks like it
> will be useful.  I spent much of my evening messing around with it, and
now I'm going to bed.  The
> class is called FastArrayList2, the test class is called
TestFastArrayList2, and I also threw in
> the test-script results for good measure.  The test script has a method
named compareSpeed() that
> gives a rudimentary comparison of fast-mode read speed between the two
versions.
>
> Thanks,
>
> Jeff
>
> P.S.  I renamed setFast(boolean) and getFast() setFastModeEnabled(boolean)
and
> isFastModeEnabled(), but I preserved the old signatures too.  JKV
>
>
> __________________________________________________
> Do you Yahoo!?
> Yahoo! Web Hosting - Let the expert host your site
> http://webhosting.yahoo.com


----------------------------------------------------------------------------
----


> --
> To unsubscribe, e-mail:
<ma...@jakarta.apache.org>
> For additional commands, e-mail:
<ma...@jakarta.apache.org>


--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>