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 > 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 |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Namespace Identifiers - U, David Carlisle | Thread | [xsl] RE: Elements between attribut, Oliver Sick |
[xsl] Namespace Identifiers - URI, , Hewko, Doug | Date | RE: [xsl] dynamic import of stylesh, Chris Bayes |
Month |