Skip to Content.
Sympa Menu

xom-interest - Re: [XOM-interest] Unreachable block?

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 Harold <elharo AT metalab.unc.edu>
  • Cc: xom-interest <xom-interest AT lists.ibiblio.org>
  • Subject: Re: [XOM-interest] Unreachable block?
  • Date: Wed, 1 Dec 2004 09:41:36 -0800

Checking for this.getParent() != null is cheapest and almost always short-circuits the rest of the checks.
But the difference is not large. Rather, it seems the problem with insertChild(...) has more to do with lack of inlining and lack of memory locality than the performance of code in insertionAllowed().

By the way, thinking about this I suspect the unproven hypothesis I added to ParentNode recently ("it is significantly faster to construct documents from the top down than the bottom up. That is, one should add an element to its parent before adding its children. This short-circuits some possibly expensive checks.") is in fact false. I don't think it makes a difference.

That probably a good assessment.
Wolfgang.

On Dec 1, 2004, at 4:21 AM, Elliotte Harold wrote:

Wolfgang Hoschek wrote:
I see. However, it seems you can reformulate the check as follows
else if (this.getParent() != null && child.getChildCount() > 0 && isCycle(child, this.getParent())) {
throw new CycleException(
"Cannot add an ancestor as a child");
}


I'm not sure that's a big help because if the parent is null thats caught in the second pass through the loop in insertionAllowed:

private static boolean isCycle(Node child, ParentNode parent) {

while (parent != null) {
if (parent == child) return true;
parent = parent.getParent();
}
return false;

}


Possibly I could eliminate the first pass through the loop because it's redundant. insertionAllowed has already checked that the parent is not the child:

else if (child.isElement()) {
if (child == this) {
throw new CycleException(
"Cannot add a node to itself");
}
else if (child.getChildCount() > 0 && isCycle(child, this)) {
throw new CycleException(
"Cannot add an ancestor as a child");
}
return;
}


That is, I could rewrite isCycle like this:

parent = parent.getParent();
while (parent != null) {
if (parent == child) return true;
parent = parent.getParent();
}
return false;

If I do this I should probably just pull the complete cycle check into the same method for clarity rather than having half of it in insertionAllowed and half in isCycle(). I doubt the savings in execution time is noticeable.

By the way, thinking about this I suspect the unproven hypothesis I added to ParentNode recently ("it is significantly faster to construct documents from the top down than the bottom up. That is, one should add an element to its parent before adding its children. This short-circuits some possibly expensive checks.") is in fact false. I don't think it makes a difference.

--
Elliotte Rusty Harold elharo AT metalab.unc.edu
XML in a Nutshell 3rd Edition Just Published!
http://www.cafeconleche.org/books/xian3/
http://www.amazon.com/exec/obidos/ISBN=0596007647/cafeaulaitA/ref=nosim





Archive powered by MHonArc 2.6.24.

Top of Page