example of dynamic optimization

[uicbert.eecs.uic.edu!wilson@uxc.cso.uiuc.edu]

To motivate the discussion of dynamic optimization, here's a simple
example of why I think it might be worthwhile.

Suppose you have a language in which you can have homogeneous collections
like array-of-integer.  (Or an implementation that lets you declare them.)
Suppose also that the language is basically dynamically typed, and that
the declared types are attached to the objects at runtime.  So an array
of integer would have a header saying so.

Now suppose we define a routine that processes collections, looping to
apply some operation to its elements.  A dynamic optimizing system
would generate a generic version of the code that checks the types
of the arguments and then dispatches to an optimized version for those
types.  If it has never seen that combination of types before, a new
version is created on the fly.

So the first time this generic code sees an array-of-integer, it compiles
a version of the looping routine that assumes each element is an integer,
omitting tag checks, unrolling the loop, etc.

The generic code must always check the collection's type when it is
executed, but the compiled code it dispatches to needn't.  (If it's
not a homogeneous collection, it simply dispatches to a normal
version with type checking.)

The nice thing about this is that the code is still generic from the
programmer's point of view, and type checking is not abandoned.  (Unlike
systems in which declarations tell the compiler to make assumptions
at a particular point in the code.)

My guess is that for most programs, most routines are only ever given
one kind of argument, so there wouldn't be an explosion of versions.
(You can always use a cache and throw away disused versions.)

At least for this example, the optimization would be transparent and
safe.  If somebody changes (at another point in the code) the type
of some object that is passed to the optimized routine, the dynamic
check will ensure that an appropriate version is generated.

Now the question is how general this system could be, using more
sophisticated type inference than recognizing homogeneous collections.
And can it be combined with nifty trace-scheduling techniques to 
precompute paths through often-executed chunks of code and seriously
optimize them?

Paul R. Wilson                         
Human-Computer Interaction Laboratory
U. of Illin. at C. EECS Dept. (M/C 154)   wilson%uicbert@uxc.cso.uiuc.edu
Box 4348   Chicago,IL 60680