Subject: [xsl] tail recursion optimization (was How efficient is DVC?) From: Mike Brown <mike@xxxxxxxx> Date: Sat, 22 Mar 2003 23:32:05 -0700 (MST) |
One thing Robert van Dalen said in his original post was "Because most XSLT implementations out there still do not support tail-recursion elimination, DVC is the way to go if you want to process a lot of nodes." While DVC is the way to go for large amounts of data (as proven by Dimitre), it's not accurate that XSLT implementations don't support tail-recursion elimination. I can't speak for all of them, but many do. The problem that when the recursive template is a matching template instead of a named template, it is hard for the processor to recognize that the apply-templates at the end of the template will result in the same template being applied. For example, Robert's second example has this: <xsl:template match="group"> <xsl:copy> <xsl:copy-of select="@*"/> <xsl:copy-of select="./city"/> </xsl:copy> <xsl:apply-templates select="./group"/> </xsl:template> I don't know if any processors can optimize this. It may seem obvious to you and me that the apply-templates instruction will result in this same template being applied, but there might be some other template that also matches certain 'group' elements at a higher priority, so there's no easy way for the processor to be sure (before runtime) that this template will be the one that is invoked for every one of the selected nodes. Or at least, the analysis required to be certain that this is tail-recursive is not simple enough that anyone has bothered to figure it out yet. (Suggestions welcome...) So for now, the way to tell a processor to use its tail recursion optimization is to use a named template. It's OK to use xsl:if or xsl:choose/xsl:when, as long as the recursive call is at the end (i.e. nothing else that could generate output comes after it): <xsl:template match="group"> <xsl:call-template name="process-group"> <xsl:with-param name="group-node" select="."/> </xsl:call-template> </xsl:template> <xsl:template name="process-group"> <xsl:param name="group-node"/> <xsl:if test="$group-node"> <xsl:copy> <xsl:copy-of select="$group-node/@*"/> <xsl:copy-of select="$group-node/city"/> </xsl:copy> <xsl:call-template name="process-group"> <xsl:with-param name="group-node" select="$group-node/group"/> </xsl:call-template> </xsl:if> </xsl:template> Mike -- Mike J. Brown | http://skew.org/~mike/resume/ Denver, CO, USA | http://skew.org/xml/ XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: [xsl] How efficient is DVC? - A, Michael Kay | Thread | Re: [xsl] tail recursion optimizati, Robbert van Dalen |
Re: [xsl] How efficient is DVC? - A, Mike Brown | Date | [xsl] Re: How efficient is DVC? - A, Dimitre Novatchev |
Month |