Skip to Content.
Sympa Menu

xom-interest - [XOM-interest] indexOf O(1) patch?

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: xom-interest AT lists.ibiblio.org
  • Subject: [XOM-interest] indexOf O(1) patch?
  • Date: Mon, 31 Jan 2005 16:36:06 -0800

I'm still considering and reconsidering options for reducing ParentNode.indexOf(Node) from linear to constant time, contemplating the advantages and disadvantages of impacts of various schemes and use cases. If anyone has any particular ideas/insights I'd appreciate your feedback...

The point of it all is to find the index of any given child node within a parent node (+-1), so one can jump to the next sibling in O(1).

This enables all sorts of algorithms to use indexOf() in simple yet efficient manners. For example, XOM's ParentNode.remove(Node) can exploit it, as well as ParentNode.replace(Node old, Node new), and non-recursive treewalkers in XOM could use it instead of a complicated index stack, such as Element.getValue(), Element.toXML(), DOMConverter.convert(xomElement), etc..

More interesting for the XPath and XQuery case is that it can be used for simple yet efficient backtracking logic in treewalking axis iterators, and for sibling related axis operations. That is, the descendant, descendant-or-self, following, following-sibling, preceding and preceding-sibling axes.

An indexOf() with constant time behaviour eliminates the need for the Saxon-XOM NodeWrapper to keep track of the index in more complicated manners. I've done some more performance work on the axis implementations of the NodeWrapper for Nux, using the safe variant of the O(1) ParentNode.indexOf() patch given at the end of this mail, plus other unrelated XPath improvements. The result is that those axes are now about 4-6 times faster than before. For example the iterator for the descendant axis now runs at some 60 MB/s (with the child axis continueing to run at some 200 MB/s). I speculate that performance is now roughly on par with Saxon's native tinytree, for example when running the simple XPath benchmark recently discussed on the the mailing list.

With that out of the way, let's discuss the indexOf() patch itself:

The time complexity of insert and remove are the same, with and without the patch, because the children of a ParentNode are an ArrayList. Of course, ArrayLists are designed for insertions and removals at the tail of the list, not its head.
The constant factors differ with the patch, but the good news is that updating the index on insert/remove is essentially a null operation if it happens at the end of the children list (the common case, for example for parsing a document), and has low extra overhead even if it happens in middle or the head of the list (the rare case).

The additional memory (4 bytes) required per Node doesn't hurt much either, considering how much memory is consumed by all sorts of other info in node, element, text, etc. Perhaps Elliotte can profile memory by parsing documents with java -verbose:gc and look at the final max memory consumption.

For some more background, below I'm copying some thoughts Mike Kay and me had on this issue. The source code is at the end of the mail.


Have you considered maintaining an index position which is guaranteed
monotonic but not guaranteed to have no gaps? That immediately reduces the
cost for remove, and potentially also for insert. For example, when
inserting at the end, number the node as the number for the previous node
+2048; when inserting between two nodes, choose the number half way between;
renumber only when you run out of numbers.

Well, the point of it all is to find the array index of "myself" (+-1), so one can jump to the next sibling in O(1).
Above scheme couldn't do that it seems.


I'm concerned here with worst-case scenarios, like adding each new node as
the first sibling. That could have chronic performance when adding 10,000
children to the same parent. (But I guess it would anyway, if using an
ArrayList rather than linked list?)

Right. An ArrayList (no matter if with or without the O(1) patch) has quadratic time complexity in this case.
An ArrayList isn't designed or intended for this. Luckily I can hardly see any meaningful practical use cases that would need to do a lot of inserts/removes at the head of a long children list. Plus, on average an element only has 1-3 children. Presumably that (and the fact that ArrayList performance and memory consumption is *very* good for all other cases, including iteration) was the reason Elliotte chose is over LinkedList. So the patch seems consistent with the overall XOM choice.


Another solution would be to do the
numbering lazily - set the number initially to -1 and renumber all the
siblings at once when the numbers are first needed.

A possibility, but it would require more ParentNode memory to hold the current state (numbered/not numbered), plus setting the ParentNode flag to false on insert/remove. It would loose out under some scenarios where inserts/removes are interspersed with calls to indexOf(), which would be the case for ParentNodce.replaceChild(Node old, Node new). I still think that given the main use cases, the original O(1) schema is the best.


Finally, source code for the proposed patches follows. They are safe and fully retain the original semantics if you think about it carefully.

Node.java:

private int siblingPosition = 1; // used by ParentNode.indexOf() // WH
final void setSiblingPosition(int position) { siblingPosition = position; }
final int getSiblingPosition() { return siblingPosition; }

ParentNode.java:

public int indexOf(Node child) { // returns in constant time
return (child != null && child.getParent() == this) ?
child.getSiblingPosition() :
-1; // WH
}

final void fastInsertChild(Node child, int position) {
if (children == null) children = new ArrayList(1);
children.add(position, child);
child.setParent(this);
child.setSiblingPosition(position); // WH
for (int i=getChildCount(); --i > position; )
((Node)children.get(i)).setSiblingPosition(i);
}

public Node removeChild(int position) {
if (children == null) {
throw new IndexOutOfBoundsException(
"This node has no children"
);
}
Node removed = (Node) children.get(position);
if (removed.isElement()) fillInBaseURI((Element) removed);
children.remove(position);
removed.setParent(null);
for (int i=children.size(); --i >= position; ) { // WH
((Node)children.get(i)).setSiblingPosition(i);
}
return removed;

}

For example, as a result some other methods can immediately take advantage of the O(1) indexOf() behaviour:

public Node removeChild(Node child) {

int position = indexOf(child); // WH !!
if (position == -1) {
throw new NoSuchChildException(
"Child does not belong to this node"
);
}
return removeChild(position);
}

public void replaceChild(Node oldChild, Node newChild) {

if (oldChild == null) {
throw new NullPointerException(
"Tried to replace null child"
);
}
if (newChild == null) {
throw new NullPointerException(
"Tried to replace child with null"
);
}
// check is not needed anymore
// if (children == null) {
// throw new NoSuchChildException(
// "Reference node is not a child of this node."
// );
// }
// int position = children.indexOf(oldChild);
int position = indexOf(oldChild); // WH
if (position == -1) {
throw new NoSuchChildException(
"Reference node is not a child of this node."
);
}

if (oldChild == newChild) return;

insertionAllowed(newChild, position);
removeChild(position);
insertChild(newChild, position);

}





Archive powered by MHonArc 2.6.24.

Top of Page