harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Catherine Hope <catherine.v.h...@googlemail.com>
Subject Re: [classlib][luni] Collections classes - code reviews and optimisations
Date Thu, 05 Aug 2010 10:12:02 GMT
I've done some analysis of the size of the backing arrays that are
constructed by the RI, by serializing ArrayLists on the RI and then reading
them back in on Harmony (the serialization spec saves the length of the
backing array).
The RI's grow heuristics differ from Harmony in that there's not a minimum
grow size - adding an element to a zero capacity ArrayList on the RI grows
it by just one element, whereas on Harmony the ArrayList will be grown by a
minimum of 12 elements.  So this may have an impact if lots of ArrayLists
are constructed that only add a few elements.  From some experimentation the
growth rate on the RI in the general case is to grow by the larger of the
size of Collection or 0.5*capacity (and then add 1 if it's the
0.5*capacity!), so:
>create an ArrayList and call addAll with 1000 element Collection
  size is 1000, capacity is 1000
>then call addAll with 1000 element Collection
  size is 2000, capacity is 2000
>then call addAll with 50 element Collection
  size is 2050, capacity is 3001
>then call addAll with 1000 element Collection
  size is 3050, capacity is 4502

On Harmony the growth rate is the larger of the size of the Collection or
0.5*size, so:
>create an ArrayList and call addAll with 1000 element Collection
  size is 1000, capacity is 1000
>then call addAll with 1000 element Collection
  size is 2000, capacity is 2000
>then call addAll with 50 element Collection
  size is 2050, capacity is 3000
>then call addAll with 1000 element Collection
  size is 3050, capacity is 3075

Therefore the arrays will grow at a slower rate on Harmony compared to the
RI.

I notice a difference between the Java 5 and Java 6 spec for ArrayList in
that the requirement that an ArrayList created from a Collection should have
capacity 110% of the Collection size has been removed, so maybe we should
also remove this from the Java 6 branch of ArrayList.  This seems to be the
only change between the specs.

I also noticed going through the spec that the doc for the add and addAll
methods that take a location state that all subsequent elements should be
shifted to the right and therefore space should only be added onto the end
of the array, and similarly for remove with a location.  Currently we try
and use both ends of the array, so this is against the spec, but it isn't
something that can be tested for (since the backing array isn't accessible
and even when it's serialized only the length of the array is stored and not
the index of the first element).

Cath

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message