[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: stack usage in for-each and apply-templates (was R

Subject: Re: stack usage in for-each and apply-templates (was Re: Is xsl:for-each "syntactic sugar"?)
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Fri, 7 May 2010 12:02:41 -0700
Re:  stack usage in for-each and apply-templates (was R
On Fri, May 7, 2010 at 10:55 AM, C. M. Sperberg-McQueen
<cmsmcq@xxxxxxxxxxxxxxxxx> wrote:
> 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.


This is just a clarification that I used the word "recursion", not
"apply-templates".

And using <xsl:apply-templates> is not automatically synonymous to recursion.

Only when we have <xsl:apply-templates> evaluated *within* a template
(that itself was instantiated explicitly or implicitly by an
<xsl:apply-templates> or <xsl:call-template>) this *may* lead to
recursion if this causes directly or indirectly the same template to
be evaluated further down the call graph.

As for the rest of the text of . M. Sperberg-McQueen's message, there
is probably nothing more to argue about -- these are wellknown facts.

Also it is a fact that not all XSLT implementations recognize/optimize
tail-recursion, so if we are writing a portable XSLT application and
want it to be efficient when processing more or less large XML
documents, we have to resort either to DVC-style recursion or to try
to avoid recursion, if possible.


--
Cheers,
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
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play




>
> In imperative languages, it's different. B If you iterate over the
> integers from 1 to 1000000 using a tail-recursive function of the
> form
>
> B (defun f (i)
> B  B  B  B ... body ...
> B  B  B  B (f (+1 i)))
>
> or
>
> B declare function f ( $i : xs:int) as xs:int {
> B  B ... body ...
> B  B if ... then
> B  B  B return $result
> B  B else
> B  B  B return f($i + 1)
> B }
>
> 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. B 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. B (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?) B 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:
>
> B <xsl:apply-templates select="first-node-of-nodeset-foo"
> B  B mode="s.w.a.b."/>
>
> B <xsl:template match="*" mode="s.w.a.b.">
> B  B <xsl:param name="accumulator" select="0"/>
>
> B  B ... body ...
>
> B  B <xsl:choose>
> B  B  B <xsl:when test="... termination condition ... ">
> B  B  B  B <xsl:value-of select="$new-accum"/>
> B  B  B </xsl:when>
> B  B  B <xsl:otherwise>
> B  B  B  B <xsl:apply-templates
> B  B  B  B  B select="next-node-of-nodeset-foo"
> B  B  B  B  B mode="s.w.a.b.">
> B  B  B  B  B  B <xsl:with-param
> B  B  B  B  B  B  B name="accumulator" select="$new-accum"/>
> B  B  B  B </xsl:apply-templates>
> B  B  B </xsl:otherwise>
> B  B </xsl:choose>
> B </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. B 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. B (In practice, when I have
> needed this pattern it has run without any trouble at all, perhaps
> because my input documents were not large. B 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. B (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
>
> B <xsl:for-each select="foo">
> B  B ... body ...
> B </xsl:for-each>
>
> the equivalent apply-templates construction does not resemble the
> s.w.a.b. example above, but instead has
>
> B <xsl:apply-templates select="foo" mode="unique-mode-id"/>
>
> and elsewhere
>
> B <xsl:template match="*" mode="unique-mode-id">
> B  B <!--* or match="@*|/|node()" if you like, but let's
> B  B  B  B * assume we are matching only elements
> B  B  B  B *-->
> B  B ... body ...
> B </xsl:template>
>
> This iterates over the elements which match the select pattern, and
> the resulting stack usage will be that
>
> B a) A node-set stack frame F1 goes on the stack.
>
> B b) A node N is selected from the node set (this is done for
> B  B  each node in F1 in turn); a template T is found for the node N.
> B  B  If the node set has no nodes, or none that have yet been
> B  B  selected, then we go to step f).
>
> B c) A template frame F2 is added to the stack for the evaluation
> B  B  of template T with context node N,
>
> B d) Template T is evaluated with context node N. B Here, the
> B  B  stack may grow owing to instructions in T, just as it may grow
> B  B  in the for-each case owing to the instructions in the body of
> B  B  the for-each. B After all, they contain the same body. B Any
> B  B  stack growth caused by constructs in the body will be the same
> B  B  for for-each and for apply-templates, so that's a wash. B At the
> B  B  end of the evaluation, template frame F2 will once again be at
> B  B  the top of the stack.
>
> B e) The template frame F2 is popped from the stack, so the
> B  B  node-set frame F1 will be at the top of the stack again. B Go to
> B  B  step b).
>
> 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. B 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. B 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. B 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?). B 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
> ****************************************************************

Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.