Re: [xsl] Recursion performance (fibonacci numbers)

Subject: Re: [xsl] Recursion performance (fibonacci numbers)
From: Mukul Gandhi <gandhi.mukul@xxxxxxxxx>
Date: Mon, 16 Jan 2006 21:54:21 +0530
Hi Mike,
   I tried saxon:memo-function="yes". But I am getting nearly the same
timing.

The new timings reported are
n=32 -> 34.5 secs
n=33 -> 54.7 secs
n=34 -> 1 min 27 secs
n=35 -> 2 mins 17.9 secs

I suspect the algorithm is failing to take advantage of memoization
with this hint.

Regards,
Mukul

On 1/16/06, Michael Kay <mike@xxxxxxxxxxxx> wrote:
> Try setting saxon:memo-function="yes" on the xsl:function element. This
> should give you linear performance.
>
> Michael Kay
> http://www.saxonica.com/
>
> > -----Original Message-----
> > From: Mukul Gandhi [mailto:gandhi.mukul@xxxxxxxxx]
> > Sent: 16 January 2006 15:08
> > To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> > Subject: [xsl] Recursion performance (fibonacci numbers)
> >
> > Dear All,
> >    I am running this XSLT stylesheet with Saxon b 8.6.1. This prints
> > 1st n Fibonacci numbers, where n is supplied as a stylesheet
> > parameter.
> >
> > <?xml version="1.0" encoding="UTF-8"?>
> > <xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
> >                 xmlns:xs="http://www.w3.org/2001/XMLSchema";
> >                 xmlns:myfunc="http://dummy";
> >                 version="2.0">
> >
> > <xsl:output method="text" />
> >
> > <xsl:param name="n" />
> >
> > <xsl:template match="/">
> >   <xsl:for-each select="1 to $n">
> >     <xsl:value-of select="myfunc:fibonacci(position())"
> > /><xsl:text> </xsl:text>
> >   </xsl:for-each>
> > </xsl:template>
> >
> > <xsl:function name="myfunc:fibonacci" as="xs:integer">
> >   <xsl:param name="n" as="xs:integer" />
> >
> >   <xsl:sequence select="if (($n = 1) or ($n = 2))
> >                         then
> >                           1
> >                         else
> >                           (myfunc:fibonacci($n - 1) +
> > myfunc:fibonacci($n - 2))"
> >                        />
> >
> > </xsl:function>
> >
> > </xsl:stylesheet>
> >
> > The problem is, that it takes long time for large values of n. I
> > observed the following timing
> >
> > n=32 -> 35.5 secs
> > n=33 -> 55.2 secs
> > n=34 -> 1 min 27.3 secs
> > n=35 -> 2 mins 20.1 secs
> >
> > Is it possible I can improve the performance of this stylesheet for
> > large values of n?
> >
> > Regards,
> > Mukul

Current Thread