[racket] Typed Racket - (Sequenceof Index) As Looping Index

At Wed, 27 Feb 2013 16:34:46 -0500,
Ray Racine wrote:
> The below is just an observation.
> 
> Historically in TR I've always struggled with Index vs Fixnum vs Natural
> for the vector indexing type when iterating over a vector (or large
> sub-ranges or even larger vectors).  Either the Optimizer complains that an
> index? check was not elided in a vector-ref OR you end up doing something
> along the lines of  (assert (add1 idx) index?) while looping your index
> variable passing over the Vector.
> 
> But I've just noticed that one can construct TR recognized (Sequenceof
> Index).
> 
> So in theory, TR + Compiler should be able to elide a number of checks,
> such as (assert idx index?), use `unsafe-vector-ref', even elide in loop
> bounds checks if the vector is supplied to the 'for'.  This assumes the
> (Sequenceof Index) is an efficient generator.  i.e., (in-range 3 10000000)
> is not allocating 10000000 somethings. ( I don't know what it "really" is
> happening overall, just what I think is possible.  Sufficiently smart
> compiler yada yada.)

The TR optimizer is not smart enough to completely elide bounds
checking[1]. If a vector index is guaranteed to be an `Index', the
optimizer avoids checking whether the index is >= 0, uses unsafe fixnum
operations for that check, and then calls `unsafe-vector-ref'. Not as
fast as calling `unsafe-vector-ref' directly, but still an improvement
over plain `vector-ref'.

At Wed, 27 Feb 2013 16:51:42 -0500,
Ray Racine wrote:
> Just to be clear.  The below does work in TR and idx is of type Index.
> However when one embeds the (in-range 3 5)  directly in the for/vector idx
> is not of type Index.  No reason why it shouldn't however.

The `for' macros recognize the `in-*' forms and, instead of actually
calling the corresponding functions, generate optimized code in-line.
This means that TR, instead of seeing the call to `in-range', sees the
optimized expansion and typechecks that. Since that code uses `+' in
unrestricted ways, TR can't assign precise types.

Vincent


[1] Except in very limited cases, where a vector with a bounded-length
vector type is accessed with an index of a singleton type that's within
the bound. Basically, when vectors are used as poor man's structs.