Re: [xsl] Cheaper to prepend or append an item to a sequence?

[iwanttokeepanon <iwanttokeepanon@xxxxxxxxx>]

>> On Tue, Feb 22, 2011 at 8:32 AM, Michael Kay <mike@xxxxxxxxxxxx> wrote:
>>
>> > Even with a forward-chained list, you can implement append without
copying
>> > if you choose, at least for the first append operation to a given list
>> > (which 9 times out of 10 will be the only append operation).
>>
>> How is that?  If I have X=[1,2,3] ; Y=X ; Z=Y++[4]
>>
>> How can Z append Y without copying it first?  You of course cannot
>> modify Y in FP at all (which you know), much less w/o changing X.

On Tue, Feb 22, 2011 at 4:15 PM, Liam R E Quin <liam@xxxxxx> wrote:
> Saxon is not itself written in a functional language.
>
> Suppose that X is not used again, but only Z is used, in your example.
> So, we have at the start:
>    X [1, 2, 3]
>    Y undefined
>    Z undefined
> and then at the end we have
>    X irrelevant
>    Y irrelevant
>    Z [1,2,3,4]
> The underlying implementation could write, procedurally,
>    Z.listStart := X;
>    tmp := [4]; /* make a new list */
>    X.lastItem.next = tmp; /* append */
>    X.lastItem = tmp; /* save the end pointer */
> This is an O(1) list append, and no copy was used.  It's also a case
> that's worth optimising in a lot of languages.
>
> Of course, keeping a pointer to the last item in a list as well as the
> first increases memory overhead; it's a tradeoff.  And good code would
> abstract that operation of appens-without-copy, obviously.

Thanks Michael and Liam, that makes sense.  Having an end pointer or
scope information that let's you actually mutate an irrelevant list
would be great optimizations in the implementation.

--
Rod