XOM API for Processing XML with Java

[Wolfgang Hoschek <whoschek AT lbl.gov>]

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);

    }