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.