RE: Optimisation (was Re[6]: Aggregate)

[Kay Michael <Michael dot Kay at icl dot com>]

> OK. I think my problem lies in the fact that I have never understood
> what 0(n-squared) and so on actually means.

Thanks to Davids Gamboc and Carlisle who have answered the theoretical part
of Jeni's question far better than I could.

> Mike, is it possible for you to sketch out the optimisations in Saxon

The ones that are relevant here are, I suppose, those that find an algorithm
for evaluating an expression that has lower complexity than the naive
algorithm.

Some examples:

$x < $y naively requires X*Y comparisons where X and Y are the cardinalities
of the two node-sets. Saxon evaluates it as min($x) < max($y) which requires
only O(X+Y) operations. It would be possible to optimise $x[not($x > .)]
using the same trick, but Saxon currently doesn't.

xsl:for-each with no xsl:sort naively requires to sort the selected nodes
into document order which would take O(n log n) operations. Saxon goes to
considerable pains to detect cases where the nodes are already naturally
sorted, reducing this to O(n).

$x[1] naively requires a comparison on each element of the list to see if
its position is equal to 1 (so it would be O(X)). Saxon just looks at the
first element, which is O(1).

not($x), where $x is a node-set, naively evaluates the node-set (which is
typically O(X), or even more naively O(X log X) if you were to eliminate
duplicates eagerly) and then tests to see if it is empty (which can be done
in O(1)). Saxon 5.5.1 will usually avoid evaluating the node-set and
eliminating duplicates, but not always, it depends how it is defined.

<xsl:number/> naively requires counting of the nodes that precede a given
node, which requires O(n) operations; therefore numbering a sequence of n
nodes requires O(n^2) operations. Saxon in some cases (but not all)
remembers the last node and its number, so that numbering a sequence of n
nodes becomes O(n).

I'm afraid that's a very incomplete list, but perhaps it gives a flavour.



Mike Kay


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list