RE: [xsl] What is the Maximum number of recurssions

Subject: RE: [xsl] What is the Maximum number of recurssions
From: Scott Trenda <Scott.Trenda@xxxxxxxx>
Date: Fri, 02 Mar 2012 08:36:18 -0500
I encountered this recently, when I had to retool a str:rtrim template to use bisection because the previous step-through-the-whitespace method was bombing out on large data sets.

Out of curiosity, has anyone thought about a bisection approach for str:replace (XSLT 1.0)? I was able to use bisection for my str:rtrim template, but only because the character I was looking for (' ') was only one character long. Is it possible to use bisection when searching for a dynamic-length string in the subject string? The basic problem theoretically is that you don't want to bisect the subject string at a point that's in the middle of an occurrence of the search string.

I suppose it's possible if you tweak the basic bisection algorithm - one idea I had was to check for contains(substring($subject, string-length($subject) / 2 - string-length($search), string-length($subject) / 2 - string-length($search))) before splitting the string at string-length($subject) / 2; my assumption is that you'll never split an occurrence of the search string if you check a sufficiently wide string surrounding the search area. I also suppose that you'd be able to optimize the conditions for where you'd stop searching, based on the length of the search string.

Basically, it sounds like there are some potential improvements to be made, but I wouldn't want to do them myself if someone else has already done them. :) I'm also guessing that the fundamental pattern in str:replace is one that would be optimized for tail recursion pretty quickly, so I don't know if there's even any potential gain to be had here.

Any thoughts?

~ Scott

-----Original Message-----
From: Dimitre Novatchev [mailto:dnovatchev@xxxxxxxxx] 
Sent: Thursday, March 01, 2012 3:23 PM
To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
Subject: Re: [xsl] What is the Maximum number of recurssions

On Thu, Mar 1, 2012 at 12:36 PM, Karl Stubsjoen <kstubs@xxxxxxxxx> wrote:
> I'm just curious, what is the maximum number of times a template can 
> recurse?

I guess you men the number of nested recursive calls (nestedness).
There is no fixed maximum and in some cases a correctly written template/function can have nestedness measured in the millions.

Such are the cases with tail-recursive functions/templates -- and this requires that the XSLT processor can recognize and optimize tail recursion.

For example, this transformation run with Saxon 6.5.4 successfully prints all numbers from 1 to one million:

<xsl:stylesheet version="1.0"
 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 <xsl:template match="/">
  <xsl:call-template name="printToN"/>

 <xsl:template name="printToN">
  <xsl:param name="pUpTo" select="1000000"/>
  <xsl:param name="pDoneWith" select="0"/>

  <xsl:if test="$pUpTo > $pDoneWith">
   <xsl:value-of select="$pDoneWith+1"/>

   <xsl:call-template name="printToN">
    <xsl:with-param name="pUpTo" select="$pUpTo"/>
    <xsl:with-param name="pDoneWith" select="$pDoneWith+1"/>

However, other XSLT processors (AltovaXML) produce this error: "XSLT instruction stack overflow"

A DVC (Divide and Conquer) style recursion is also a practical solution and processing a sequence of N items requires a maximum nestedness of only log(N). This recursive style is remarkable in that it doesn't require (as required in the case of tail recursion) any special abilities from the XSLT processor and works correctly with any XSLT processor. Thus the maximum callstack depth when processing a sequence of one million items with DVC-style recursion, is only 19.

> I would imagine it would be different from engine to engine.
>  Is there any other engine intelligence at play here, for example the 
> engine has decided that you've written and endless looping recursion, 
> instead of one that knows you'll eventually reach the end of your 
> source xml?

This is generally impossible to do, because whether or not an algorithm finishes often depends on the specific data that is fed to it -- typical examples are many numerical methods that converge only if the data is limited in a specific interval or by any other condition.


> Thanks,
> Karl..
> --
> Karl Stubsjoen
> (602) 845-0006

Dimitre Novatchev
Truly great madness cannot be achieved without significant intelligence.
To invent, you need a good imagination and a pile of junk
Never fight an inanimate object
To avoid situations in which you might make mistakes may be the biggest mistake of all
Quality means doing it right when no one is looking.
You've achieved success in your field when you don't know whether what you're doing is work or play
Facts do not cease to exist because they are ignored.
I finally figured out the only reason to be alive is to enjoy it.

Current Thread