Re: [xsl] how to estimate speed of a transformation

Subject: Re: [xsl] how to estimate speed of a transformation
From: David Carlisle <davidc@xxxxxxxxx>
Date: Thu, 11 Dec 2003 13:57:22 GMT
   + access by position to a nodeset exhibits constant time in advanced implementations (and linear in
    others);
  - accessing a nodeset by position, since there are implementations with access time proportional
    to the position() in a nodeset.

If the node set is being calculated (or re-calculated) you would expect
the more optimised processors to have accesss times that increase
greatly with [n].
If I go (//*)[1]  and (//*)[1001] then a system that searches the entire
document to build (//*) and then selects the 1st and 1001st  entries may
well do bioth of these in the same time, but both slowly, however a
system that stops building the node set as soon as the numeric filter is
satisfied will find (//*)[1]  but finding (//*)[1001]  will require
time presumably depending on the depth of the tree.

Even if you have the node set in a variable and go $x[10001]  you can't
know if it is being re-calculated.

In another message you said

> Why don't you think it (delayed construction of the hash table) should
> not be relied upon  

Because the processing model of XSLT isn't sufficiently constrained that
these kind of constraints can be made. In the case of xsl:key for
example, you can't insist that creation of the hash table is delayed as
the spec explictly does not insist that a hash table is built at all,
XSLT is almost soley specified by expected result, not assuming any
processing model, and given that, it is very hard to make the kind of
assurances that you are seeking. I'm not sure if you can even really
specify what it means to do tail recursion elimination unless you have
some explict stack model for implementing template calls.

It is certainly the case that in a highly optimising system that can
recognise repeated expressions and produce indices automatically, then
xsl:key could be a no-op as just using the equivalent xpath would
automatically be indexed and produce the same result. Similarly a
system that is highly unoptimised, could implement key() by just
replacing it by the equivaent xpath expression, so again xsl:key
wouldn't make any dofference. In practice though, systems are not at
either extreme, and the hint given by xsl:key that the system might like
to optimise that Xpath  appears to speed things up on most processors, i
don't think you can say more than that.

David

________________________________________________________________________
This e-mail has been scanned for all viruses by Star Internet. The
service is powered by MessageLabs. For more information on a proactive
anti-virus service working around the clock, around the globe, visit:
http://www.star.net.uk
________________________________________________________________________

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


Current Thread