xominterest AT lists.ibiblio.org
Subject: XOM API for Processing XML with Java
List archive
Re: [XOMinterest] Possible ArrayList optimization
 From: dirk bergstrom <dirk AT juniper.net>
 To: Elliotte Rusty Harold <elharo AT metalab.unc.edu>
 Cc: xominterest <xominterest AT lists.ibiblio.org>
 Subject: Re: [XOMinterest] 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) {
modCount++;
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)
etc.
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.net
_____________________________________________
Juniper Networks Inc., Computer Geek
Tel: 408.745.3182 Fax: 408.745.8905

[XOMinterest] Possible ArrayList optimization,
Elliotte Rusty Harold, 05/09/2003
 Re: [XOMinterest] Possible ArrayList optimization, John Cowan, 05/09/2003

Re: [XOMinterest] Possible ArrayList optimization,
dirk bergstrom, 05/09/2003

Re: [XOMinterest] Possible ArrayList optimization,
Elliotte Rusty Harold, 05/09/2003
 Re: [XOMinterest] Possible ArrayList optimization, Elliotte Rusty Harold, 05/11/2003

Re: [XOMinterest] Possible ArrayList optimization,
Elliotte Rusty Harold, 05/09/2003

Re: [XOMinterest] Possible ArrayList optimization,
Bradley S. Huffman, 05/09/2003
 Re: [XOMinterest] Possible ArrayList optimization, Elliotte Rusty Harold, 05/10/2003

Re: [XOMinterest] Possible ArrayList optimization,
Elliotte Rusty Harold, 05/11/2003

Re: [XOMinterest] Possible ArrayList optimization,
Bradley S. Huffman, 05/12/2003
 Re: [XOMinterest] Possible ArrayList optimization, Elliotte Rusty Harold, 05/12/2003

Re: [XOMinterest] Possible ArrayList optimization,
Bradley S. Huffman, 05/12/2003

Re: [XOMinterest] Possible ArrayList optimization,
Janek Bogucki, 05/11/2003

Re: [XOMinterest] Possible ArrayList optimization,
Elliotte Rusty Harold, 05/12/2003
 Re: [XOMinterest] Possible ArrayList optimization, dirk bergstrom, 05/12/2003

Re: [XOMinterest] Possible ArrayList optimization,
Elliotte Rusty Harold, 05/12/2003
Archive powered by MHonArc 2.6.24.