Re: [xsl] Re: Re: reverse() template (Was: RE: XSL output method="text" and indent preservation)

[Jeni Tennison <mail@xxxxxxxxxxxxxxxx>]

Hi Francis,

>> I compared the speed of the two kinds of transformations on an
>> 350MHz 64MB RAM Pentium, doubling the string length from 100 to
>> 3200.
>> 
> So the least-recursion algorithm is way faster for large inputs -
> worth remembering in a functional programming environment.

It's also interesting to compare the templates with a tail-recursive
approach, such as:

<xsl:template name="reverse3">
   <xsl:param name="theString" />
   <xsl:param name="reversedString" />
   <xsl:choose>
      <xsl:when test="$theString">
         <xsl:call-template name="reverse3">
            <xsl:with-param name="theString"
                            select="substring($theString, 2)" />
            <xsl:with-param name="reversedString"
                            select="concat(substring($theString, 1, 1),
                                           $reversedString)" />
         </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
         <xsl:value-of select="$reversedString" />
      </xsl:otherwise>
   </xsl:choose>
</xsl:template>

I compared times from the three templates on a 800MHz 128Mb RAM
Pentium, running each test 10 times, averaging the times reported by
MSXML run from the command line, and rounding to the nearest
millisecond. Here are the results:

Length        Simple        Least Recursive         Tail Recursive
------------------------------------------------------------------
 100              22                    36                       5
 200              41                    61                      11
 400              95                   124                      24
 800             241                   249                      77
1600             650                   485                     220
3200            3465                   975                    1369

The tail recursive template is always substantially faster than the
simple algorithm, but it suffers from the same problem in the end -
the time taken increases exponentially rather than linearly based on
the length of the string, so for really long strings the least
recursive algorithm works best. I haven't taken detailed timings, but
there's a similar pattern in Saxon (although Saxon bugs out with the
simple algorithm and long strings, I guess a stack overflow). A
processor that doesn't optimise tail recursion would probably have
similar performance from both the simple and tail-recursive templates.

Cheers,

Jeni

---
Jeni Tennison
http://www.jenitennison.com/


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