[jdom-interest] About JDOM performance

[Ken Rune Helland]

>Subject: Re: [jdom-interest] About JDOM performance
>To: Ken Rune Helland <kenh at csc.no>
>X-Mailer: Lotus Notes Release 5.0.3 (Intl) 21 March 2000
>From: phil at triloggroup.com
>Date: Tue, 22 May 2001 15:16:22 +0200
>X-MIMETrack: Serialize by Router on netfinity/TRILOG(Release 5.0.3 
>(Intl)|21 March 2000) at
>  05/22/2001 05:15:43 PM
>
>
>About the LinkedList/ArrayList debate, I both agree and disagree with you.
>You're write when saying that ArrayList are better when the initial size 
>is known at creation time and when saying that
>inserting an item at the list top may be inefficient. But what inefficient 
>really means?
>I attached a simple prog source and a graph of the JProbe result.
>
>Althrough this test may be naive, the result is without any ambiguity: 
>adding an element at the beggining of a list is
>effectively faster on the linked list (39.009s compared to 48475s). But 
>this is not significant regarding the time taken
>to add an element at the end of the list: the array did that in 6,200 
>while the linked list remains constant at 38,673s.
>Up to 6 times faster !!
>And we can consider that we were using large list (average of 50,000 items)
>
> >>>But in the most time-critcal (IMHO) case is building a document from 
> an external source and when parsing a document
>you are inserting an unknown number of items in the list<<<
>Effectively. But when parsing a document from, for example, a text 
>datasource, the builder (SAXBuilder...) will add the
>objects at the end of the list, not at the beggining. And this is really 
>faster (6x) with an array list, regarding less
>the number of items.
>
> >>>But since we already have introduced factories for builders it woud be 
> easy to get the builders<<<
>I was supprised (and happy) by this new capability since I spoked about 
>that with Jason months ago, when he said it was
>of no interest...
>But, frankly, I think that having a factory for the collection is not 
>necessary. Perhap's we may simply change the data
>members from LinkedList to List and let a derived class to create its own 
>list, either in the constructor or by
>overwriting the add...() method.
>
>Phil.
>
>
>(See attached file: colprof.gif)(See attached file: colprof2.gif)(See 
>attached file: TstCollection.java)
>
>

This results really suprises me, ArrayList has to move a lot of references 
when inserting in front
of the list, that copying on average 50.000 references is almost as fast as 
creating a ListItmem
object and setting five references must mean the computer time overhead 
when creating new objects
must be VERY large, even considering that System.arraycopy() is a low level 
native function.

And also when inserting in the back ArrayList has to create a new 50% 
larger array and copy all references to the new array every time the old 
array is full. Wich means most inserts shoud be very fast but once in a 
while there woud be a very slow one, obviusly not as slow as I exspected.

On the other hand you risk having a ArrayList using a 150.000 size array 
holding a 100.000 objects List.


KenR



-------------- next part --------------
A non-text attachment was scrubbed...
Name: colprof.gif
Type: image/gif
Size: 18195 bytes
Desc: not available
Url : http://jdom.org/pipermail/jdom-interest/attachments/20010522/488feb4d/colprof.gif
-------------- next part --------------
A non-text attachment was scrubbed...
Name: colprof2.gif
Type: image/gif
Size: 5632 bytes
Desc: not available
Url : http://jdom.org/pipermail/jdom-interest/attachments/20010522/488feb4d/colprof2.gif
-------------- next part --------------
import java.util.*;

public class TstCollection {

    private static String objectToAdd = "BlahBlah";
    private static int numberOfLoop   = 100;
    private static int numberOfItems  = 10000;

    private static void TstLinkedList() {
        for( int i=0; i<numberOfLoop; i++ ) {
            addToLinkedList(new LinkedList());
        }
        for( int i=0; i<numberOfLoop; i++ ) {
            insertToLinkedList(new LinkedList());
        }
    }
    private static void addToLinkedList(LinkedList list) {
        for( int i=0; i<numberOfItems; i++ ) {
            list.add(objectToAdd);
        }
    }
    private static void insertToLinkedList(LinkedList list) {
        for( int i=0; i<numberOfItems; i++ ) {
            list.addFirst(objectToAdd);
        }
    }

    private static void TstArrayList() {
        for( int i=0; i<numberOfLoop; i++ ) {
            addToArrayList(new ArrayList());
        }
        for( int i=0; i<numberOfLoop; i++ ) {
            insertToArrayList(new ArrayList());
        }
    }
    private static void addToArrayList(ArrayList list) {
        for( int i=0; i<numberOfItems; i++ ) {
            list.add(objectToAdd);
        }
    }
    private static void insertToArrayList(ArrayList list) {
        for( int i=0; i<numberOfItems; i++ ) {
            list.add(0,objectToAdd);
        }
    }

    public static void main( String[] args ) {
        long start = System.currentTimeMillis();
        TstLinkedList();
        TstArrayList();
        long end = System.currentTimeMillis();
        System.out.println( "Global test executed in "+(end-start)+" ms" );
    }
}