HAVE: optimizing compiler for O-O programs; NEED: well-written OO programs

jdean@pysht.cs.washington.edu (Jeffrey Dean)
Thu, 31 Aug 1995 19:01:06 GMT

          From comp.compilers

Related articles
HAVE: optimizing compiler for O-O programs; NEED: well-written OO prog jdean@pysht.cs.washington.edu (1995-08-31)
| List of all articles for this month |

Newsgroups: comp.compilers
From: jdean@pysht.cs.washington.edu (Jeffrey Dean)
Keywords: OOP, optimize, C++, modula, question
Organization: University of Washington
Date: Thu, 31 Aug 1995 19:01:06 GMT

WANTED: C++ and Modula-3 programs written in an object-oriented style
                  to serve as benchmarks


The Cecil group at the University of Washington has been conducting
research on effective techniques for optimizing object-oriented
programs. We have developed and extended several optimization
techniques for reducing the overhead of dynamically-dispatched
messages (e.g. virtual function calls in C++), which are described in
recent PLDI, ECOOP, and ICSE papers and in an upcoming OOPSLA paper.
These techniques include:

    o Class hierarchy analysis. By allowing the compiler to examine the
        inheritance hierarchy of the whole program, the compiler can
        automatically achieve the effects of static binding when no
        overriding methods are present. This provides a superset of the
        benefits possible by manually making a function 'non-virtual', and
        does so automatically.

    o Selective specialization. By combining class hierarchy analysis with
        profile data to identify program hot spots, it is possible to
        identify when it is beneficial to compile multiple versions of a
        single source routine, each specialized to a different set of receiver
        classes or argument classes.

    o Profile-guided receiver class prediction. Using the observation
        that one or a handful of classes are most common at a particular
        dynamically-dispatched message send, it is possible to insert explicit
        tests for the most common classes of objects, and to optimize the call
        site for these common classes. For example:

                Shape* shape = ...;

        If squares turn out to be more common at this call site, our compiler will
        automatically transform this code into the following:

                Shape* shape = ...;
                if (class_of(shape) == Square_class) {
     ... inlined version of Square::draw() ...
                } else {
                      shape->draw(); // Original code to handle shape not being a square

We've implemented these techniques, along with other, more traditional
optimizations, in the context of our Vortex compiler infrastructure.
Initially, Vortex compiled only programs written in Cecil, a purely
object-oriented language. These optimization techniques have been
shown to be effective at improving the performance of Cecil programs,
including the Vortex compiler itself, which is about 60,000 lines of
Cecil code.

We are now in the final stages of connecting C++ and Modula-3 front
ends onto the Vortex compiler, so that we can explore the
effectiveness of these techniques on hybrid, statically-typed


We are now looking for programs that make heavy use of object-oriented
features to serve as benchmarks for assessing the effectiveness of our
techniques on C++ and Modula-3 programs. In particular, we are
looking for C++ programs that make heavy use of inheritance and
virtual functions, and for Modula-3 programs that make heavy use of
objects and inheritance.

Another of our goals is to build a suite of well-written, object-oriented
benchmark programs that we and other researchers can use to evaluate
optimization techniques and to guide the development of new optimizations.

For these purposes, we're looking for C++ and Modula-3 programs that run
on UNIX systems (ideally Suns, although we're willing to do some
porting). We need source code for the programs. Ideally, the code
would be in the public domain or under GNU copyleft, so that we could
make the code available to other researchers who want to duplicate our
results or use the programs for other purposes. However, if you have
proprietary source code, we're willing to keep it that way.


Fame, glory, and our undying thanks. And we might be able to provide you
with a program executable that's faster than the one you're able to
get out of your current compiler.


If you have one or more programs that you think meet our criteria,
send me e-mail at jdean@cs.washington.edu.

If you want more information about our Cecil, Vortex, or our
optimization techniques, visit the Cecil Group's WWW page:


(Most of the information on the WWW page is also available via
anonymous ftp from cs.washington.edu in the directory /pub/chambers).

If you have any questions, please don't hesitate to ask them.

-- Jeff

Jeffrey Dean (jdean@cs.washington.edu) Graduate Student, Cecil Project
Dept. of Computer Science & Engineering University of Washington

Post a followup to this message

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