This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
Re: Re: topological sort
Jeni Tennison wrote:
>
> Hi Joerg,
> > Xalan shows a small but overall insignificant improvment.
[...]
> It might be that Xalan isn't optimising the test. Anyway, I took
> another look and it might be that you can make this more efficient:
>
> <xsl:if test="count(struct)>count($processed)">
> <xsl:variable name="nextnodes"
> select="struct[not($processed/name=name)
> and not(field/type/ref[not(. = $processed/name)])]"/>
> <xsl:if test="$nextnodes">
> <xsl:call-template name="process">
> <xsl:with-param name="nodes" select="$nextnodes"/>
> <xsl:with-param name="finished" select="$processed"/>
> </xsl:call-template>
> </xsl:if>
> </xsl:if>
>
> [....] Each iteration, the processor has to
> count all the struct nodes in the document, count all the processed
> nodes, and compare those two values. One way that you could make it
> more efficient is to store the number of struct nodes in a global
> variable:
Well, this is an artefact of an earlier Xalan version, which gave
me a cryptical error at the definition of the global variable. I did
not investigate further and forgot about this. Thank you for
remainding me. The speedup is still small but noticable.
Apart from this: a reasonably clever processor should recognize that
the value of count(struct) is constant and should store it after
first computation. Actually, recognizing that count(struct) is
constant is quite hard, i should have used count(/structs/struct)
instead which is more robust.
Furthermore, if i were to build an XSL processor, i would compute
the cardinality of a set while constructing it, which would make
count($setvar) O(1) instead of O(card($setvar)) if the variable has
been evaluated before. This way count($processed) would come for
free, because the set will have to be constructed in full anyway.
Of course, i don't know whether Xalan uses any of this optimisations.
> If you look at the $nextnodes variable definition, if all the structs
> are processed, then $nextnodes will be an empty node set. The inner
> xsl:if tests whether $nextnodes is empty before doing anything. I'm
> pretty sure, therefore, that you can get rid of the outer xsl:if
> altogether and retain the same logic: $nextnodes will sometimes be
> constructed when it doesn't need to be, but that's better than
> counting nodes in node sets every single time you recurse.
>
> Does that make it any faster?
Unfortunately, no: processing time rises from ~45 seconds to ~51 (Xalan-1).
Apparently the selection for the nextnodes variable is much slower than
the omitted comparision.
I tried to switch to Xalan-2 but release 2.0D06 bails out at the definition
of the variable "processed" :-(
> Jeni
Thanks!
J.Pietschmann
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list