Saxon diaries

Saxon has for a long time supported a number of implementations of the XDM tree model:

• Native Saxon implementations: the TinyTree, the LinkedTree, and a variant of the TinyTree called TinyTreeCondensed
• External object models: DOM, JDOM, DOM4J, XOM
• Newly added in the last few weeks: JDOM2, AXIOM

The addition of two more external models suggested it was time we did some measurements. We adapted our test driver for the XMark benchmark suite to work with any of the above models, and ran the queries to compare the results. The results quoted below are for the nominal 1Mb source document (actual size 1182530 bytes).

DOM of course is an interface rather than an implementation; the DOM used here was the Apache Xerces DOM.

First, memory usage: the table below gives the "expansion factor", that is, the amount of memory used divided by the number of bytes in the source XML document:

No great surprises there.

As for query performance, our first measurements showed some alarmingly bad performance on many of the external models for Q7. This query is dominated by traversal of the descendant axis. On some of the models this was taking almost 100 times as long as for the TinyTree. We know that the TinyTree is particularly good at traversing the descendant axis, but this ratio was worse than we expected. We found that the recursive algorithm used by some of the models was particularly inefficient, and replaced it with the non-recursive algorithm used by the LinkedTree, which significantly improved the figures. After this tuning exercise, the following table shows for each model, the average elapsed time compared with the TinyTree figure, together with the minimum and maximum values of this ratio.

This clearly shows that of the external object models, XOM is clearly out-performing the others. But even XOM is nearly four times slower than the TinyTree on average.

Finally, we also measured build time: the time taken to build the tree. The figures below are in ms:

Nothing dramatic here, except to note that Axiom appears to be very slow to build the tree.

The results here are of course not necessarily representative of other workloads. Notoriously, the XMark data does not use namespaces, and that could seriously distort the results. The XMark queries are also heavily optimized; for example, they probably do less sorting-into-document-order than your average workload, and that's an operation that can be very expensive with some object models. Nevertheless, any data is better than none, and publishing this may encourage some people to take another look at XOM. Unfortunately, most of the people who use DOM with Saxon do so out of ignorance, and they are the people who are least likely t read this article.

Footnote

A more detailed look at the XMark performance data showed that in many cases the worst-performing code in a number of the external model wrappers (XOM being a notable exception) was when navigating the descendant axis. We've changed some of the wrappers, notably DOM and DOM4J, to use the same algorithm as XOM was using for the descendant axis, and the result is a notable improvement. However, one concern about this algorithm is that it has the potential for very poor performance in trees with a high fan-out, for example, where one parent node has tens of thousands of immediate children. In the case of DOM the problem is compounded by the fact that DOM is an interface, not an implementation, so different implementations of DOM might exhibit very different performance characteristics: the right approach for one implementation is not necessarily the right approach for others.