[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:

Subject: stack usage in for-each and apply-templates (was Re: Is xsl:for-each "syntactic sugar"?)
From: "C. M. Sperberg-McQueen" <cmsmcq@xxxxxxxxxxxxxxxxx>
Date: Fri, 7 May 2010 11:55:50 -0600
 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
****************************************************************

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.