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: Wolfgang Hoschek <whoschek AT lbl.gov>
  • To: Elliotte Rusty Harold <elharo AT metalab.unc.edu>
  • Cc: xom-interest AT lists.ibiblio.org
  • Subject: Re: [XOM-interest] DOMConverter bug
  • Date: Sat, 21 Aug 2004 10:06:09 -0700

On Aug 21, 2004, at 8:37 AM, Elliotte Rusty Harold wrote:

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.

I suspect the recursive versions were not buggy because they exhibit an obvious inherent logic that makes it hard to get things wrong in the first place.


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.

Just run the stackoverflow test snippet I sent previously with the d25 DOMConverter (rest of xom at 1.0b2). See at which XML nesting depth the stack overflows. Then rerun with "time java ..." and press CTRL-C just before the stack overflows (right after 20498 has been printed). Write down the time reported by the "time" command. Then redo the exercise with the current DOMConverter (again CTRL-C after 20498 has been printed).

Result: 7 secs vs 34 secs runtime (and the ratio gets worse with increasing depth). The precise numbers don't matter, the ratio does.

What I outlined here is a quick and dirty way of checking things, and it could clearly be improved: Since getting the next sibling seems O(N), and since O(N) applied at every nesting level multiplies to O(N*M), one could probably write a worst-case test that creates many many siblings at every level, and hence stresses getting the next sibling routine a lot more than the snippet I sent, and the result would probably be an order of magnitude worse than the already bad ratio of 7 vs. 34 secs.

So far for performance, but keep in mind that the main argument I've been trying to make is not performance related, but simply software quality/bug related.

I'd be more than happy if you'd decide to call the iterative XOM work an interesting experiment that didn't quite work out as hoped for, and revert to the recursive versions in the places we had them historically. If you should come back to try and change something in one of those methods in a year or two you'll appreciate the obvious logic flow, gaining confidence that things are actually working correctly simply by looking at the code. Unit tests are good. Unit tests for clear obvious code are better.

Note to others who might follow this discussion thread: Changing to recursive versions would be purely internal and does not change any interface.





Archive powered by MHonArc 2.6.24.

Top of Page