Re: List and String concatenation speed.

On Mon, Aug 29, 2016 at 6:31 AM, Kostirya <[email protected]> wrote:
> I I found that List.@ is very slow. It is slower than:
>
>     fun x @ nil = x
>       | x @ y = let
>         fun app nil = y
>          | app (a :: b) = a :: app b
>         in app x end

The Basis Library implementation of List.@ is the classic
tail-recursive implementation that reverses the first list and then
append-with-reverse onto the second list:
  https://github.com/MLton/mlton/blob/master/basis-library/list/list.sml#L49
This compiles to a nice tight local loop, but does require traversing
and allocating the list twice.  Asymptotically, this should be better
than the naive non-tail-recursive implementation (because the cost of
a non-tail call and return should be more than allocating a cons).
But, your results are interesting.  Also, the tail-recursive
implementation generates more garbage, which may cause an increase in
GC costs.

> Here are the benchmark results:
>
>> mlton l.sml && ./l
> 12.066907
>> mlton l.sml && ./l
> 1.934971
>
>
> String concatenation is slow due to similar reasons.

String concatenation uses a completely different implementation:
  https://github.com/MLton/mlton/blob/master/basis-library/arrays-and-vectors/sequence0.sml#L282
Note that this is a polymorphic implementation, used for all types of
arrays and vectors.  In particular, it copies the elements of the
input sequences element by element into the output sequence.

>> poly --script string_concat.sml
> 0.462269
>
>> mlton string_concat.sml && ./string_concat
> 2.713323

It looks like Poly/ML uses memmove to implement String.^, which would
be more efficient for character sequences.

-- 
You received this message because you are subscribed to the Google Groups "MLton-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].


------------------------------------------------------------------------------