[jdom-interest] JDOM BOF at SD West: problem resolving

[Dennis Sosnoski]

I agree completely with Joe on the ArrayList issue. The only case where a linked list
has an advantage is where you frequently go through the list, adding or removing
items as you go. Even here, ArrayList performance will beat SinglyLinkedList except
for large lists (probably about 20 items or more).

The reason for the performance hit with SinglyLinkedList is the need for separate
object allocations for each item in the list.

Using ArrayList would also allow indexed access to children, so that getChild(int
index) and getChildCount() methods could be provided. For all the processing I've
done with JDOM (using it in three projects, so far) I could have used these methods
exclusively for my access to JDOM documents. As it is, I have to use the
getChildren() method which constructs a copy of the list.

  - Dennis

Dennis M. Sosnoski
Sosnoski Software Solutions, Inc.
http://www.sosnoski.com

Joseph Bowbeer wrote:

> > * Singly or doubly linked list?
> >
> > Singly was unanimously agreed on, at least for now.
> > In the rare circumstances where you need to iterate
> > backward or do indexed access, you can always get
> > the List, copy it to your own List, and iterate backward.
> > Makes the performance O(n).
> >
>
> When does SinglyLinkedList beat ArrayList?  I'd like to see the
> memory/performance benchmarks that are driving the SinglyLinkedList design.
>
> I know it's rude to beatup on something that isn't even implemented yet.  I
> support the iterative approach of implementing and testing, and so on.
> Still... Based on the comparison below, I don't see what SinglyLinkedList
> has to offer.
>
> Space: ArrayList is almost always more space efficient than *any* linked
> list.  One exception: remove most of the elements from the ArrayList without
> calling trimToCapacity.
>
> Time: ArrayList outperforms SinglyLinked list on *all* operations except
> add(beginning), remove(beginning), and clear() -- which aren't the most
> common ones.
>
> Compared to LinkedList, SinglyLinkedList is twice as slow, on average,
> performing random get(i) or set(i) operations.  This is because LinkedList
> will access the desired element starting at the head or the tail, depending
> on which end is closest.
>
>   n/4 = average LinkedList cost
>
>   n/2 = average SinglyLinkedList cost
>
> But the fact that SinglyLinked list is slower than LinkedList hardly matters
> because *any* linked list implementation is O(n) times slower than ArrayList
> when it comes to random access.
>
> Processing in reverse order is the real killer with SinglyLinkedList.  (And
> who would suspect, unless they happened to read the warning in the JDOM
> documentation?)  I think processing in reverse order is a common enough
> situation that it makes SinglyLinkedList a bad choice.  Time-ordered
> documents are one example where it's fairly common to start with the
> messages at the end (the most recent) and work backwards.