Re: Cheaper to prepend or append an item to a sequence

On Tue, 2011-02-22 at 14:00 -0600, iwanttokeepanon wrote:
> 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.

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.

Liam


-- 
Liam Quin - XML Activity Lead, W3C, http://www.w3.org/People/Quin/
Pictures from old books: http://fromoldbooks.org/
Somtimes blog - http://barefootliam.org/