[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

[xsl] Re: Recursion


Subject: [xsl] Re: Recursion
From: Joerg Pietschmann <joerg.pietschmann@xxxxxx>
Date: Wed, 29 Aug 2001 13:50:20 +0200

Dimitre Novatchev <dnovatchev@xxxxxxxxx> wrote:
> The above example very well illustrates your conclusion.
> However, it is not safe to arrive to a general conclusion based on a single example.

I should have phrased the conclusion more carefully. You have to
observe the difference between tail recursion optimization and the
complexity of the algorithm formulated in the code.

Tail recursion optimization is a technique to avoid allocating
stack frames for recursive procedure (template) invocation by
reusing or overwriting the space already allocated for parameters
and local variables of the actual running instance of the procedure
(template). The compiler (XSLT processor) usually does a lifetime
analysis in order to detect whether parameter values or local
variables has to be kept alive across the recursive invocation.
If they are all dead, their space can be overwritten and a new
allocation of space can be avoided, thereby turning the recursive
formulation of the algorithm effectively into some sort of loop
formulation.

BTW: XSLT processors have a much easier job doing flow and lifetime
analysis because variables cannot be altered, so that this usually
hard and time consuming job can be done on the fly (a good argument
against the use of xsl:script and the various zzz:assign elements).

Note that the primary reason for tail recursion optimization
is avoiding stack overflow, performance improvements are a
secondary effect (though this usually happens due to avoided
copy operations and perhaps improved memory utilization and
reduced swapping).

The other issue is algorithm complexity. Lets look at the
code from the quoted message:
  <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>
The template is invoked n times for an input string of length n.
However, in each invocation the $reversedString is set to the
result of a concatenation. This is likely to cause a copy of the
string, especially as a new character is concatenated to the
front of the old value (if it would be appended, a very clever
optimizer could try to extend the buffer holding the string).
With this assuption the runtime complexity of the i-th invocation
is O(i), as $resultString has the length O(i). The total
complexity is sum(O(i),0,n)=O(n^2), or quadratic (not
exponential). The numbers quoted for the run time show that the
algorithm is actually a bit worse.

Here is another shot at the same problem which runs a little bit
faster:
  <xsl:template name="reverse4">
    <xsl:param name="theString" />
    <xsl:param name="len" select="string-length($theString) - 1"/>
    <xsl:if test="$len &gt; 0">
      <xsl:value-of select="substring($theString,$len,1)"/>
      <xsl:call-template name="reverse4">
        <xsl:with-param name="theString" select="$theString" />
        <xsl:with-param name="len" select="$len - 1" />
      </xsl:call-template>
    </xsl:if>
  </xsl:template>
Any explicit copying is avoided, however, the characters are probably
written into a buffer which grows in chunks of equal size, each
growing results in a copy and therefore the complexity is still
quadratic. Rough measurements (using saxon 6.4.3) indicate that this
is actually so. A processor which uses an exponential buffer growing
strategy would show a better performance for longer strings. (The
stratey is: if the buffer is full, double the size. This is based on
Zipf's law about the distribution of problem sizes.)

The divide-and-conquer algorithm you gave in
  http://sources.redhat.com/ml/xsl-list/2001-08/msg00243.html
has a better complexity. It can be derived as follows: in the first
invocation the results of the second stage invocations are concatenated,
resulting in a run time complexity of n in addition of the time needed
by the second stage invocations. In the second stage there are similarly
copy operations of the results of the third stage invocations which
are half as long, but there are two of them, resulting again in n, and
so on. Because there are log(n) stages, the total complexity is
O(n*log(n)). The empirical results show that this is not far off.
It should be obvious that for any n greater than, say, 3, O(n*log(n)) is
better, usually *much* better, than O(n*n). For the problem sizes
mentioned (n>99) any overhead costs resulting in a larger front factor
are easily covered.

It should be noted that string reversion can be solved in O(n) time and
space: allocate a buffer of the length of the string and copy the string
in reverse. Unfortunately, there is no explicit buffer allocation
in XSLT.

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

I don't think there is an easy rule when to use what, as a lot of
complexity can be hidden in short expressions and quite a bit
depends on the inner mechanics implemented in the processor and
on its optimizing capabilities.
If a transformation is slow, try to get a feeling how it depends on
the input, identify bottlenecks through profiling and then do a careful
analysis of the critical algorithms, backed by empirical data.
Quick "intuitive" guesses require a *lot* of experience and even then
are almost always wrong. I could tell stories...

It should be safe to say that simple recursion is easier to understand
and can be safely used for such tasks like traversing a node set, for
example doing vector calculations like sum(a[i]*b[i]).

Divide-and-conquer algorithms are likely to perform better for string
processing, like string reversal, due to string copies. Generic sorting
is another application, which should be well known.
I'd like to point out that it is somewhat difficult to apply divide-
and-conquer to the general substring replacement problem, which is
of much more practical relevance than string reversal as questions
on this list show.

Another rule of thumb is that results should be written to the result
tree a soon as possible instead of collecting stuff into variables and
copy it later.

The complexity of other algorithms, for example for $foo/bar[not(preceding::bar=.)]
has already extensively discussed on this list (and why its better to use key()).

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

Regards
J.Pietschmann

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



Current Thread
Keywords