Multiple inheritance: subtyping tests, dispatching and object layout.

Table of contents:

• Abstract
• Database of class hierarchies used in our experiments

    The object oriented (OO) paradigm has become the norm for software development. OO languages, such as C++, JAVA, EIFFEL, and SMALLTALK, are used in almost every software project. The OO programming style, and the languages that enable it, have acquired an aura of respectability. OO programming promotes reusability, extendibility, reliability, and portability. All these blessings come however at a cost of runtime efficiency. Better understanding of this cost, and finding ways to reduce it, were the subject of my thesis.

This thesis presents our contributions to the following three fundamental problems in the runtime environment of OO languages: subtyping tests, message dispatching (both single and multiple dispatching), and object layout. It is important to note that although the problems take variations in different languages, these variations are minor in the implementation of these languages. The results will therefore be of general interest, and applicable to many different languages.

Surprisingly, we use our message dispatching techniques in designing the best algorithm for deciding isomorphism of simple types, i.e., whether two non-recursive types using product- and function-type constructors, are isomorphic under the axioms of commutative and associative products, and currying and distributivity of functions over products. We show that this problem can be solved in O(n log² n) time and O(n) space, where n is the input size. This result improves upon the O(n² log n) time and O(n²) space bounds of the best previous algorithm. We also describe an O(n) time algorithm for the linear isomorphism problem, which does not include the distributive axiom, thereby improving upon the O(n log n) time of the best previous algorithm for this problem.

The above contributions were published in five conference papers, two of which were also accepted to a journal.

Database of class hierarchies

• A. Krall, J. Vitek, and R. N. Horspool. Efficient type inclusion tests. In Proceedings of the 12th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 142–157, Atlanta, Georgia, Oct. 5-9 1997. OOPSLA’97, Acm SIGPLAN Notices 32(10) Oct. 1997.

 
• A. Krall, J. Vitek, and R. N. Horspool. Near optimal hierarchical encoding of types. In Aksit and Matsuoka [2], pages 128–145.

• Click here to dowload the final version of our database (zip) - 286 kb.
• The dipatching files (lisp-like lists of classes having lists of member functions). See the paper Minimizing Row Displacement Dispatch Tables for a high-level description of the benchmarks.