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

Subject: Re: [xsl] Re: Re: reverse() template (Was: RE: XSL output method="text" and indent preservation)
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Sun, 5 Aug 2001 11:43:13 -0700 (PDT)
--- Jeni Tennison <mail@xxxxxxxxxxxxxxxx> wrote:
> 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/
> 


I added Jeni's algorithm and one more (6400 long) string, and timed all three
templates with both MSXML3 and Saxon. The two tables below summarize the results.

As it can be seen, these results are similar to my previous results and to Jeni's.

I cannot explain the non-linear performance of the tail-recursive algorithm under
Saxon, because as we know Saxon optimises tail-recursion implementing it using
iteration.

Based on these empirical results, then the following will be the "optimal"
algorithm:


<xsl:template name="reverse">
    <xsl:param name="theString"/>

    <xsl:choose>
       <xsl:when test="string-length($theString) > 1600">
          <xsl:call-template name="lrReverse">
              <xsl:with-param name="theString" select="$theString"/>
          </xsl:call-template>
       </xsl:when>
       <xsl:otherwise>
          <xsl:call-template name="trReverse">
              <xsl:with-param name="theString" select="$theString"/>
              <xsl:with-param name="reversedString" select="''"/>
          </xsl:call-template>
       </xsl:otherwise>
    </xsl:choose>
</xsl:template>

The tail-recursive and least-recursive templates will have to be modified, so that
they call not themselves, but the above "reverse" template, which actually acts as a
dispatcher:

<xsl:template name="lrReverse">
  <xsl:param name="theString"/>
  <xsl:variable name="thisLength" select="string-length($theString)"/>
	<xsl:choose>
		<xsl:when test="$thisLength = 1">
		    <xsl:value-of select="$theString"/>
		</xsl:when>
		<xsl:otherwise>
		    <xsl:variable name="length1" select="floor($thisLength div 2)"/>
		    <xsl:variable name="reverse1">
			<xsl:call-template name="reverse">
			    <xsl:with-param name="theString"
				select="substring($theString, 1, $length1)"/>
			</xsl:call-template>
		    </xsl:variable>
		    <xsl:variable name="reverse2">
			<xsl:call-template name="reverse">
			    <xsl:with-param name="theString"
				select="substring($theString, 
                                                  $length1+1, 
		                                  $thisLength - $length1
                                                  )"/>
			</xsl:call-template>
		    </xsl:variable>
		    <xsl:value-of select="concat($reverse2, $reverse1)"/>

		</xsl:otherwise>
	</xsl:choose>
</xsl:template>


<xsl:template name="trReverse">
   <xsl:param name="theString" />
   <xsl:param name="reversedString" />
   <xsl:choose>
      <xsl:when test="$theString">
         <xsl:call-template name="trReverse">
            <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>


Here are the timings tables:

MSXML3
------

Length        Simple        Least Recursive   Tail-Recursive
------------------------------------------------------------
 100              37                    58               9.5
 200              85                   117              24.7
 400             199                   235              63
 800             522                   469             197
1600            1460                   927             613
3200           35000                  1870            2198
6400          193703                  3760           16000


Saxon
------

Length        Simple        Least Recursive   Tail-Recursive
------------------------------------------------------------
 100             360                   550             240
 200             450                   641             280
 400             705                   711             375
 800            1392                   951             641
1600     Out of memory  Error         1512            1655
3200     Out of memory  Error         2714            5570
6400     Out of memory  Error         5250           21000


Cheers,

Dimitre Novatchev.


__________________________________________________
Do You Yahoo!?
Make international calls for as low as $.04/minute with Yahoo! Messenger
http://phonecard.yahoo.com/

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


Current Thread