Re: [Caml-list] Preferred Way to Split a List

[skaller <skaller@users.sourceforge.net>]

On Mon, 2007-10-29 at 10:34 +0100, Christophe Raffalli wrote:
> Or
> 
> let split l n =
>   let rec aux acc l n =
>      if n = 0 then List.rev acc, l
>      else match l with
>         [] -> List.rev acc, []
>      | hd::l -> aux (hd::acc) l (n-1)
>   in aux [] l n
> 
> This is tail recursive, it does not use magic nor  references
> and keed the original ordering of the list.

Yes, but it double handles the head needlessly. Ignoring
the interesting observation you make below, this would
be expected to transfer head memory twice into the cache,
when once would suffice.

> Finally, I did in the past some testing  comparing a tail-rec append or map
> using magic and the composition of rev and rev-append or rev-map ...
> There was no noticable difference, because the extra cost  of
> mutability (regarding the managment of the grey val list) compensate
> the extra call to reverse.

However, you raise here an important issue not covered well anywhere:
when you have a garbage collection, the effect of some operation
should include not just the local algorithmic considerations
but also the cost of the garbage collection.

In the equivalent Felix code, there is no issue with write
barriers because Felix collector doesn't use them, so mutations
don't incur any cost. OTOH allocations are expensive.

Now, back to collectors .. the append is a special.
The mutations in the append are not mutations, but deferred
initialisations, that is, the write operation is guaranteed
to be replacing a NULL pointer.

Overwriting of NULL pointers is already possible in functional
coding without it implying mutation.

So one might imagine a collector with a minor and major heap,
in which the major heap requires special handling for mutations.
However the rule for moving an object out of the minor heap
is that the object must be fully initialised. (all pointers
in the block are non-null). 

In that design (I have no idea if it is viable!) the performance
might be different for the 'append' and other mutations.

The bottom line is that a good point is made that the 
usual fine detail performance analysis doesn't apply to
a garbage collected language.. thanks for pointing this out!


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net