Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!mit-eddie!uw-beaver!Teknowledge.COM!polya!carcoar!wilson
From: wilson@carcoar.Stanford.EDU (Paul Wilson)
Newsgroups: comp.arch
Subject: multilevel dynamic compilation [was Re: Self-modifying code]
Summary: does anybody really defer compilation until nth execution?
Keywords: dynamic compilation, execution counts, levels of optimization
Message-ID: <12367@polya.Stanford.EDU>
Date: 11 Oct 89 16:08:40 GMT
References: <1080@mipos3.intel.com> <4415@bd.sei.cmu.edu>
Sender: news@polya.Stanford.EDU
Reply-To: wilson@carcoar.Stanford.EDU (Paul Wilson)
Organization: Stanford University
Lines: 57

In article <4415@bd.sei.cmu.edu> firth@sei.cmu.edu (Robert Firth) writes:
>Finally, one very powerful technique is used in some implementations
>of prototyping languages.  Typically, such languages are interpreted,
>so each statement in 'Object Logo Plus', or whatever, is turned into
>a data structure that is crawled over by an interpreter.
>
>The trick is this: keep track of how often a code fragment (procedure,
>method, or whatever) is modified, and how often it is executed.  When
>a certain stability threshold is reached, compile the sucker into true
>machine code, and have all subsequent executions be direct rather than
>interpreted.  Over a prototyping session of an hour or two, the user
>will observe a speedup of 2x to 20x, as the more stable and heavily used
>parts of the program get converted gradually into machine code.
>
>Hope that helps.

Does anybody actually do this?  It seems the obvious thing to do, but
I don't know of anybody who does it.  All of the dynamic compilation
systems I know of compile things the very first time they're executed,
and don't recompile unless something gets redefined.

It seems to me that in a very high-performance system you want to do
this, recompiling with a higher level of optimization when an execution
count hits a threshold.  This will heuristically improve your
response time/ execution time tradeoff in an interactive programming
environment.  (And also your space/time tradeoffs in the generated
code.)

I would be *very* interested in anybody's experiences with such a
system, especially any statistics on the frequencies of execution
of different procedures/methods.  (e.g., does a 90/10 rule apply,
or an 80/20, or what?  What does the curve look like?)

I'm interested in preventing unnecessary compilation and optimization
of things that aren't executed very frequently.  This is not just
to avoid useless compiler work, but to keep the code transparently
debuggable whenever possible.

(Yes, I know you can often debug optimized code by recording the
optimizations and backward-mapping them at debug time.  But sometimes
you can't, and it's always more work for the compiler and debugger
writers.  I'm looking at two levels of optimized code -- easily
source-mappable "transparent" optimizations, and hairy "opaque"
optimizations for important well-debugged time-critical code.
Any info to evaluate the tradeoffs would be of interest.)


   -- Paul

Paul R. Wilson                         
Software Systems Laboratory               lab ph.: (312) 996-9216
U. of Illin. at C. EECS Dept. (M/C 154)   wilson@carcoar.stanford.edu
Box 4348   Chicago,IL 60680 
Paul R. Wilson                         
Software Systems Laboratory               lab ph.: (312) 996-9216
U. of Illin. at C. EECS Dept. (M/C 154)   wilson@carcoar.stanford.edu
Box 4348   Chicago,IL 60680