Skip to Content.
Sympa Menu

xom-interest - Re: [XOM-interest] DOMConverter bug

xom-interest AT lists.ibiblio.org

Subject: XOM API for Processing XML with Java

List archive

Chronological Thread  
  • From: Elliotte Rusty Harold <elharo AT metalab.unc.edu>
  • To: Wolfgang Hoschek <whoschek AT lbl.gov>
  • Cc: xom-interest AT lists.ibiblio.org
  • Subject: Re: [XOM-interest] DOMConverter bug
  • Date: Sat, 21 Aug 2004 11:37:10 -0400

At 11:01 PM -0700 8/20/04, Wolfgang Hoschek wrote:

I'd go for a codebase that's easy to understand and maintain (implies a good chance of being bug free) over one that tries to account for practically irrelevant, obscure failure modes (and fails for practically relevant cases). Same argument applies to other iterative tree walking XOM methods, IMHO.

I suspect it's buggy because it's poorly written. After pouring through it again to fix the latest bugs, I think I see how to rewrite these methods more cleanly if I need to do this again.

BTW, a side effect of the iterative version is that it seems to exponentially slow down with increasing depth level; a behaviour not observed for the recursive versions (xom-1.0d25).

If you have measurements of this, I'd like to see them. I'm not surprised that performance is worse. The iterative version uses instanceof in several places, and that's a bad performance hit. The core classes have package protected methods that let them avoid this, but I can't access those from DOMConverter. :-(

I am surprised that the hit is exponential. Are you sure of that? If you could demonstrate that, I would look for ways to fix it, and/or consider switching back to the recursive solution. Possibly the use of indexOf might account for this. The algorithm used should be similar to recursion if certain operations such as getting the parent, getting the first child, and getting the next sibling are O(1). Getting the parent and getting the first child are O(1) but getting the next sibling is not. It's actually a relatively expensive operation in XOM since I made a deliberate decision not to store the extra pointers making this order(1) would require. It's a real speed-memory tradeoff. However, I do traverse the tree in a particular order, so it might be possible to use a slightly different algorithm that does not exhibit this behavior.

--

Elliotte Rusty Harold
elharo AT metalab.unc.edu
Effective XML (Addison-Wesley, 2003)
http://www.cafeconleche.org/books/effectivexml
http://www.amazon.com/exec/obidos/ISBN%3D0321150406/ref%3Dnosim/cafeaulaitA




Archive powered by MHonArc 2.6.24.

Top of Page