xom-interest AT lists.ibiblio.org
Subject: XOM API for Processing XML with Java
List archive
- 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
-
[XOM-interest] DOMConverter bug,
Wolfgang Hoschek, 08/19/2004
-
Re: [XOM-interest] DOMConverter bug,
Elliotte Rusty Harold, 08/20/2004
- Re: [XOM-interest] DOMConverter bug, Elliotte Rusty Harold, 08/20/2004
-
Re: [XOM-interest] DOMConverter bug,
Elliotte Rusty Harold, 08/20/2004
-
Re: [XOM-interest] DOMConverter bug,
Wolfgang Hoschek, 08/21/2004
-
Re: [XOM-interest] DOMConverter bug,
Elliotte Rusty Harold, 08/21/2004
- Re: [XOM-interest] DOMConverter bug, John Cowan, 08/21/2004
-
Re: [XOM-interest] DOMConverter bug,
Wolfgang Hoschek, 08/21/2004
-
[XOM-interest] XOM in an applet,
Ken Kast, 08/22/2004
-
Re: [XOM-interest] XOM in an applet,
Elliotte Rusty Harold, 08/22/2004
- Re: [XOM-interest] XOM in an applet, Ken Kast, 08/23/2004
- Re: [XOM-interest] XOM in an applet, Elliotte Rusty Harold, 08/23/2004
- Re: [XOM-interest] XOM in an applet, Elliotte Rusty Harold, 08/23/2004
-
Re: [XOM-interest] XOM in an applet,
Elliotte Rusty Harold, 08/22/2004
-
[XOM-interest] XOM in an applet,
Ken Kast, 08/22/2004
-
Re: [XOM-interest] DOMConverter bug,
Elliotte Rusty Harold, 08/21/2004
-
Re: [XOM-interest] DOMConverter bug,
Wolfgang Hoschek, 08/21/2004
-
Re: [XOM-interest] DOMConverter bug,
Elliotte Rusty Harold, 08/20/2004
Archive powered by MHonArc 2.6.24.