[MLton] array flattening (was: bool array size)

[Stephen Weeks]

> The only place where there was an array subscript/update without
> selecting the components was in the quick sort.

I bet that's enough.  Since quicksort is swapping elements as
2-tuples, the flattening optimizer, which is very conservative about
introducing new allocation, decides not flatten.  The optimizer isn't
smart enough to notice that the tuple allocation that it would
introduce would be simplified away because the tuple is immediately
used in a flattened array.

Sad.

To see if this explanation is correct, you could try passing a custom
"swap" function to quicksort.  Something like:

----------------------------------------------------------------------
fun swap (a, i, j) =
   let
      val {key = ki, ord = oi} = Array.sub (a, i)
      val {key = kj, ord = oj} = Array.sub (a, j)
      val () = Array.update (a, i, {key = kj, ord = oj})
      val () = Array.update (a, j, {key = ki, ord = oi})
   in
      ()
   end
----------------------------------------------------------------------

But that's really very ugly.  Even better would be to improve the
optimization, ssa/deep-flatten.fun, to flatten in this case.  After
some thought, of course, to make sure that it doesn't introduce any
space-safety issues.