common sub-expressions

Stephen Weeks MLton@sourcelight.com
Wed, 9 Aug 2000 09:05:19 -0700 (PDT)


> Speaking  of  common  subexpression  elimination,  I  was looking at the code
> generated for an FFT and it REALLY hurt (maybe not in terms of  run-time  but
> in  terms  of  pain)  to  see the repeated checks for subscript out of range.
> First, the way the code  is  written  it  is  `clear'  that  the  checks  are
> unneeded.  Ignoring that, what really hurts is code like
>     Array.update(a, i, x + Array.sub(a, i))
> where it checks if i is in range twice.

Here is an upper bound on the run-time pain for fft.
-DMLton_safe=1	37.16
-DMLton_safe=0	35.06

I.E. a 6% hit.  This is noticeable enough to be worth doing.  It's on the
ever-expanding todo list.
 
> On  an unrelated note, what is the story on not-flattening out array entries?
> I.e., if I have an array whose entries are tuples,  it  is  always  an  extra
> level of indirection to get to the entries of the tuple.  Why are these never
> flattened out?

For now these are not flattened.  The todo list already contains an entry (I
think I sent mail to mlton a while back) to put in an optimization to convert
('a * 'b) array to 'a array * 'b array.  However, in talking with Matthew and
Neal, we realized that we could do better in RCPS, because that type system can
express the idea of a (flat 'a * 'b) array.  So, I think I'm gonna hold off on
that optimization for a while.  If you really want it on CPS, I think you could
write it in a few hours and less than 300 lines.