[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] stack usage in for-each and apply-templates (was Re:
On 6 May 2010, at 19:49 , Dimitre Novatchev wrote:
>> 4. Favor recursive functions over xsl:for-each. (True or False) > No, Always choose iterative processing over recursion, if this is > possible. You may gain significant efficiency this way. True. But if we are going to allow efficiency of execution to play a role in our choice (it's not always wrong to do so, I guess!), then in the context of XSLT it's important to note that the choice between for-each and apply-templates with a mode (along the lines suggested by David Carlisle) is not a choice between iterative processing and recursion: both constructs are iterative in XSLT. In imperative languages, it's different. If you iterate over the integers from 1 to 1000000 using a tail-recursive function of the form (defun f (i) ... body ... (f (+1 i))) or declare function f ( $i : xs:int) as xs:int { ... body ... if ... then return $result else return f($i + 1) } then the stack will grow as the recursion proceeeds, and in the absence of tail-recursion optimization you are going to end up trying to push a million stack frames onto the execution stack, which means you are likely to run out of stack space. And in the imperative languages I know, those are your two choices: iterative constructs or iteration by means of tail-recursive functions. It's possible to write a similar style of (tail-) recursive template in XSLT, of course. (I'm not telling D.N. anything he doesn't know, of course.) As far as I can tell the main reason (maybe the only reason?) to do it is to pass some value along in a parameter that serves as a kind of accumulator, and finally, when the recursion ends, to pass back the accumulated value, so that the pattern I have in mind is something like this: <xsl:apply-templates select="first-node-of-nodeset-foo" mode="s.w.a.b."/> <xsl:template match="*" mode="s.w.a.b."> <xsl:param name="accumulator" select="0"/> ... body ... <xsl:choose> <xsl:when test="... termination condition ... "> <xsl:value-of select="$new-accum"/> </xsl:when> <xsl:otherwise> <xsl:apply-templates select="next-node-of-nodeset-foo" mode="s.w.a.b."> <xsl:with-param name="accumulator" select="$new-accum"/> </xsl:apply-templates> </xsl:otherwise> </xsl:choose> </xsl:template> (The mode name 's.w.a.b.' stands for 'Scheme with angle brackets' and is intended to amuse those readers who may find it amusing. The rest of you can stop groaning now, please. Thank you.) For this, you really do need tail-recursion optimization or a lot of stack space, at least in principle. (In practice, when I have needed this pattern it has run without any trouble at all, perhaps because my input documents were not large. The common view seems to be that this will always fail on anything but artificially small examples; in reality, it has always worked for me.) Two observations arise here: (1) I don't know how to get the effect of the accumulator with xsl:for-each. (But just wait for XSLT 2.1 and the xsl:iterate instruction!) Is it possible to do accumulator-passing in for-each? (2) As David Carlisle has pointed out, if you take a for-each construct of the form <xsl:for-each select="foo"> ... body ... </xsl:for-each> the equivalent apply-templates construction does not resemble the s.w.a.b. example above, but instead has <xsl:apply-templates select="foo" mode="unique-mode-id"/> and elsewhere <xsl:template match="*" mode="unique-mode-id"> <!--* or match="@*|/|node()" if you like, but let's * assume we are matching only elements *--> ... body ... </xsl:template> This iterates over the elements which match the select pattern, and the resulting stack usage will be that a) A node-set stack frame F1 goes on the stack. b) A node N is selected from the node set (this is done for each node in F1 in turn); a template T is found for the node N. If the node set has no nodes, or none that have yet been selected, then we go to step f). c) A template frame F2 is added to the stack for the evaluation of template T with context node N, d) Template T is evaluated with context node N. Here, the stack may grow owing to instructions in T, just as it may grow in the for-each case owing to the instructions in the body of the for-each. After all, they contain the same body. Any stack growth caused by constructs in the body will be the same for for-each and for apply-templates, so that's a wash. At the end of the evaluation, template frame F2 will once again be at the top of the stack. e) The template frame F2 is popped from the stack, so the node-set frame F1 will be at the top of the stack again. Go to step b). f) The node set frame F1 is popped from the stack. If the node set we are concerned with has K members, then the loop from b) to e) will be run once for each node in the node set selected, but even without tail-recursion optimization, the stack will grow by 1 item, not by K items. Contrast the s.w.a.b. example, in which you do get an increase in stack depth of K frames (or in a really naive implementation K*2, since each recursion will push both a singleton node-set and a template frame onto the stack). I'm assuming a fairly naive pattern of stack usage here; it's possible to improve it in various ways. But an implementation would have to go a long way out of its way to make a single call to apply-templates, with a select expression matching K nodes, increase stack depth by K instead of by 1. There may be good reasons to use for-each. It may for example be better optimized than an apply-templates with a mode (but if the mode has only a single template, which matches everything, just how slow can the processor make the search for the appropriate template?). Some people may for example find for-each clearer (although in my experience some programmers who find for-each clearer are not comfortable in XSLT in the first place). But difference in stack usage is NOT a reason to choose for-each over apply-templates. -- **************************************************************** * C. M. Sperberg-McQueen, Black Mesa Technologies LLC * http://www.blackmesatech.com * http://cmsmcq.com/mib * http://balisage.net ****************************************************************
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|