[MLton] user-level elimination of array bounds checks
Stephen Weeks
MLton@mlton.org
Fri, 23 Jan 2004 07:32:53 -0800
> Don't you also need to check if the arrays are equal?
Agreed.
> > fun get (T (a, i)) = Array.sub (a, i)
> >
> > fun set (T (a, i), x) = Array.update (a, i, x)
>
> Presumably these are the Unsafe sub and updates.
Yes.
> > fun next (T (a, i)) = elt (a, i + 1)
> >
> > fun prev (T (a, i)) = elt (a, i - 1)
>
> I would think that the following is just a little more efficient:
>
> fun next (T (a, i)) = let val j = i + 1
> in if j < Array.length a
> then SOME (T (a, j))
> else NONE
> end
> fun prev (T (a, i)) = let val j = i - 1
> in if 0 <= j
> then SOME (T (a, j))
> else NONE
> end
>
> The point is that a value T (a, i) of type 'a Elt.t is definitely within
> bounds, so we know that 0 <= i andalso i < Array.length a. Hence, it
> certainly follows that 0 <= i + 1 andalso i - 1 < Array.length a.
> Actually, the real point is that if the value was created too far away,
> then the optimizer won't be able to see the bounds check used to create
> the value.
Agreed, bu it doesn't matter. It will all be a single test in the end
because I would implement the bounds check as an unsigned comparison.
fun elt (a, i) =
if Word.fromInt i < Word.fromInt (Array.length a)
then SOME (Elt.T (a, i))
else NONE