[prev in list] [next in list] [prev in thread] [next in thread] 

List:       xom-interest
Subject:    Re: [XOM-interest] Possible ArrayList optimization
From:       "Karl Waclawek" <karl () waclawek ! net>
Date:       2003-05-13 20:48:55
Message-ID: 016001c31991$1192ede0$9e539696 () citkwaclaww2k
[Download RAW message or body]


> >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


[prev in list] [next in list] [prev in thread] [next in thread]