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