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

Joseph Bowbeer jozart at csi.com
Thu Apr 12 20:55:15 PDT 2001


> So we had a great JDOM BOF (Birds of a Feather) session
> at SD West last night.

Thanks, Jason.  Wish I'd been there.  I have comments on two items.


> * Do we keep original list data in case of illegal add?
>
> YES, absolutely.
>

That's how I sided initially, but the fact that IllegalAddException is
unchecked, plus concerns about interaction with subclass implementions
caused me to change my mind.  Please see:

 http://lists.denveronline.net/lists/jdom-interest/2001-April/005620.html

In the case of setMixedContent, I suggest we view it as a composite of more
primitive operations.  We should strive to make the primitive 'add'
operations failure atomic, but, on failure, we should simply abort
setMixedContent at the point of failure.


By the way, tweaking JDOM for subclassing is a TODO topic in itself.  There
are some specific things we can do, such as never calling overridable
methods from the constructors or the "pseudo-constructors" (clone and
readObject).   There are also some design/documentation issues concerning
what subclasses are allowed to do.  I'll send this TODO item along with some
others in a separate message.


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


> * Keep getSerializedForm() methods?
>
> No, deprecate and remove them.
>

OK.  So I guess it doesn't matter that Attribute.getSerializedForm is broken
with respect to the special characters [& < > "] and the characters greater
than '\u007f' ...

--
Joe Bowbeer






More information about the jdom-interest mailing list