wilson@uicbert.eecs.uic.edu (01/13/89)
I am looking for references to advanced techniques in dynamic compilation
and tentative optimization. (Is anybody out there working on such things?
Is anybody doing anything beyond the Deutsch-Schiffman compiled-method
caching and inline caching of method lookups?) In particular, I'm interested
in systems that compile specific *versions* of methods/procedures that
handle polymorphic arguments.
(Especially systems that keep more than one version around, and systems
that proceed to do interesting optimizations based on the particular
combinations of types that it actually encounters.)
The closest thing I've found to what I'm looking for is a paper by E.J.
Van Dyke in the Hewlett-Packard Journal in July 1977 ("A Dynamic Incremental
Compiler for an Interpretive Language," pp. 17-24).
Van Dyke describes Hewlett-Packard's APL/3000, which compiles each
procedure the first time it encounters it. It initially compiles a
very specific version, which assumes that the arguments will be of exactly
the same type next time (e.g., that array bounds will be the same). The
The compiled code contains a short prologue of "signature code" that checks
to see if the assumptions are correct. If not, the code "breaks" and calls
the compiler to recompile it. It is then recompiled with fewer assumptions
(e.g., array type but not array bounds).
I posted my own ideas for dynamic compilation and tentative optimization
on the Scheme list a while back, which is how I got referred to Van Dyke.
I've tagged those postings onto the end of this one for anyone who's interested.
(They contain some basic references to dynamic compilation articles. I'm
really looking for more advanced techniques. The big question for me is
what has happened in tentative optimization in the last ten years.)
I'm told T.C.Miller's 1978 thesis from Yale is also relevant, but have not
received it from Yale yet. It's called "Tentative Compilation: a Design
for an APL Compiler" (Yale U. DCS 78-CS-013, May 1978.)
-------------------------------------
First posting:
-------------------------------------
I've been thinking about using dynamic compilation for Scheme, and wondering
if anybody else is. Have people pretty much abandoned the idea of dynamic
compilation, and if so, was it premature?
Some of the advantages might be:
1) portable images could still run fast
2) an optimizer could be called in to optimize those chunks of
code that are ACTUALLY executed a bunch of times.
(rather than just optimizing the time/space tradeoff between
interpreted and compiled code, it could be used to adjust
compile time/run time tradeoffs.)
3) Transparent, automatic compilation and optimization.
In particular, I'm thinking about a scheme in which inlining would
be done automatically, but dependencies would be recorded. If somebody
changed the value of an inlined procedure or constant, the code
depending on those values would be invalidated and dynamically
recompiled at runtime.
(The mechanism for this depends on near-lexical-scoping. Procedures
that are never redefined in a lexically apparent way could be inlined.
Primitives that can modify things (like first-class environments) in
non-lexically-apparent ways would have to check for dependencies.)
Anybody care to comment on this idea? In particular, is there some
irreducible cost of dynamic compilation that I don't know about? Any
advantages?
(It seems to me that you might dynamically determine what types of
arguments frequently-executed procedures were frequently called with.
You could then compile special versions for the common combinations.
A large-grained check would dispatch to the proper version, within
which most type checking could be eliminated using type inference.
Would this be workable/worthwhile?)
----------------------------------------
second posting:
----------------------------------------
There seems to be some interest out there, so here's a bit more detail
on those dynamic compilation ideas:
* When a chunk of code is dynamically compiled (not optimized yet), it
is given a little prologue that increments a count every time it is
executed. When the count exceeds a threshold, the code is recompiled
with a much higher level of optimization. The most optimized code
would not have this prologue to slow it down, since it wouldn't
need it anymore. Highly optimized code might be less subject
to being discarded as well.
* The business about noticing common types of arguments and compiling
specially optimized versions could be handled similarly. A little
prologue would check every nth execution for types, rather than
every execution. Most times, it would just increment a counter.
Very highly optimized code could forego the checking and counting
entirely, assuming it had already learned all of the likely argument
type combinations. (Actually, every nth time it would change n
a little to avoid rhythmic problems.)
* Something like this might also be useful for trace scheduling.
Every now and then you execute an "instrumented" version of the
code that collects data on common execution patterns.
Any comments? Does anybody know of any systems that use dynamic
compilation? I know a couple of Smalltalks do it, and now
I'm told that MIT Scheme has a somewhat similar cache-with-
dependencies mechanism for variable lookups.
Does anybody have any opinions on the expected efficiency of such a system?
It seems to me that it could be quite good. It could also be advantageous
in that it would not optimize a lot of the code. In particular, it could
keep things in a more debuggable form than something that optimizes
more stupidly, without much performance penalty. (Especially since
frequently modified things will never get heaviliy optimized.)
I only have a few references on dynamic compilation, none of which go into
anything advanced. If you have others, please send them to me and I'll
pass them on to interested parties.
(Besides the ones in Andy Gordon's posting, there was "An Evaluation
of Throw-away Compiling" in Software Practice and Experience, vol. 13
(1983), pp. 241-249.)
[ NOTE: here are the citations from Andy Gordon's posting:
[1] A. D. Gordon, "How to Breed Hybrid Compiler/Interpreters",
Technical report ECS--LFCS--88--50, Laboratory for the
Foundations of Computer Science, Computer Science Dept.,
University of Edinburgh, Edinburgh, EH9 3JZ, Scotland.
April, 1988.
[2] P. J. Brown, "Throw-away compiling", Software P & E, 6,
pages 423--434, 1976.
[3] J.R. Low, "Automatic data structure selection: an example and
overview," CACM, 21(5), pages 376--385, May 1978.
[4] R. J. Dakin and P. C. Poole, "A mixed code approach", The Computer
Journal, 16(3), pages 219--222, 1973.
]
I have not gotten any responses indicating that dynamic compilation has
been used to control levels of optimization or to recompile when
optimizer assumptions are violated.
[ NOTE: after I posted this originally, I did find the two references
mentioned above, thanks to Greg Jaxon at U. of Illinois. ]
---------------------------------------
third posting:
---------------------------------------
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.
(That is, an array-of-integer will always contain only integers, but
you can't look at a particular point in the source code and tell what
class(es) an argument could belong to. So some objects are "statically"
typed in that their components don't change types, but the code is
not amenable to static type analysis -- you can always call a procedure
with any kind of argument you want. If types can be created at runtime,
then the set of possible types at many points in the code could be infinite.)
Now suppose we define a procedure 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 infrequently used 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.eecs.uic.edu
Box 4348 Chicago,IL 60680 wilson@uicbert.eecs.uic.edu (01/18/89)
Apologies to anybody who responded to my dynamic compilation posting and didn't get a response. Our site lost most of the incoming mail last week; please try again. (You might want to cc a copy to me as wilson@carcoar.stanford.edu, just to be sure I get it.) Thanks, Paul R. Wilson Human-Computer Interaction Laboratory lab ph.: (312) 413-0042 U. of Ill. at Chi. EECS Dept. (M/C 154) wilson@uicbert.eecs.uic.edu Box 4348 Chicago,IL 60680 (and/or wilson@carcoar.stanford.edu)