Skip to Content.
Sympa Menu

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

xom-interest AT lists.ibiblio.org

Subject: XOM API for Processing XML with Java

List archive

Chronological Thread  
  • From: "Karl Waclawek" <karl AT waclawek.net>
  • To: "xom-interest" <xom-interest AT lists.ibiblio.org>
  • Subject: Re: [XOM-interest] Possible ArrayList optimization
  • Date: Tue, 13 May 2003 16:48:55 -0400


> >well, you probably don't want to start too big, since as you build a
> >document you'll have un-trimmed ArrayLists for many of the nodes.
>
> No, I was thinking you'd call trimToSize() from the endElement()
> method, not the endDocument() method. This wouldn't have more than a
> few untrimmed elements at any one time. The default of 10 may be
> adequate.

This is a comment from a non-Java person, so please forgive
me when I am talking nonsense:

Having seen the code for trimToSize in another message:

public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
Object oldData[] = elementData;
elementData = new Object[size];
System.arraycopy(oldData, 0, elementData, 0, size);
}
}

It seems every call copies the array. Now if the runtime is smart
enough to avoid copying when re-sizing memory in place, this should be OK.

However, the approach often used in other languages, is like this:
- pre-allocate a working buffer (array) sized to the biggest size one can
expect
- then on every iteration simply write array items to this buffer, starting
at index 0, overwriting existing items, and keeping track of their count
- and at the end of the iteration, allocate a correctly sized new array
and copy the items out of the buffer as shown above (System.arraycopy)

That is one allocation for the working buffer (which can be pre-allocated),
and one array allocation plus array copy per iteration.
The working buffer can be re-sized should it turn out to be too small.
The scheme I use for that is to extend it by a given percentage when
the limit is hit, or even to double it if one can assume that this
does not become excessive.

Karl





Archive powered by MHonArc 2.6.24.

Top of Page