[MLton] Vector.fromList performance
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