Programming Techniques, Tools and Languages Group

C++ Open Method Compiler

Overview

multiple dispatch: an abstraction mechanism that invokes the most specific implementation based on the dynamic information of multiple arguments.

open classes: a mechanism that allows classes to be extended retroactively.

Design Goals

To warrant an increased language complexity, we define the following goals for open-methods:

  1. Better performance than workaround techniques
  2. Smaller memory footprint than workaround techniques
  3. Dispatch rules should generalize overload and virtual dispatch semantics
  4. Full support for C++'s object model, including virtual and repeated inheritance
  5. Exception free (e.g., important for embedded systems)
  6. Extensible mechanism that can cope with dynamic loading and linking
  7. Zero-overhead for orthogonal language features

Example

The following figure shows a part of a realistic hierarchy of image formats:

A host of concrete image formats such as RGB24, JPEG, and planar YUY2 will be represented by further derivations. The optimal conversion algorithm must be chosen based on a source-target pair of formats. The following table lists the algorithm that best handle specific source-target pairs.

Now the conversion can be simply defined by using the source and destination formats.

 
    bool convert(virtual const RGB&  src, virtual RGB&  dst); // uses DD 
    bool convert(virtual const RGB&  src, virtual YUV&  dst); // uses CC 
    bool convert(virtual const YUV&  src, virtual RGB&  dst); // uses CC 
    bool convert(virtual const YUV2& src, virtual UYVY& dst); // uses 2B 
    // ... 
    

Without open-methods (or multi-methods), the programmer would be required to use the visitor pattern (double dispatch), pre-processors, or multi-method library solutions.

The object model

In order to achieve dispatch time that only depends on the number of virtual arguments, we extended the Itanium object model for C++. The following graph shows the modifications (grey entries) to the runtime data structure. The class hierarchy in the example uses repeated inheritance (D derives from A twice).

Implementation

The C++ open method compiler extends the EDG C++ compiler's lowering pass that generates C code. In addition, the compiler extracts data on class hierarchies and open-method declarations from each translation unit and stores them in separate files. A pre-linker synthesizes this data from all translation units, checks for dispatch ambiguities, and generates the dispatch table layout.

Performance Results

In our test setting, we randomly intersect two objects out of a pool of 20 different classes. This gives 400 possible dispatch combination, for which we implemented 40 (empty) overriders.

The following table compares the generated code with alternative implementations in terms of executable size and execution speed. The results were obtained by compiling the C++/lowered C code with g++ 4.1 (Linux, Pentium-D) and gcc 4.0.1 (OSX, Core2Duo) with optimization level set to -O3. The results for the C++ open method compiler are shown with yellow background.

Single virtual dispatch measures the performance of a single isolated virtual function call to one of the 20 objects. The multi-method (multi-methods have to be declared in class) and open-method prototype are hand crafted implementations that approximate automatic lowering of C++ code. We initially developed them to assess performance trade-offs of different design decisions.

Approach Size (bytes) Cycles/Loop Cycles/Loop
Linux Pentium-D Core2Duo
Simple Virtual function n/a 75 55
Multi-methods prototype 42 972 78 60
Open-methods prototype 40 636 82 63
Open-method Compiler 42 504 82 64
Double Cpp 34 812 120 82
Visitor 38 236 132 82
Chinese Remainders prototype n/a 175 103
Cmm (constant time) 155 344 415 239
Cmm 155 056 1 320 772
Loki Library 75 520 3 670 2 238

Publications

Presentation

Poster


Upcoming Events




Share This Article




Headlines

About Us | Parasol Lab | Computer Science and Engineering | ©2010 Texas A&M University