[MLton] Vector.fromList[] performance

Matthew Fluet fluet at cs.cornell.edu
Thu Oct 26 20:03:05 PDT 2006

>> I really don't think that it is completely out of the question to
>> recover a direct construction at this point.  The essential thing is
>> to identify that the loops L_179,L_180 and L_186,L_187 are called on
>> directly constructed lists, and then unroll the loops the length of
>> the list.
> Fair enough.  But noticing that a loop terminates, that unrolling it
> won't blow up code size, and then unrolling it completely, is pretty
> far from the kind of stuff MLton has done in the past (not that we
> shouldn't do it).

True.  My point is only that I think it is reasonably to imagine an 
optimization that eliminates the list construction, length, and fold; it 
is a pretty localized analysis and transformation.

> One possible advantage of putting Vector_fromList into MLton and
> teaching MLton's optimizer about vectors would be that the SSA
> optimizer could take advantage of their immutability.  Recovering that
> from the array-cast-to-vector might be tricky.

You mean eliminating vector subscript operations in favor of the 
vector elements known at creation?  That might be harder to get from the 
array-cast-to-vector (although, in this situation, it should be clear that 
the array doesn't escape before the cast).

> Another thought I had, short of implementing loop unrolling within
> MLton, was to change the implementation of Vector.fromList in the
> basis, and do the unrolling manually.  Something like
> fun fromList l =
>   case l of
>      [] => ...
>    | [x0] => ...
>    | [x1, x2] => ...
>    | [x1, x2, x3] => ...
>    | _ => <old code for fromList>

That would seem to work.

More information about the MLton mailing list