How to append to a sequence of elements in linear time?

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

How to append to a sequence of elements in linear time?

Dimitre Novatchev
As described in the documentation, one of the changes in Saxon 8.6 is
the following:

"A new optimization has been introduced to ensure that a recursive
function that builds a sequence by incremental append operations now
has linear performance: the time taken, and the memory used, are both
proportional to the length of the sequence (and to the number of
recursive calls). Note that it is useful to write such functions to be
tail recursive. The optimization typically operates when a function
returns a result that is obtained by appending to the sequence
supplied as the argument. This optimization makes use of a new
sequence representation (ShareableSequence) that allows many sequences
to share the same underlying list in memory, provided that the value
of each of the sequences is a leading sublist of this underlying
list."

I need an example how to use SharableSequence, because my attempts
show still quadratic behavior:

Nodes added     Time (ms)      Memory (MB)
==================================
    100                                15                   1.9

    200                                 31                  3.2

    400                                 31                  4.6

    800                                 31                 13

  1600                                93                  24

  3200                              453                 45

  6400                            1687               145

12800                            5890               551




Here's the tested code (does not use any source xml document) run once
with each of the leftmost column values substituted for the last
argument of f:multiAppend() below:

<xsl:stylesheet version="2.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
 xmlns:xs="http://www.w3.org/2001/XMLSchema"
 xmlns:f="http://fxsl.sf.net/"
 exclude-result-prefixes="f xs">

 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 <xsl:variable name="vEnv" as="element()*">
   <x0>0</x0>
 </xsl:variable>

 <xsl:template match="/">
     <xsl:sequence select=
       "f:multiAppend($vEnv, 'x', 1,12800)"/>
 </xsl:template>

 <xsl:function name="f:appendENV" as="element()*">
  <xsl:param name="pEnv" as="element()*"/>
  <xsl:param name="pvarName" as="xs:string"/>
  <xsl:param name="pValue" as="item()*"/>

  <xsl:sequence select="$pEnv"/>
  <xsl:element name="{$pvarName}">
    <xsl:sequence select="$pValue"/>
  </xsl:element>
 </xsl:function>

 <xsl:function name="f:multiAppend" as="element()*">
  <xsl:param name="pEnv" as="element()*"/>
  <xsl:param name="pvarName" as="xs:string"/>
  <xsl:param name="pminValue" as="xs:integer"/>
  <xsl:param name="pmaxValue" as="xs:integer"/>

  <xsl:sequence select=
   "if($pminValue le $pmaxValue)
      then
         f:multiAppend(f:appendENV($pEnv,$pvarName,$pminValue),
                       $pvarName,
                       $pminValue+1,
                       $pmaxValue
                       )
      else $pEnv"
   />
 </xsl:function>
</xsl:stylesheet>

--
Cheers,
Dimitre Novatchev
---------------------------------------
To avoid situations in which you might make mistakes may be the
biggest mistake of all.


-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
<a href="http://ads.osdn.com/?ad_idv37&alloc_id865&op=click">http://ads.osdn.com/?ad_idv37&alloc_id865&op=click
_______________________________________________
saxon-help mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/saxon-help
Reply | Threaded
Open this post in threaded view
|

RE: How to append to a sequence of elements in linear time?

Michael Kay
An interim report on this (as it's bedtime...)

Saxon is only using a ShareableSequence if an expression that appends to a
singleton value or a ShareableSequence is evaluated lazily. In this example
the function call that would produce the ShareableSequence isn't evaluated
lazily because the function call is done while evaluating one of the
arguments of a recursive function. Normally function arguments are evaluated
after lazily (after creating the stack-frame of the called function), but
where an argument to a tail-recursive function is itself a function call,
it's evaluated eagerly on the caller's stack frame to avoid blowing the
stack (which wouldn't happen here because the f:appendENV function doesn't
do a recursive call on f:multiAppend, but Saxon hasn't worked that out...)

I tried to get round this by using a variable:

<xsl:function name="f:multiAppend" as="element()*" saxon:explain="yes"
xmlns:saxon="http://saxon.sf.net/">
  <xsl:param name="pEnv" as="element()*"/>
  <xsl:param name="pvarName" as="xs:string"/>
  <xsl:param name="pminValue" as="xs:integer"/>
  <xsl:param name="pmaxValue" as="xs:integer"/>
  <xsl:choose>
    <xsl:when test="$pminValue le $pmaxValue">
      <xsl:variable name="t"
select="f:appendENV($pEnv,$pvarName,$pminValue)"/>
      <xsl:sequence select="f:multiAppend($t,
                       $pvarName,
                       $pminValue+1,
                       $pmaxValue
                       )"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:sequence select="$pEnv"/>
    </xsl:otherwise>
  </xsl:choose>
</xsl:function>

but this revealed other problems: see bugs 1368686 and 1368700. After fixing
these bugs, the original problem remained: Saxon treats the lazily-evaluated
variable used as a function argument with the same caution as the original
function call, again as a result of previous bad experiences.

I'm going to explore two possibilities: firstly, using a ShareableSequence
in cases where an eager evaluation rather than a lazy evaluation is being
performed; and secondly, avoiding the eager evaluation of the innocent
(non-recursive) function call in cases where I can work out that it really
is innocent.

Thank you for continuing to supply such interesting test cases.

Michael Kay
http://www.saxonica.com/

> -----Original Message-----
> From: [hidden email]
> [mailto:[hidden email]] On Behalf Of
> Dimitre Novatchev
> Sent: 27 November 2005 07:06
> To: [hidden email]
> Subject: [saxon] How to append to a sequence of elements in
> linear time?
>
> As described in the documentation, one of the changes in Saxon 8.6 is
> the following:
>
> "A new optimization has been introduced to ensure that a recursive
> function that builds a sequence by incremental append operations now
> has linear performance: the time taken, and the memory used, are both
> proportional to the length of the sequence (and to the number of
> recursive calls). Note that it is useful to write such functions to be
> tail recursive. The optimization typically operates when a function
> returns a result that is obtained by appending to the sequence
> supplied as the argument. This optimization makes use of a new
> sequence representation (ShareableSequence) that allows many sequences
> to share the same underlying list in memory, provided that the value
> of each of the sequences is a leading sublist of this underlying
> list."
>
> I need an example how to use SharableSequence, because my attempts
> show still quadratic behavior:
>
> Nodes added     Time (ms)      Memory (MB)
> ==================================
>     100                                15                   1.9
>
>     200                                 31                  3.2
>
>     400                                 31                  4.6
>
>     800                                 31                 13
>
>   1600                                93                  24
>
>   3200                              453                 45
>
>   6400                            1687               145
>
> 12800                            5890               551
>
>
>
>
> Here's the tested code (does not use any source xml document) run once
> with each of the leftmost column values substituted for the last
> argument of f:multiAppend() below:
>
> <xsl:stylesheet version="2.0"
>  xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
>  xmlns:xs="http://www.w3.org/2001/XMLSchema"
>  xmlns:f="http://fxsl.sf.net/"
>  exclude-result-prefixes="f xs">
>
>  <xsl:output omit-xml-declaration="yes" indent="yes"/>
>
>  <xsl:variable name="vEnv" as="element()*">
>    <x0>0</x0>
>  </xsl:variable>
>
>  <xsl:template match="/">
>      <xsl:sequence select=
>        "f:multiAppend($vEnv, 'x', 1,12800)"/>
>  </xsl:template>
>
>  <xsl:function name="f:appendENV" as="element()*">
>   <xsl:param name="pEnv" as="element()*"/>
>   <xsl:param name="pvarName" as="xs:string"/>
>   <xsl:param name="pValue" as="item()*"/>
>
>   <xsl:sequence select="$pEnv"/>
>   <xsl:element name="{$pvarName}">
>     <xsl:sequence select="$pValue"/>
>   </xsl:element>
>  </xsl:function>
>
>  <xsl:function name="f:multiAppend" as="element()*">
>   <xsl:param name="pEnv" as="element()*"/>
>   <xsl:param name="pvarName" as="xs:string"/>
>   <xsl:param name="pminValue" as="xs:integer"/>
>   <xsl:param name="pmaxValue" as="xs:integer"/>
>
>   <xsl:sequence select=
>    "if($pminValue le $pmaxValue)
>       then
>          f:multiAppend(f:appendENV($pEnv,$pvarName,$pminValue),
>                        $pvarName,
>                        $pminValue+1,
>                        $pmaxValue
>                        )
>       else $pEnv"
>    />
>  </xsl:function>
> </xsl:stylesheet>
>
> --
> Cheers,
> Dimitre Novatchev
> ---------------------------------------
> To avoid situations in which you might make mistakes may be the
> biggest mistake of all.
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep
> through log files
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  
> DOWNLOAD SPLUNK!
> <a href="http://ads.osdn.com/?ad_idv37&alloc_id865&op=ick">http://ads.osdn.com/?ad_idv37&alloc_id865&op=ick
> _______________________________________________
> saxon-help mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/saxon-help
>




-------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc. Do you grep through log files
for problems?  Stop!  Download the new AJAX search engine that makes
searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
<a href="http://ads.osdn.com/?ad_idv37&alloc_id865&op=click">http://ads.osdn.com/?ad_idv37&alloc_id865&op=click
_______________________________________________
saxon-help mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/saxon-help