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: "Karl Waclawek" <karl AT>
  • To: "xom-interest" <xom-interest AT>
  • 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() {
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
- 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.


Archive powered by MHonArc 2.6.24.

Top of Page