## [saxon] How to append to a sequence of elements in linear time?

 [saxon] How to append to a sequence of elements in linear time? From: Dimitre Novatchev - 2005-11-27 07:06:11 ```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) =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D 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: 0 -- Cheers, Dimitre Novatchev --------------------------------------- To avoid situations in which you might make mistakes may be the biggest mistake of all. ```

### Thread view

 [saxon] How to append to a sequence of elements in linear time? From: Dimitre Novatchev - 2005-11-27 07:06:11 ```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) =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D 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: 0 -- Cheers, Dimitre Novatchev --------------------------------------- To avoid situations in which you might make mistakes may be the biggest mistake of all. ```
 RE: [saxon] How to append to a sequence of elements in linear time? From: Michael Kay - 2005-11-29 00:20:26 ```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: ; 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: saxon-help-admin@...=20 > [mailto:saxon-help-admin@...] On Behalf Of=20 > Dimitre Novatchev > Sent: 27 November 2005 07:06 > To: saxon-help@... > Subject: [saxon] How to append to a sequence of elements in=20 > linear time? >=20 > As described in the documentation, one of the changes in Saxon 8.6 is > the following: >=20 > "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." >=20 > I need an example how to use SharableSequence, because my attempts > show still quadratic behavior: >=20 > Nodes added Time (ms) Memory (MB) > = =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D > 100 15 1.9 >=20 > 200 31 3.2 >=20 > 400 31 4.6 >=20 > 800 31 13 >=20 > 1600 93 24 >=20 > 3200 453 45 >=20 > 6400 1687 145 >=20 > 12800 5890 551 >=20 >=20 >=20 >=20 > 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: >=20 > xmlns:xsl=3D"http://www.w3.org/1999/XSL/Transform"; > xmlns:xs=3D"http://www.w3.org/2001/XMLSchema"; > xmlns:f=3D"http://fxsl.sf.net/"; > exclude-result-prefixes=3D"f xs"> >=20 > >=20 > > 0 > >=20 > > "f:multiAppend(\$vEnv, 'x', 1,12800)"/> > >=20 > > > > >=20 > > > > > >=20 > > > > > >=20 > "if(\$pminValue le \$pmaxValue) > then > f:multiAppend(f:appendENV(\$pEnv,\$pvarName,\$pminValue), > \$pvarName, > \$pminValue+1, > \$pmaxValue > ) > else \$pEnv" > /> > > >=20 > -- > Cheers, > Dimitre Novatchev > --------------------------------------- > To avoid situations in which you might make mistakes may be the > biggest mistake of all. >=20 >=20 > ------------------------------------------------------- > This SF.net email is sponsored by: Splunk Inc. Do you grep=20 > through log files > for problems? Stop! Download the new AJAX search engine that makes > searching your log files as easy as surfing the web. =20 > DOWNLOAD SPLUNK! > http://ads.osdn.com/?ad_idv37&alloc_id=16865&op=3Dick > _______________________________________________ > saxon-help mailing list > saxon-help@... > https://lists.sourceforge.net/lists/listinfo/saxon-help >=20 ```