Xalan optimizations ...

[Jose Alberto Fernandez <JF...@viquity.com>]

This is an excerpt of a messagfe sent to the XSL list.
Can someone comment on the optimizations that Xalan J 2 does today?

"> 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."

Jose Alberto