RE: [xsl] XSLT 2.0 function - fastest node comparison

Subject: RE: [xsl] XSLT 2.0 function - fastest node comparison
From: "Andrew Welch" <ajwelch@xxxxxxxxxxxxxxx>
Date: Thu, 10 Mar 2005 15:44:09 -0000
> You could experiment to see if reversing the conditions:
>
> $ranges/range[@to &gt;=$char][@from &lt;= $char]
>
> is any faster: this will only do one test on the ranges that
> are too low, rather than two (assuming that Saxon searches in
> forwards order, which it does). Still linear, but potentially
> up to twice the speed.

That's a very good tip!  It does speed up the execution time by around
100ms just by swapping the predicates around.  Out of interest, I've
implemented a binary search function which works out slower than the
sequential search, but this is probably due to the fact that there are
only 94 ranges to compare against...


<xsl:function name="f:isInRange" as="xs:boolean">
  <xsl:param name="char" as="xs:integer"/>
  <xsl:param name="low" as="xs:double"/>
  <xsl:param name="high" as="xs:double"/>
  <xsl:variable name="middle" select="number(floor(($high - $low) div
2))" as="xs:double"/>

  <xsl:variable name="currentNode" select="$ranges/range[middle]"/>

  <xsl:sequence select="if ($currentNode[@from &lt;= $char][@to &gt;=
$char])
                          then true()
                        else if ($high > $low) then
                          if ($char > $currentNode/@from) then
                            f:isInRange($char, $middle, $high)
                          else
                            f:isInRange($char, $low, $middle)
                        else false()"/>
</xsl:function>


I will use the linear search technique with the @to predicate test first
as Mike suggested as that's fastest, but comments welcome on the
function...

Interestingly, using 'cast as' on $middle to narrow it to an integer
causes the execution time to increase by 250ms, so I've left them all as
doubles (the positional predicate in $currentNode doesn't appear to mind
using a double).

cheers
andrew

Current Thread