[xsl] Re: Recursion Was: Re: 2 Questions: (1) about looping...

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

Joerg Pietschmann wrote:

> Dimitre Novatchev <dnovatchev@xxxxxxxxx> wrote:
> > You can organise a loop in XSLT using either:
> > 
> >   1. Simple recursion, where a template processes one member of a list and then
> > calls itself recursively to process the rest -- see for example:
> [snip] 
> > From the above three, the first works efficiently only on relatively short
lists,
> > getting an exponential-time behaviour very soon when the length of the input
list
> > increases. It also crashes existing XSLT processors (with the exception when
> > "tail-recursion" and XSLT processors optimised for tail-recursion are used). The
> > maximum call-stack depth is N - 1.
> > 
> 
> 
> I have to comment on this.
> The following code will not crash Saxon even if you start it with i=1000000
> and it wont slow down exponentially:
>   <xsl:template name="foo">
>     <xsl:param name="i"/>
>     <xsl:if test="$i > 0">
>       <xsl:text>*</xsl:text>
>       <xsl:call-template name="foo">
>         <xsl:with-param name="i" select="$i - 1"/>
>       </xsl:call-template>
>     </xsl:if>
>  </xsl:template>
> Some not quite representative execution times as measured by saxon -t
> (includes some overhead):
>       i  time (ms)
>      10    161
>     100    170
>    1000    290
>   10000    441
>  100000   5358
> 1000000  54579
>
> As you see it's somewhat superlinear asymptotically but hardly worth
> arguing about it.
[snip]
> 
> Conclusion: properly implemented text-book recursion works, even on
> large input values/long lists, if the processor is good enough.
> Divide-and-conquer/binary split techniques may have an adavantage
> nevertheless due to limited recursion depth, especially if potentially
> large string buffers are involved. However, the larger overhead of
> divide-and-conquer techniques is always a disadvantage for small
> problem sizes.

Hi Joerg,

The above example very well illustrates your conclusion.
However, it is not safe to arrive to a general conclusion based on a single example.

There's another example of a tail recursive template -- the one for reversing a
string that Jeni Tennison published recently. She also took the timings and here's
what she had to say:
http://sources.redhat.com/ml/xsl-list/2001-08/msg00257.html

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

[long code snipped]

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."

So if any conclusion is possible, it would be that there are examples of
tail-recursive algorithms that are significantly outperformed by divide and conquer
algorithms, even for moderate length input. There may be cases, in which specific
tail-recursion algorithms perform better, but the characteristics of these remain to
be well studied and described (e.g. having just a single short (numeric) parameter).

This is very useful information for anyone, who is involved in building real world
industrial strength applications.

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