Re: Type-based Optimizatoins? [was: tail calls [was: Vanishing MrEd] ]

[Noel Welsh <noelwelsh@yahoo.com>]

> So, I'm left wondering if there isn't room for
> improvement in MzScheme's
> internal representation of data types.  For example,
> I wonder if Andrew
> Wright's soft type system could be used in an
> optimization pass in
> the "scheme-to-c" mode of the compiler to perhaps
> create fast-paths for
> native C data types?

I'm also interest in speed improvements.  Andrew
Wright's work has moved on to control flow based type
inference.  I think they decreased run-time to between
80 and 10(!)% by removing type checks and inlining
functions. See
http://citeseer.nj.nec.com/jagannathan98polymorphic.html
 There is also source code available.
 
The creator of Stalin (Jeff Siskind) has a tech report
called "Flow-Directed Lightweight Closure" that
explains one optimisation Stalin does, again based on
control flow.  See
http://external.nj.nec.com/homepages/qobi/papers.html

Spidey must include some form of control-flow
analysis, and it, IMO, is the key to speed
improvements.  Some optimisations one could do with a
control flow analysis include:
- removing type checks
- unboxing
- inlining
- method dispatch (e.g. when the type of an object is
known the method can be selected at compile time).
- folding calls (don't know what this optimisation is
called, but if you have a sequence of calls like
(filter x (map y list)) then the calls to x and y can
be collapsed into one recursion over list)

I'd like to see 'machine types', like 32-bit integers,
and associated operations included as well, and
functional arrays in the style of SAC
(http://www.informatik.uni-kiel.de/~sacbase/).  

cya,
Noel

__________________________________________________
Do You Yahoo!?
Yahoo! Auctions - Buy the things you want at great prices. 
http://auctions.yahoo.com/