[MLton] Vector.fromList[] performance

[Benoit Hudson]

On 10/25/06, Stephen Weeks <sweeks at sweeks.com> wrote:
> [lots]

Two comments:
1. Part of the deal is that mlton thinks it needs to heap-allocate the
list and vector.  Ideally, mlton would not: after inlining
Vector.fromList, it can discover from the SSA (or, really, any basic
block form) that there's no pointer to the vector or list that is ever
leaked from the "vectors" function; and it can also discover (after
tail recursion elimination) that the list and vector can be safely
stack-allocated.  Basically, this is a simple version of region
analysis, and would replicate SML/NJ's optimisation of this code.

Given the SSA representation already computed, it seems that this
should be a fairly self-contained project: just adding another
compiler pass that comes after all other analysis-heavy passes.  It's
too bad I already did my compilers class, but I might be able to pitch
it to some of the younger PL students next semester.

2. It'd be great if mlton could entirely eliminate the construction of
the vector and list here.  In my actual code, where I create
vectors/lists is often when two parts of the code that store
everything as tuples communicate via a signature that specifies the
use of a vector or list.  Most of the functions are very simple and
thus very inlineable.  For instance:

functor Triangulation(G: GEOMETRY) = struct
  type triangle = G.point * G.point * G.point
  ...
  fun inSimplex (t: triangle, p: point) = G.inSimplex([#1 t, #2 t, #3 t], p)
end

structure Geo2d :> GEOMETRY = struct
  type point = real * real
  ...
  fun inSimplex (points, p) =
    case length points of
      3 => (* break up the list into 6 reals and call
ExactPredicates.orient2 thrice *)
    | _ => raise WrongDimension
end

Theoretically it should be possible to inline Geo2d.inSimplex into
Triangulation.inSimplex and thus eliminate the conversion to a list,
along with the case statement.  Any solution that could handle that
should also be able to automatically inline Vector.fromList of course,
so I presume this is somehow Hard.  On the other hand, this is
evidence of this hard project being worthwhile.

-- Benoît