Re: looking for information about profiling of OO languages

Francois-Xavier Josset (Francois-Xavier.Josset@irisa.fr) wrote:
: I am looking for informations concerning profiling of object-oriented
: languages (in particular, Java),


There has been quite a bit of work in this area. In particular, for
object-oriented languages, a new form of profile information that
measures a histogram of receiver classes that appear at each method
invocation can be used to optimize method invocations. For example,
consider a message send to draw a shape:


    shape.draw()


This message send might invoke a number of different methods (for
example, a version for the Circle class, a version for the Square
class, etc.). However, by profiling the actual classes that appear at
this call site, compilers receive useful information about how this
call site is used in practice (essentially a histogram of classes at
this call site):


    Rectangle 1000
    Circle 10
    Square 10




This information is different than traditional profile information,
which usually measures just execution frequencies of basic blocks or
edges. Using this histogram information, the call site can be
optimized as follows:


    if (shape.Class == Rectangle) {
        ... inlined version of Rectangle::draw ...
    } else {
        shape.draw(); // Full message send for else case
    }


This is quite a powerful technique, because it not only allow the
direct overhead of the message send to be eliminated, but also allows
inlining. Because decomposition of programs into many small methods
is a common programming idiom in object-oriented languages, this can
have quite substantial performance benefits.


This idea was originally proposed by both Calder & Grunwald (who
presented simulation results for C++) and by Hoelzle & Ungar, who
implemented it in the Self-93 system, where it forms the basis of many
of the optimizations performed by that compiler. It was subsequently
used in the Vortex compiler for Cecil, Java, C++ and Modula-3, where
it was extended so that the histogram was separated into separate
histograms for different calling contexts (based on the chain of
callers traversed in order to reach a particular routine). The Vortex
compiler also uses this kind of profile information to guide its code
specialization algorithm.


For more info, see the following papers:


o Urs Hoelzle and David Ungar. "Optimizing Dynamically-Dispatched
Calls with Run-Time Type Feedback", in Proceedings of the ACM SIGPLAN
`94 Conference on Programming Language Design and Implementation
(PLDI'94), Orlando, FL, June 1994.


    http://www.cs.ucsb.edu/oocsb/papers/type-feedback.html


o Brad Calder and Dirk Grunwald, Reducing Indirect Function Call
Overhead In C++ Programs, in Proceedings of the 21st Symposium on
Principles of Programming Languages (POPL'94), pages 397-408, January
1994.


    http://www-cse.ucsd.edu/~calder/papers/POPL-94.ps.Z


o David Grove, Jeffrey Dean, Charles Garrett, and Craig Chambers.
"Profile-Guided Receiver Class Prediction", in Proceedings of 1995
Conference on Object-Oriented Programming Systems, Languages and
Applications (OOPSLA'95), Austin, TX, October, 1995.


    http://www.cs.washington.edu/research/projects/cecil/www/Papers/profiles.html


o Jeffrey Dean, Craig Chambers, and David Grove. "Selective
Specialization for Object-Oriented Languages", in Proceedings of 1995
Programming Language Design and Implementation, La Jolla, CA, June,
1995.


    http://www.cs.washington.edu/research/projects/cecil/www/Papers/specialize-pldi.html


These four papers are probably the first ones that I would read.
Other papers that apply profile-guided optimizations and/or compare it
with various other optimization techniques include:


>From http://www.cs.ucsb.edu/oocsb/papers.shtml:


    Aigner and Hoelzle. "Eliminating Virtual Function Calls in C++
    Programs" (ECOOP'96)


    Agesen and Hoelzle, "Type Feedback vs. Concrete Type Analysis: A
    Comparison of Optimization Techniques for Object-Oriented Languages"
    (OOPSLA '95).


    Ungar and Hoelzle. "Reconciling Responsiveness with Performance in Pure
    Object-Oriented Languages" (TOPLAS 1996)


From
http://www.cs.washington.edu/research/projects/cecil/www/Papers/papers.html:


    Dean, DeFouw, Grove, Litvinov, and Chambers. "Vortex: An Optimizing
    Compiler for Object-Oriented Languages" (OOPSLA'96).


    Chambers, Dean, and Grove. "Whole-Program Optimization of
    Object-Oriented Languages" (UW technical report, 1996).


In addition to these more specialized forms of profiling, more traditional
profiling information, such as basic block execution frequencies, also
helps with many phases of optimizing object-oriented languages, just as it
aids in the compilation of more traditional non-object-oriented languages.


-- Jeff


------------------------------------------------------------------------------
Jeffrey Dean (jdean@pa.dec.com) Member of Research Staff
Western Research Laboratory Digital Equipment Corporation
                                      http://www.research.digital.com/people/jdean
--

Return to the comp.compilers page.
Search the comp.compilers archives again.