[MLton] Vector.fromList[] performance

[Stephen Weeks]

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

> After that, constant folding in the shrinker should turn it into a single 
> basic block that allocates the array, directly fills the elements, and 
> then casts to a vector.

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.

> Which optimizer?

I was thinking that either the XML optimizer or the SSA optimizer
would do it, although I was leaning toward XML in my mind so that the
SSA optimizer wouldn't have to learn a new primitive.

> Once you determine that something is a directly constructed list in
> SSA, I don't see that it is much harder to determine whether the
> list is used in Vector_fromList or if the list is used in a loop.

This I disagree with.  Noticing that there is a constructed list
supplied to Vector_fromList is trivial.  It fits in with the current
shrinker architecutre.  Discovering terminating loops is significantly
more complicated.


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>