CMSC 838Y Paper Reviews

Skip down to paper 0: Joel Auslander, Matthai Philipose, Craig Chambers, Susan J. Eggers, and Brian N. Bershad. Fast, effective dynamic compilation. In SIGPLAN Conference on Programming Language Design and Implementation, pages 149-159, 1996. [ .html ]


Reviews for paper 0

Review from Bryan Payne <bdpayne@cs> at Wed Mar 5 22:32:54 EST 2003:

The idea for this paper is to compile some code at run-time in order to get 
more optimized code.  Since this is only useful if the time required for 
dynamic compilation is less than the speedup you get from it, this paper was 
concentrating on ways to get good speedups with minimal time spent on dynamic 
compilation.

My biggest complaint with the idea is that it requires the programmer to notate 
the code with additional information.  The authors spent a fair ammount of time 
arguing that this is a sort of necessary evil and saying that they tried to 
find a middle ground in order to provide minimal notation for maximal benefit.  
However, I feel that the extra notation alone makes this idea less practical.

Having said that, the idea is still quite interesting.  By precomiling / 
optimizing sections of code and simply leaving out the unknown variable values, 
the time required for dynamic compilation at run-time should be significantly 
reduced.  So, I like the idea, but feel that a little more work is required in 
order to make this more viable (i.e., reduce the burden on the programmers).

Review from Prashant Lamba<plamba@wam.umd.edu> at Wed Mar 5 23:47:52 EST 2003:

This paper gives the framework for the dynamic compilation.Rather than VCODE 
paper this paper explains pretty well what is dynamic  compilation and  how it 
is implemented in the system described in the paper.Authors have have defined 
the basis of the system in one statement as "One man's variable is another 
man's constant".In the system described as in paper has both static and a 
dynamic compiler.A static compiler produces the pre-compiled machine-code 
templates,whose instruction contains holes that will be filled in,set up code 
determines the value of run time constants.In sec 2 the paper explians the 
Programmer Annotations which are used to determine the parts of the code wich 
are to be dynamically compiled.The later part of the paper describes how to 
generate the Run time constants,set up code .It also explains the various 
factors contributing the quatilty if the dynamic complied code such as 
optimization of dynamic regions etc.In the end the code generation is explained 
where the static compiler generates the machine code.The stitcher as the name 
indicates does the job of stiching.The sticher is seperate from the cstatic 
compiler through a simple interface.
This paper describes pretty well the concept of dynamic compilation and its 
implemetation as compared to the VCODe papaer where the authors emphasise on 
the functionality of VCODE rather than how Dynamic compiltauion is achieved.

Review from Piyush Bhagat<piyushb@glue.umd.edu> at Thu Mar 6 00:18:19 EST 2003:

The paper is about dynamic compilation. It goes into detail of a dynamic 
compilation scheme as is suggested by the authors. The paper starts with 
underlining the importance of dynamic compilation over static compilation. The 
paper claims that the dynamic compilation scheme suggested by the authors is 
both fast and delivers high quality dynamically generated code. The paper says 
that traditional compilation does not optimize around invariant variables till 
run time, as their values are not known to it. These variables must be 
reinterpreted during each run time causing a lot of overhead. The paper then 
gives the details of its dynamic compilation scheme.
The scheme is a collection of both a static compiler and a dynamic compiler. 
The static compiler produces pre compiled machine code templates and space to 
be filled in by runtime constants. It also produces code to calculate the 
values of derived run time constants and directives for the dynamic compiler 
about how to produce executable code. The dynamic compiler just fills in the 
values of the runtime constants according to the directives. The key aspect of 
the scheme is that the programmer annotates to specify the regions of the code 
that are to be dynamically compiled, the variables that are to be treated 
constants during run time etc. This approach makes the scheme neither fully 
manual nor fully automatic. I think the manual annotation part may induce 
errors in the scheme. The paper then deals with computing derived run time 
constants and optimization. The paper lays down some requirements for 
optimization and says that the scheme suggested by the authors fulfills the 
requirements. After all these things the stitcher or the dynamic compiler has 
nothing much to do but run according to the directives of the static compiler. 
I think that the paper finally lives scope for further research on application 
of this scheme on object oriented languages and complete automation of the 
scheme by removing the programmer annotation part.                

Review from Piyush Bhagat<piyushb@glue.umd.edu> at Thu Mar 6 00:18:19 EST 2003:

The paper is about dynamic compilation. It goes into detail of a dynamic 
compilation scheme as is suggested by the authors. The paper starts with 
underlining the importance of dynamic compilation over static compilation. The 
paper claims that the dynamic compilation scheme suggested by the authors is 
both fast and delivers high quality dynamically generated code. The paper says 
that traditional compilation does not optimize around invariant variables till 
run time, as their values are not known to it. These variables must be 
reinterpreted during each run time causing a lot of overhead. The paper then 
gives the details of its dynamic compilation scheme.
The scheme is a collection of both a static compiler and a dynamic compiler. 
The static compiler produces pre compiled machine code templates and space to 
be filled in by runtime constants. It also produces code to calculate the 
values of derived run time constants and directives for the dynamic compiler 
about how to produce executable code. The dynamic compiler just fills in the 
values of the runtime constants according to the directives. The key aspect of 
the scheme is that the programmer annotates to specify the regions of the code 
that are to be dynamically compiled, the variables that are to be treated 
constants during run time etc. This approach makes the scheme neither fully 
manual nor fully automatic. I think the manual annotation part may induce 
errors in the scheme. The paper then deals with computing derived run time 
constants and optimization. The paper lays down some requirements for 
optimization and says that the scheme suggested by the authors fulfills the 
requirements. After all these things the stitcher or the dynamic compiler has 
nothing much to do but run according to the directives of the static compiler. 
I think that the paper finally lives scope for further research on application 
of this scheme on object oriented languages and complete automation of the 
scheme by removing the programmer annotation part.                

Review from Nathaniel Waisbrot <waisbrot@cs> at Thu Mar 6 11:18:42 EST 2003:

	Auslander et al.'s dynamic compiler attempts to apply compiler optimizations 
at run-time.  There are a number of optimization dealing with constant values.  
The authors point out that a program will frequently have some values which are 
constant over the execution of a program, but are not known at compile time.  A 
simple example would be configuration settings read from a file or the command 
line.  Their system allows the programmer to annotate which values will be 
constant at run-time, and they compile the code with those values as unknown 
constants.  At run time, the dynamic compiler just fills in the blanks.
	Like VCODE, this is pretty much one clever trick which gives them a lot of 
milage.  Having to use annotations is disappointing, but it does illustrate, as 
they point out, that their system can be used to optimize values which are 
constant in one area of the program, but change before or afterwards.  They 
mentioned that a dynamic region could be keyed to a constant, which is a nice 
idea.  (I imagine every function in a program claiming that variables which 
don't change locally are keyed run-time constants -- the running program 
contains thousands of optimized copies of each function, and nearly every call 
needs to take a page fault.  So much for trusting the programmer!)  The lack of 
safety is too bad, but they're probably right that it's not such a big deal.  
Once they get the system automated, this could provide some easy speed boosts.

Review from Brian K <bjkrz@cs> at Thu Mar 6 11:31:04 EST 2003:

This paper focussed on runtime dynamic compilations ability to
optimize code based on runtime constants that are not available to static
compilers.  The system discussed is an efficient hybrid static/dynamic 
compiler.
Loading such a program requires first the dynamic compiler to calculate values
based on learned runtime constants, after which a 'sticher' runs through object 

code 'templates' and inserts the correct values.   Most optimizations are taken
directly from static compilation techniques- in this sense teh author's did not
try to reinvent the wheel.  Through modification of existing algorithms they 
can treat runtime constants essentially as real constants (with some caveats), 
adding on  some bookkeeping to allow for runtime patchup code.  So, if 
x= folded runtime constant + y, 
then the static algorithms can calculate what the folding should have been,
and the stitcher can actually do the runtime folding and insert it in the code.
Pretty neet.  The system also allows for dynamic loop unrolling based on 
constants-
though this decision is left to the programmer as the overhead of dynamically
unrolling a loop could be inefficient for a rarely reached loop.  The paper
spends some time on how it extrapolates what values are in fact constants based
on declared constant values- though I think this analysis largely mirrors the 
static
case.   Sppedups of 1.2-1.8 are given- modest but nice for relatively little 
effort on the part of the programmer.  Pretty cool.

Review from Jeff Odom <jodom@cs.umd.edu> at Thu Mar 6 11:48:56 EST 2003:

The Auslander et al paper describes a framework for runtime optimization.  
Here, the major idea is that invariants which cannot be determined until 
runtime must generally be stored in memory, thus requiring loads each time that 
invariant is referenced.  In practice, we would like to be able to treat each 
invariant as what it is - a constant - and not require memory accesses.  
Additionally, because they are constant, we would like to be able to perform 
constant folding/propagation optimizations.  The system the authors propose 
requires minimal effort on the programmer, who primarily simply annotates which 
variables are invariants.  Their system then automatically finds additional 
invariants by what amounts to be a type analysis (you could treat the 
annotations as type-qualifiers).  Once this is performed, the compiler 
generates template code whereby each load of an invariant is replaced by 
instructions that set a register to some constant value.  Initially this value 
is some default which will be replaced later by the runtime invariant.  The 
compiler also generates code to "fill-in" these default values at runtime, 
which is executed only once for each time a region that uses an invariant is 
entered.

The only negative aspect to this system is its performance.  There seems to be 
a large overhead imposed by the set-up and stitcher, forcing high breakeven 
points.  This seems to indicate that such a system may not be useful for 
short-lived programs, but longer running applications (such as servers) would 
most likely benefit from this type of optimization.  The authors also note that 
the set-up and stitcher code sections could be combined to decrease the 
overhead, so the utility of such a system could be improved.

Review from Mujtaba Ali <mujtaba@bitsmart.com> at Thu Mar 6 12:32:32 EST 2003:

I found the dynamic compilation approach mentioned in this paper very 
appealing, primarily due to its usefulness in a general-purpose setting.  The 
scheme detailed here is highly concerned with practicality and usability.  In 
order to make dynamic compilation practical (fast and effective), this scheme 
takes a great amount of assistance from static compilation, producing templates 
for speed, yet still performing effective optimizations.  And usability is 
provided in the sense that the process is not completely manual as VCODE is 
and, unlike VCODE, the programmer does not have to be an expert on run-time 
optimization techniques.  However, there is one catch; the programmer must 
manually annotate sections of code that he/she believes will benefit from 
dynamic compilation.  Such an approach is consistent with what we saw in 
dynamic updating - with a little help (in form of domain-specific input) from 
the user, you can avoid a lot of thorny issues. 

Opting to go with a partially manual approach still introduces a couple of 
undesirable side effects.  Primarily, code maintenance and debugging are 
difficult.  Even though this approach is more general than VCODE, it should 
still only be applied in very critical situations.

Both VCODE and this scheme increase memory footprint, but it is unclear how to 
avoid this problem.

I would say that the dynamic component of this scheme is not anything special 
and the static component really steals the show.  I also found the keyed 
approach especially novel and practical.  As far as the paper itself, the 
diagrams and figures were invaluable and the authors successfully imparted 
their algorithms.

Review from Yuan Yuan<yuanyuan@cs> at Thu Mar 6 12:34:57 EST 2003:

This paper constructs a dynamic compilation framework to achieve high-quality 
dynamically compiled code and low run-time compilation overhead. The main idea 
is based on optimizations of the values of invariant data computed at run-time. 
By annotating the dynamically compiling regions by programmer and mechanisms in 
compiler to use these annotations, they could limit the run-time overhead 
caused by dynamic compile.

The compiler designed here includes both a static and a dynamic compiler 
(Stitcher). The static part is used to identify run-time constant, generate 
setup code and template to make Stitcher directive, then do standard 
optimization. With the preparation of static compiler, dynamic one only follows 
the derivatives to initiate the templates and fill the holes with run-time 
constants. 

Authors argue this approach for dynamic compilation is efficient though the 
experimental assessment. And this approach is a well trade-off between 
automatic generating code and generality. Although it need intermediate storage 
for templates, it provide a way to do optimization in the static complier. 


Generated: Thu Mar 6 15:39:24 EST 2003 by mwh


mwh@cs.umd.edu