The estimation of the complexity cannot simply be derived from a simple
parsing and analysis of the stylesheet. It depends on the processor
implementation, the implementation of the JVM if using one, and on the
version of the processor used.
For XSLT, as well as for most programming languages, it is possible
to estimate complexity for a non-optimizing implementation; such as
James Clark's XT, which is very fast but does not do much beyond verbose
interpretation of the transformation.
The fact is that, due to restrictions of the data model of XSLT, there
are several optimizations which are always possible and are caused not
by sophistication of an underlying layer, but by features of the language
itself, that is, XSLT.
My questions are following:
- what are these optimizations?
- how these optimizations affect computation complexity for certain
operations?
- how 'much' of the 'mandatory' optimizations is implemented in each of
widely used
implementations?
These questions have no relation to either implementation language or
execution platform.
They should have their answers regardless of the implementation media.
Having answers to these questions would help program advanced algorithms
adequately,
without recourse to testing with each of a dozen of available
implementations. In
particular, while writing stylesheets with only a basic implementation in
mind helps
ensure that a stylesheet behaves adequately (in terms of memory usage and
speed) in
the worst case, knowing which expressions are in fact evaluated
recurrently and which
data structures are re-used can help in constructing programs that benefit
from optimizations
when the optimizations are available. Again, the optimizations of this
class should not
be an 'art', they can be specified formally and in fact are features of
the language.
This is an example of wishful thinking -- it is unrealistic to have the
answers to these questions for all XSLT processors or even for a fixed set
of XSLT processors and these answers are going to change considerably with
time.
It seems to me that the developers of XSLT processors, who replied said in
essence just that.
Also, it is strange for an XSLTprogrammer to feel inconvenienced from the
fact that some XSLT processors perform advanced optimizations thus
devaluating his efforts to implement an "optimal" algorithm for a given
problem.
On the contrary, every such optimization *is* welcome! It would be nice if
more XSLT developers implemented the optimizations that their colleagus have
done and if this process would go on.
The only correct answer to such questions is benchmarking the different XSLT
processors. This is an art in itself.
=====
Cheers,
Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list