Table of Contents

How this solution came about Example 1: Total-sales Example 2: Reversing strings Example 3: Search&replace Interpretation of the results Conclusion

Two-stage recursive algorithms in XSLT

By Dimitre Novatchev and Slawomir Tyszko


Summary
This article presents several examples of two-stage recursive XSLT algorithms. In each of them the first stage is implemented as DVC (divide and conquer) recursive template, and the second stage as simple recursive template. The examples show that such a combination results in better performance than other solutions, including classic DVC-only algorithms

How this solution came about

XSLT is an offspring of DSSSL, which is based on the Scheme programming language, and, as such, belongs to the category of so-called declarative programming languages. As such it is quite different from a procedural language. One such outstanding difference is that variables can only be initialised and are immutable. xsl:param and xsl:variable elements have local scope and can only be "shadowed" in a "more local" scope, by another variable with the same name. Among other things, this makes it difficult to implement iterative computations, very common in procedural languages. In cases when such computations are necessary in an XSLT transformation, the only solution is to resort to recursion, by having a named template call itself recursively. With this solution, the intermediate result, instead of being accumulated in one place in memory, is, after each computation step, pushed from one place to another on the call-stack, corresponding to different instances of the an xsl:param at different levels of recursion. 

However, this method, in its simplest "handbook form", can have some essential and unpleasant limitations. When an XSLT processor is used, which does not handle tail recursion intelligently (does not implement tail recursion with iteration) it may crash when processing big xml source documents, due to the call-stack overflow. Processing time increases much steeper than in a linear way before the crash-point is reached with the size of the source xml document increasing.

There are several ways of addressing this problem. One way was presented in Dimitre Novatchev's snippet: Avoiding an XSLT Processor crash due to deep recursive processing. This method (known as the Piez method) makes it possible to replace recursion by a xsl:for-each loop, but it can be used only in the simplest case - in iterations, where there is no passing of data computed in a given step to the next steps.

Another solution was proposed in Slawomir Tyszko's snippet: Another way of avoiding XSLT processor crash. It does not relinquish recursion, but reduces its depth, by using two named recursive templates instead of just one. In this solution the input is partitioned into "chunks". The first template recursively computes partial results inside chunks, while the second template acts as "chunk manager", as it recursively calls the first template for processing successive chunks, and uses returned partial results to compute the final result. If, for instance, the input consists of 10 000 nodes, it may be partitioned into 100 chunks, each containing 100 nodes. In such a case, the recursion depth will be reduced from 10 000 to 200 (100+100).

Before this last snippet was published, Dimitre had been actively promoting DVC (divide and conquer) approach to deep-recursion problems in XSLT, mostly in his posts to the xsl-list forum. No wonder then, that he immediately responded to the Slawomir's snippet with: DVC Algorithms in XSLT, in which he had pointed out that, in this case, the classic DVC solution would be much better: simpler, faster, enabling much higher reduction of the recursion depth (to only 14 instead of 200).

But, after a more detailed examination, Slawomir was able to prove this was not always the case. While the DVC solution was unrivalled in case of computation of a single-number result (large sum of sales*price products examined in those two snippets), experimentation with another problem (search-and-replace on a very long string) had shown that, in that case, the "chunk algorithm", with adequately chosen chunk-size parameter, was several times faster (see: Re: DVC Algorithms in XSLT).

Theoretical considerations reveal that both DVC and the "chunk" solution have advantages, as well as limitations. DVC's main advantage is a very low recursion depth (to log₂N), which is also a substantial factor determining the speed of the algorithm, while its limitation stems from the inevitable overhead necessary to implement this method. This overhead affects mostly the bottom-level (most numerous) steps of recursion. With the "chunk" solution the picture is reversed: the recursion depth reduction is not so radical, but the overhead related to the last recursion steps is small, as those last steps are performed by the chunk-processing template, which is a simple, regular recursive template.

Next comes the following question: isn't it possible to somehow combine the strong points of those two solutions, so that this combination would exceed the performance of both solutions on almost any task? Such ideal solution would have lower depth of recursion than the chunk algorithm, and at the same time would have lower overhead, than the pure DVC solution. We now know that the replacement of the whole of the two-template chunk algorithm, by the classic DVC solution, was too radical a move; there are situations where the chunk algorithm is distinctly faster. But what if we took the chunk algorithm and replaced just the first recursive template (the chunk manager) with the DVC template, leaving the second, chunk-processing, template intact? In such a way we could get a two-stage algorithm; one stage performed by a classic DVC template, dividing the input into smaller and smaller segments until the remaining segments are small enough, and the second stage, performed by a simple recursive template, processing those small segments (chunks). As compared to the chunk algorithm, such an algorithm will still have much lower recursion depth. On the other hand, as compared to pure DVC solution, the overhead, related to DVC implementation, will be much reduced, since it will be completely eliminated for the large number of small DVC divisions, where the overhead is most expressed.

This solution is pursuing a practical goal to maximize the processing speed, with recursion depth kept well below a safe limit (e.g. 1000). As it turns out, this practical goal can be achieved. In fact, last August, in the xsl-list, Dimitre suggested a very similar solution, as the "optimal" algorithm for reversing strings (see: http://sources.redhat.com/ml/xsl-list/ 2001-08/msg00258.html).

In the rest of the article we investigate three examples of such two-stage algorithms, and compare them to their classic DVC equivalents.

Example 1: Total-sales

This is the example investigated in the above-mentioned snippets: Another way of avoiding XSLT processor crash and DVC Algorithms in XSLT. In fact, this example is based on an example given in chapter 8 (9 in the second edition) of the Michael Kay's XSLT Programmer's Reference to demonstrate the use of simple recursion (template named total-sales-value) for computing the sum of sales*price products for all book elements contained in the booklist element:

<booklist>
 <book>
   <title>Angela's Ashes</title>
   <author>Frank McCourt</author>
   <publisher>HarperCollins</publisher>
   <isbn>0 00 649840 X</isbn>
   <price>6.99</price>
   <sales>235</sales>
 </book>
 <book>
   <title>Sword of Honour</title>
   <author>Evelyn Waugh</author>
   <publisher>Penguin Books</publisher>
   <isbn>0 14 018967 X</isbn>
   <price>12.99</price>
   <sales>12</sales>
 </book> </booklist>

Let us use this task to compare the performance of the simple recursion, classic DVC recursion, and our new two-stage algorithm. Below is the recursive solution - implemented by the template sumSales1:

<xsl:stylesheet version="1.0" 
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="text"/>
  
  <xsl:template match="/">
    <xsl:call-template name="sumSales1">
      <xsl:with-param name="pNodes" select="/*/book"/>
    </xsl:call-template>
  </xsl:template>

  <xsl:template name="sumSales1">
   <xsl:param name="pNodes"  select="/.."/>
   <xsl:param name="result"  select="0"/>
   
   <xsl:choose>
     <xsl:when test="$pNodes">
       <xsl:call-template name="sumSales1">
         <xsl:with-param name="pNodes"
                         select="$pNodes[position()!=1]"/>
         <xsl:with-param name="result" 
             select="$result
                    + $pNodes[1]/sales*$pNodes[1]/price"/>
       </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:value-of select="$result"/>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
</xsl:stylesheet>

And here is the  DVC solution:

<xsl:stylesheet version="1.0" 
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="text" />

  <xsl:template match="/">
    <xsl:call-template name="sumSales">
      <xsl:with-param name="pNodes" 
                      select="/*/book" />
    </xsl:call-template>
  </xsl:template>

  <xsl:template name="sumSales">
    <xsl:param name="pNodes" select="/.." />
    <xsl:param name="result" select="0" />

    <xsl:variable name="vcntNodes" 
                  select="count($pNodes)" />

    <xsl:choose>
      <xsl:when test="$vcntNodes = 1">
        <xsl:value-of select=
          "$result + $pNodes/sales * $pNodes/price" />
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="vcntHalf" 
              select="floor($vcntNodes div 2)" />

        <xsl:variable name="vValue1">
          <xsl:call-template name="sumSales">
            <xsl:with-param name="pNodes" select=
              "$pNodes[position() &lt;= $vcntHalf]" />
            <xsl:with-param name="result" 
                            select="$result" />
          </xsl:call-template>
        </xsl:variable>

        <xsl:call-template name="sumSales">
          <xsl:with-param name="pNodes" select=
                "$pNodes[position()&gt; $vcntHalf]" />
          <xsl:with-param name="result" 
                          select="$vValue1" />
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
</xsl:stylesheet>

Finally, the two-stage-algorithm-based solution is a combination of the previous two:

<xsl:stylesheet version="1.0" 
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="text" />

  <xsl:template match="/">
    <xsl:call-template name="sumSales">
      <xsl:with-param name="pNodes" 
                      select="/*/book" />
      <xsl:with-param name="threshold" 
                      select="10" />
    </xsl:call-template>
  </xsl:template>

<!-- DVC template:    -->
  <xsl:template name="sumSales">
    <xsl:param name="pNodes" select="/.." />
    <xsl:param name="threshold" select="10" />
    <xsl:param name="result" select="0" />

    <xsl:variable name="vcntNodes" 
                  select="count($pNodes)" />

    <xsl:choose>
      <xsl:when test="$vcntNodes &lt;= $threshold">
        <xsl:call-template name="sumSales1">
          <xsl:with-param name="pNodes" 
                          select="$pNodes" />
          <xsl:with-param name="result" 
                          select="$result" />
        </xsl:call-template>
      </xsl:when>

      <xsl:otherwise>
        <xsl:variable name="vcntHalf" 
              select="floor($vcntNodes div 2)" />

        <xsl:variable name="vValue1">
          <xsl:call-template name="sumSales">
            <xsl:with-param name="pNodes" select=
                "$pNodes[position()&lt;= $vcntHalf]" />
            <xsl:with-param name="threshold" 
                            select="$threshold" />
            <xsl:with-param name="result" 
                            select="$result" />
          </xsl:call-template>
        </xsl:variable>

        <xsl:call-template name="sumSales">
          <xsl:with-param name="pNodes" select=
              "$pNodes[position() &gt; $vcntHalf]" />
          <xsl:with-param name="threshold" 
                          select="$threshold" />
          <xsl:with-param name="result" 
                          select="$vValue1" />
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

<!-- simple recursive template:   -->
  <xsl:template name="sumSales1">
    <xsl:param name="pNodes" select="/.." />
    <xsl:param name="result" select="0" />

    <xsl:choose>
      <xsl:when test="$pNodes">
        <xsl:call-template name="sumSales1">
          <xsl:with-param name="pNodes" 
               select="$pNodes[position()!=1]" />
          <xsl:with-param name="result" select=
           "$result+$pNodes[1]/sales * $pNodes[1]/price"/>
        </xsl:call-template>
      </xsl:when>
      <xsl:otherwise>
        <xsl:value-of select="$result" />
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
</xsl:stylesheet>

The sumSales template first compares the number of nodes, in the input node-set, with the value of the threshold parameter. If it exceeds the threshold, the template behaves like a classic DVC template, i.e. divides the input node-set into two almost equal parts and calls itself twice (one call with each part). Otherwise the number of nodes is below the threshold, so the simple recursive template sumSales1 is called to carry out the final computations.

To compare the performance of those three stylesheets we used 5 input files: booklist01.xml, booklist02.xml, booklist04.xml, booklist08.xml and booklist16.xml, generated by appropriately replicating Michael Kay's original example. They contained correspondingly: 1000, 2000, 4000, 8000 and 16000 book elements. They are all included in the attached source.zip file. The tests were carried out with the Xalan C++ XSLT processor running on the 500 MHZ Pentium, 256 MB RAM PC. We have compared the speed of all three above algorithms, the last one using 5 different threshold values.

In the table below are the results in milliseconds, each obtained by running the corresponding stylesheet 3 times and then taking the average of the Xalan-reported transformation times:

As can be seen, the simple recursive template, in which the recursion depth equals the number of nodes in the input node-set, could not cope with the files containing 8000 and 16000 book elements, and with smaller files the transformation times were many times higher than with the more sophisticated algorithms. In fact, with simple recursion, when the recursion depth doubles, the transformation time increases about 5 times.

The classic DVC template was 11 times faster with the 1000-book-elements file, and 63 times faster with the 4000-elements file, as compared to the simple recursive template. And it can be seen that, when using DVC, the processing time grows approximately linearly with the size of the input, i.e. much slower than with the simple recursion.

The two-stage algorithm, with the threshold parameter set to 1, is functionally equivalent to the classic DVC solution. It is slightly slower, though, because in this specific case, in addition to splitting the input node-set with the DVC template sumSales, which proceeds in exactly the same way in both cases, the two-stage algorithm requires also one call to the simple recursive template sumSales1 for each book element. However, it is enough to set the threshold to 2 to get this algorithm overtake pure DVC. The transformation time decreases until the threshold reaches 10-20, due to DVC overhead reduction. After that it starts increasing again because of the growing size of the segments processed by the second-stage template.

The two-stage algorithm, with optimally set threshold (between 10 and 20), is from 20 to 30% faster than the classic DVC algorithm. This is not very impressive, although in some real-life applications such improvement may be significant. The gain is rather modest because, in this example, the overhead related to the DVC implementation, as compared to the main processing, is relatively small, so its reduction, by shifting at some point to simple recursion, is also not very significant. 

Example 2: Reversing strings

The second example is, in fact, an implementation of the idea of the optimal string-reversal algorithm suggested by Dimitre in http://sources.redhat.com/ml/xsl-list/ 2001-08/msg00258.html.

Here is a stylesheet , which implements a classic DVC template (reverse2). It differs slightly from the template originally used by Dimitre, the modifications were made in order to reduce the inherent DVC overhead as much as possible:

<xsl:stylesheet version="1.0" 
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="text" />

  <xsl:template match="/">
    <xsl:call-template name="reverse2">
      <xsl:with-param name="theString" 
                      select="/*/text()" />
    </xsl:call-template>
  </xsl:template>

  <xsl:template name="reverse2">
    <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:call-template name="reverse2">
          <xsl:with-param name="theString"
               select="substring($theString,
                                 $length1+1, 
                                 $thisLength - $length1
                                 )" />
        </xsl:call-template>

        <xsl:call-template name="reverse2">
          <xsl:with-param name="theString"
          select="substring($theString, 1, $length1)" />
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
</xsl:stylesheet>

And here is the two-stage version of the string-reversal stylesheet, built by combining the above code with a simple recursive template (reverse):  

<xsl:stylesheet version="1.0" 
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="text" />

  <xsl:template match="/">
    <xsl:call-template name="reverse2">
      <xsl:with-param name="theString" 
                      select="/*/text()" />
      <xsl:with-param name="threshold" 
                      select="75" />
    </xsl:call-template>
  </xsl:template>

<!--  DVC template:    -->
  <xsl:template name="reverse2">
    <xsl:param name="theString" />
    <xsl:param name="threshold" 
               select="50" />

    <xsl:variable name="thisLength" 
             select="string-length($theString)"/>

    <xsl:choose>
      <xsl:when test="$thisLength &lt;= $threshold">
        <xsl:call-template name="reverse">
          <xsl:with-param name="theString" 
                          select="$theString" />
        </xsl:call-template>
      </xsl:when>

      <xsl:otherwise>
        <xsl:variable name="length1" 
                 select="floor($thisLength div 2)"/>

        <xsl:call-template name="reverse2">
          <xsl:with-param name="theString"
           select="substring($theString,
                             $length1+1, 
                             $thisLength - $length1
                             )" />
          <xsl:with-param name="threshold" 
                          select="$threshold" />
        </xsl:call-template>

        <xsl:call-template name="reverse2">
          <xsl:with-param name="theString"
            select="substring($theString, 1, $length1)"/>
          <xsl:with-param name="threshold" 
                          select="$threshold" />
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

<!-- simple recursive template:   -->
  <xsl:template name="reverse">
    <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:value-of 
          select="substring($theString,$thisLength,1)"/>

        <xsl:call-template name="reverse">
          <xsl:with-param name="theString"
          select="substring($theString, 
                            1, 
                            $thisLength -1)" />
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
</xsl:stylesheet>

The DVC template (reverse2) first compares the length of the input string with the threshold parameter. If it exceeds the threshold, the template behaves like a classic DVC template, i.e. divides the input string into two equal (almost) segments, and calls itself twice (one call for each segment). Otherwise, it calls the simple recursive template reverse.

To compare the performance of the two stylesheets we used 4 input files: reverse01.xml, reverse02.xml, reverse04.xml and reverse08.xml. Each of them contained one text node with correspondingly: 100 000, 200 000, 400 000 and 800 000 characters. They are all included in the attached source.zip file. Like before, the tests were carried out with the Xalan C++ XSLT processor running on a 500 MHZ Pentium, 256 MB RAM PC. We have compared the speed of the two  algorithms, the last one using 5 different threshold values. The stylesheet based on just the simple recursive template could not have been included in the comparison, since, even with the smallest input file, it would require a recursion depth of 100 000, far exceeding Xalan capabilities.

Below are the results in milliseconds, each obtained by running the corresponding stylesheet 3 times, then taking the average of the Xalan-reported transformation times:

The two-stage algorithm, with the threshold parameter set to 1, is functionally equivalent to the classic DVC solution. It is slower, though, because in this specific case, in addition to splitting the input string with the DVC template, which proceeds in exactly the same way in both cases, the two-stage algorithm requires also one call to the simple recursive template lrReplace3 for each character of the string. However, it is enough to set the threshold to 5 to get this algorithm overtake pure DVC. The transformation time decreases until the threshold reaches approximately 75 characters, due to DVC overhead reduction. After that, its further reduction becomes less and less significant, whereas the growing size of the segments processed by the second-stage template gains more significance, hence the processing time begins to grow.

The two-stage algorithm, with optimally set threshold (about 75), is about 37% faster than classic DVC solution. This is a more tangible difference than in the previous example, although still not very impressive. Nevertheless, it seems sufficiently promising to encourage us to investigate the last example.

Example 3: Search&replace

This last example deals with search and replace operations performed on very long strings. The straightforward solution is, of course, a simple recursive template (see, for instance, How to do a search and replace in XSLT or XSLT string Replace function). With such a solution the recursion depth is equal to the number of substrings to be replaced, hence, as we already know, it can not be used to deal with long input strings containing many thousands of replacements targets.

The next option is the classic DVC solution, which requires splitting the input string into two possibly equal parts and applying the recursive template to both parts, and so on until the parts become very short (e.g. until each of them can not contain more than one occurrence of the replacement target), and only then making actual replacements. However, in this case, applying DVC is not as simple as in the previous examples because, when splitting the input string, we may also split a target. Such a target will not be detected in the right part of the input string, or in its left part, so it will not be replaced.

One way of dealing with this problem (as used in this algorithm) is to shift a small number of the last characters that may belong to a target, from the right part to the left part of the input string. After such a move the target will not be detected in the right part, but it should be detected in the left part, as now the left part contains the complete instance of the target.

In order to implement this idea, the recursive template should not return the whole string passed to it (after accomplishing all the replacements), but the returned string should be truncated by an adequate number of characters (leaving out the characters that could belong to a split target). In addition, the template should also produce a number specifying how many characters it had left out. This number (a displacement) is necessary to precisely determine which part of the input string should be passed to the next call of the template, so as to include the characters left out by the previous call. One consequence of this approach is that the recursive DVC template, applied to the whole input string, will not process it completely, but some endmost characters may be left out. Thus, the stylesheet, after calling the template, should extract the displacement, and copy the indicated number of the endmost characters from the input string, appending them to the output.

Determining the displacement is very simple: let us denote the displacement by u (from uncertain), and by s the remainder of the input string composed of the characters following the last occurrence of the target. Then when s is empty, u = 0; when string-length(s) < string-length( target), u = string-length(s); when string-length(s) >= string-length( target), u =  string-length(target) - 1. 

The DVC template goes on splitting the input string into two approximately equal segments, until the length of the resulting segments becomes less than 2*string-length(target), which means that such a terminal segment can contain at most one occurrence of the target. If this is the case, instead of further splitting, the possible replacement takes place, and the template returns the truncated string along with the displacement.

The last difficulty relates to the fact that our DVC template must return both the converted string and a number (a displacement). To make it possible we have had to resort to the vendor-supplied node-set extension function, so unlike the previous examples, this algorithm requires an XSLT processor with a node-set extension implemented. Thus, the output of the DVC template is stored in a variable, as a result tree fragment: the converted string - as a text node, and the displacement - as contents of the element u. After converting the result tree fragment to a node-set (hence the need of the extension function) both items can be easily extracted.

Here is the pure DVC solution:

<xsl:stylesheet version="1.0" 
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:msxsl="urn:schemas-microsoft-com:xslt">
  
  <xsl:output method="text" 
              encoding="iso-8859-1" />

  <xsl:template match="/">
    <xsl:variable name="Result">
      <xsl:call-template name="lrReplace">
        <xsl:with-param name="theString" 
                        select="/*/text()"/>
        <xsl:with-param name="target" 
                        select="'AAA'" />
        <xsl:with-param name="replacement" 
                        select="'ZZZ'" />
      </xsl:call-template>
    </xsl:variable>

    <xsl:value-of select="$Result" />
  </xsl:template>

  <xsl:template name="lrReplace">
    <xsl:param name="theString"/>
    <xsl:param name="target"/>
    <xsl:param name="replacement"/>

    <xsl:variable name="lStr" 
         select="string-length($theString)"/>

    <xsl:variable name="resRTF">
      <xsl:call-template name="lrReplace2">
        <xsl:with-param name="theString" 
                        select="$theString"/>
        <xsl:with-param name="target" 
                        select="$target"/>
        <xsl:with-param name="replacement" 
                        select="$replacement"/>
      </xsl:call-template>
    </xsl:variable>

    <xsl:variable name="resNode-set" 
         select="msxsl:node-set($resRTF)"/>

    <xsl:value-of select="$resNode-set/text()"/>

    <xsl:value-of 
     select="substring($theString,
                       $lStr -$resNode-set/u+1
                       )" />
  </xsl:template>

  <xsl:template name="lrReplace2">
    <xsl:param name="theString"/>
    <xsl:param name="target"/>
    <xsl:param name="replacement" select="''" />

    <xsl:variable name="lStr" 
         select="string-length($theString)" />

    <xsl:variable name="lTarget" 
             select="string-length($target)" />

    <xsl:choose>
      <xsl:when test="$lStr &lt; $lTarget + $lTarget">
        <xsl:choose>
          <xsl:when 
             test="contains($theString,$target)">
            <xsl:value-of  select=
              "substring-before($theString,$target)" />
            <xsl:value-of select="$replacement" />
            <u>
              <xsl:value-of select="string-length
                (substring-after($theString,$target))" />
            </u>
          </xsl:when>

          <xsl:otherwise>
            <xsl:choose>
              <xsl:when test="$lStr &gt;= $lTarget">
                <xsl:value-of
                select="substring($theString,
                                  1,
                                  $lStr - $lTarget + 1)"/>
                <u>
                  <xsl:value-of select="$lTarget - 1" />
                </u>
              </xsl:when>

              <xsl:otherwise>
                <u>
                  <xsl:value-of select="$lStr" />
                </u>
              </xsl:otherwise>
            </xsl:choose>
          </xsl:otherwise>
        </xsl:choose>
      </xsl:when>

<!-- Now the general case - theString is not less 
           than twice the replacement -->
      <xsl:otherwise>
        <xsl:variable name="halfLength" 
                      select="floor($lStr div 2)"/>

        <xsl:variable name="processedHalf">
          <xsl:call-template name="lrReplace2">
            <xsl:with-param name="theString"
            select="substring($theString, 
                              1, 
                              $halfLength)"/>
            <xsl:with-param name="target" 
                            select="$target"/>
            <xsl:with-param name="replacement" 
                            select="$replacement"/>
          </xsl:call-template>
        </xsl:variable>

        <xsl:variable name="nodePrHalf"
        select="msxsl:node-set($processedHalf)"/>

        <xsl:value-of select="$nodePrHalf/text()"/>

        <xsl:call-template name="lrReplace2">
          <xsl:with-param name="theString"
          select="substring($theString,
                            $halfLength 
                              - $nodePrHalf/u + 1)" />
          <xsl:with-param name="target" 
                          select="$target" />
          <xsl:with-param name="replacement" 
                          select="$replacement" />
        </xsl:call-template>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>
</xsl:stylesheet>

The highest-level (in the call-hierarchy) named template in the above stylesheet is lrReplace, but its role consists only in calling the DVC template lrReplace2 once, and storing its output in the variable resRTF as a result tree fragment. This is necessary because the DVC template may return the string truncated by several characters. The template lrReplace first converts the resRTF variable to a node-set (contained in the variable resNode-set), then extracts from that node-set, and outputs, the text node containing the truncated string, and finally outputs the missing part of the string by copying it from the input string, its length determined by the displacement extracted from resNode-set as the contents of the element u.

The DVC template lrReplace2 consists of two parts, the first part dealing with the input strings shorter than the concatenation of two targets. That part is a direct implementation of the rules (given above), specifying how to compute the displacement. The second part, dealing with longer strings, first calls itself recursively passing as parameter theString the first half of the input string, and assigns the resulting result tree fragment to the variable processedHalf. Then it converts that result tree fragment to a node-set which becomes the contents of the variable nodePrHalf. After that, it outputs the text node extracted from the node-set, and finally, it calls itself the second time, this time passing, in theString the second half of the input string preceded by characters left out by the first call. 

As in the previous examples, we compared the performance of this pure DVC solution with the two-stage algorithm built by combining the DVC template with the simple recursive one. Here is the XSLT code of the two-stage algorithm:

<xsl:stylesheet version="1.0" 
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:msxsl="urn:schemas-microsoft-com:xslt">
 <xsl:output method="text" 
             encoding="iso-8859-1" />

 <xsl:template match="/">
   <xsl:variable name="Result">
     <xsl:call-template name="lrReplace">
       <xsl:with-param name="theString" 
                       select="/*/text()"/>
       <xsl:with-param name="target" 
                       select="'AAA'"/>
       <xsl:with-param name="replacement" 
                       select="'ZZZ'"/>
       <xsl:with-param name="threshold" 
                       select="2000"/>
     </xsl:call-template>
   </xsl:variable>

  <xsl:value-of select="$Result" />
</xsl:template>
 
<xsl:template name="lrReplace">
  <xsl:param name="theString"/>
  <xsl:param name="target"/>
  <xsl:param name="replacement"/>
  <xsl:param name="threshold" 
             select="150"/>
  <xsl:variable name="lStr" 
       select="string-length($theString)"/>

  <xsl:variable name="resRTF">
    <xsl:call-template name="lrReplace2">
      <xsl:with-param name="theString" 
                      select="$theString"/>
      <xsl:with-param name="target"
                      select="$target"/>
      <xsl:with-param name="replacement" 
                      select="$replacement"/>
      <xsl:with-param name="threshold" 
                      select="$threshold"/>
    </xsl:call-template>
  </xsl:variable>

  <xsl:variable name="resNode-set" 
       select="msxsl:node-set($resRTF)"/>

  <xsl:value-of select="$resNode-set/text()"/>

  <xsl:value-of 
    select="substring($theString,
                      $lStr - $resNode-set/u+1)"/>
</xsl:template>

<!-- DVC template:        -->
<xsl:template name="lrReplace2">
  <xsl:param name="theString"/>
  <xsl:param name="target"/>
  <xsl:param name="replacement"/>
  <xsl:param name="threshold" select="150"/>

  <xsl:variable name="lStr" 
       select="string-length($theString)"/>

  <xsl:variable name="lTarget" 
       select="string-length($target)"/>

  <xsl:choose>
    <xsl:when test="$lStr &lt;= $threshold">
      <xsl:call-template name="lrReplace3">
        <xsl:with-param name="theString" 
                        select="$theString"/>
        <xsl:with-param name="target" 
                        select="$target"/>
        <xsl:with-param name="replacement" 
                        select="$replacement"/>
      </xsl:call-template>
    </xsl:when>

    <xsl:otherwise>
      <xsl:variable name="halfLength" 
           select="floor($lStr div 2)"/>

      <xsl:variable name="processedHalf">
        <xsl:call-template name="lrReplace2">
          <xsl:with-param name="theString"
          select="substring($theString, 
                            1, 
                            $halfLength)" />
          <xsl:with-param name="target" 
                          select="$target" />
          <xsl:with-param name="replacement" 
                        select="$replacement"/>
          <xsl:with-param name="threshold" 
                        select="$threshold"/>
        </xsl:call-template>
      </xsl:variable>

      <xsl:variable name="nodePrHalf"
           select="msxsl:node-set($processedHalf)"/>

      <xsl:value-of select="$nodePrHalf/text()"/>

      <xsl:call-template name="lrReplace2">
        <xsl:with-param name="theString"
        select="substring($theString,
                          $halfLength 
                           - $nodePrHalf/u + 1)"/>
        <xsl:with-param name="target" 
                        select="$target"/>
        <xsl:with-param name="replacement" 
                        select="$replacement"/>
        <xsl:with-param name="threshold" 
                        select="$threshold" />
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

<!--  simple recursive template:   -->
<xsl:template name="lrReplace3">
  <xsl:param name="theString" />
  <xsl:param name="target" />
  <xsl:param name="replacement" />

  <xsl:choose>
    <xsl:when test="contains($theString, $target)">
      <xsl:value-of select=
          "substring-before($theString, $target)"/>
      <xsl:value-of select="$replacement"/>

      <xsl:call-template name="lrReplace3">
        <xsl:with-param name="theString" select=
           "substring-after($theString, $target)"/>
        <xsl:with-param name="target"
                      select="$target"/>
        <xsl:with-param name="replacement" 
                      select="$replacement"/>
      </xsl:call-template>
    </xsl:when>

    <xsl:otherwise>
      <xsl:variable name="lStr" 
           select="string-length($theString)"/>
      <xsl:variable name="lTarget" 
           select="string-length($target)"/>

      <xsl:choose>
        <xsl:when test="$lStr &gt;= $lTarget">
          <xsl:value-of
          select="substring($theString,
                            1,
                            $lStr -$lTarget+1
                            )" />
          <u>
            <xsl:value-of select="$lTarget -1"/>
          </u>
        </xsl:when>

        <xsl:otherwise>
          <u>
            <xsl:value-of select="$lStr"/>
          </u>
        </xsl:otherwise>
      </xsl:choose>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>
</xsl:stylesheet>

To compare the performance of the two stylesheets we used 3 input files: transl01.xml (156 kB) , transl02.xml (313 kB) and transl04.xml (626 kB). Each of them contained one text node with correspondingly: 10 000, 20 000 and 40 000 replacements targets (strings 'AAA'). They are all included in the attached source.zip file. Since here we needed an XSLT processor with node-set extension implemented, we used MSXML 3.0, which we invoked via the msxsl.exe command line utility. The transformations were performed, as before, on a 500 MHZ Pentium, 256 MB RAM PC. We compared the speed of the two algorithms, the last one using 6 different threshold values. The stylesheet based on just the simple recursive template could not have been included in the comparison, since even our smallest input file required a recursion depth of 10 000 which, as expected, was enough to cause call-stack overflow.
Presented below are the results in milliseconds, obtained by running each corresponding stylesheet 3 times and taking the average msxsl.exe- reported time:

The two-stage algorithm, with the threshold parameter set to 5 characters, is functionally equivalent to the classic DVC solution. It is slower, though, because in this specific case, in addition to splitting the input string with the DVC template, which proceeds in exactly the same way in both cases, the two-stage algorithm requires also one call to the simple recursive template lrReplace3 for each terminal segment. However, it is enough to set the threshold to 10 to get this algorithm considerably overtake the pure DVC one. The transformation time decreases until the threshold reaches approximately 1000-2000 characters, due to reduced DVC overhead . After that, its further DVC overhead reduction becomes less and less significant, whereas the growing size of the segments processed by the second-stage template gains more significance, and the transformation time begins to grow. 

When processing our test strings, the two-stage algorithm with optimally set threshold (between 1000 and 2000 characters) turned out to be over 40 times faster than classic DVC solution. This is a much more impressive result than in both previous examples, so it is worthwhile to try to interpret it.

Interpretation of the results

It is relatively easy to interpret the results of the first two examples. In order to do this let us make three observations:

1. Both the pure DVC algorithm, as well as the two-stage algorithm, contains the same first processing, which requires the same amount of time to complete. Thus, the difference in performance between those algorithms results exclusively from the second stage, which in the first algorithm consists in further DVC processing, while in the two-stage algorithm it is implemented as simple recursion. Therefore, the difference in results should be caused by the difference between the pure DVC and the simple recursion when applied to relatively short segments of the input file.
2. In the first two examples, processing such a short segment requires approximately the same number of recursive template calls in both algorithms. To show this let us for the sake of simplicity assume that the segment's length l_s = 2ⁿ. In this case the simple recursion would require l_s - 1 template calls, while the DVC would require: 1 + 2 + ... + 2^n-1 = 2ⁿ - 1 = l_s - 1 calls (splits), so, in this special case, the number of recursive calls is exactly the same in both algorithms.
3. The DVC template is much more complicated than the simple recursive one. First, it has to compute the length of the input by calling the XPath function count or string-length. Then, it has to use the operator div and the function floor. And last, but not least, it has to perform two r