Skip to Content.
Sympa Menu

xom-interest - Re: [XOM-interest] Possible ArrayList optimization

xom-interest AT

Subject: XOM API for Processing XML with Java

List archive

Chronological Thread  
  • From: dirk bergstrom <dirk AT>
  • To: Elliotte Rusty Harold <elharo AT>
  • Cc: xom-interest <xom-interest AT>
  • Subject: Re: [XOM-interest] Possible ArrayList optimization
  • Date: Fri, 09 May 2003 16:48:17 -0700

Elliotte Rusty Harold expounded at length upon:
> Internally XOM uses ArrayLists to hold both children and attributes.
> While debugging an unrelated test failure (I hate EBCDIC!) I noticed
> that these array lists are created by default with a capacity of 10.
> That means each Element object has at least 80 bytes of overhead that a
> lot of the time it doesn't need. I'm going to experiment with setting
> the initial capacity of both the elements and the attributes lists to 0
> and 1 and see if that cuts down on memory usage noticeably.

0 and 1 is probably too small, and will result in extra arraycopy operations.

> I am a little worried that dropping the capacity might impact speed, so
> if anyone knows more about array list opitmization, please pipe up!

i know just enough to be dangerous, but here goes:

ArrayList uses an array internally. whenever you try to add an element
that wouldn't fit into the array, it makes a new array, and uses
System.arraycopy() to copy from the old to new arrays.

java 1.4 uses the following method (download the java source, it makes
answering this sort of question a lot easier):

public void ensureCapacity(int minCapacity) {
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = new Object[newCapacity];
System.arraycopy(oldData, 0, elementData, 0, size);

so if your initial size is one, as you add elements, it will do the following:

first add - (1 element)
second add - set size to 2, copy array (2 elements)
third add - set size to 4 copy array (3 elements)
fourth add - (4 elements)
fifth add - set size to 7, copy array (5 elements)

admittedly, the arraycopies are pretty quick for only a few elements. i
suspect that the optimal size might be three or four, since that gets you
a few adds without a copy, but doesn't burn a ton of memory.

Dirk Bergstrom dirk AT
Juniper Networks Inc., Computer Geek
Tel: 408.745.3182 Fax: 408.745.8905

Archive powered by MHonArc 2.6.24.

Top of Page