Re: List and String concatenation speed.

On Mon, Aug 29, 2016 at 9:21 AM, Matthew Fluet <[email protected]> wrote:
> 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

Actually, it is a little more subtle.  There is a common "problem"
with benchmarking with MLton.  As an aggressive optimizing compiler,
one sometimes needs to work hard to be sure that the code that is
being executed is the code that is intended to be compared.  Note the
main benchmark loop/code:

> fun loop 0 f = ()
>   | loop i f = (f (); loop (i - 1) f)
> val _ = loop N (fn () => (l @ [0]; ()))

The result of the @ is completely ignored.  MLton will, therefore,
happily optimize the non-tail-recursive append function into a
tail-recursive function that simply walks the list and returns ().
(Unfortunately, MLton does not (yet) know that a simple traversal of a
(necessarily finite) list must terminate.)  Similarly, noting that no
code ever examines the elements of any of the lists, MLton happily
turns all of the "int list" data structures into "ignored list" data
structures:
  datatype ilist = inil | icons of ilist
For the List.@ implementation, the inner reverse still needs to build
up the "reversed" list, but the outer appendRev gets optimized to
simply walk that reversed list and return ().

If I change the main loop/code to use the result of append:

  val _ = loop N (fn () => if List.nth (l @ [0], 19) = 19 then () else
raise Fail "bug")

then the two implementations are much closer, although the List.@
implementation is still a little slower than the non-tail-recursive @:

[mtf@uller tmp]$ ./l1
11.853887
[mtf@uller tmp]$ ./l2
8.385946

-- 
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].


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