Introduction

Existing schemes for object memory layout and method dispatch in statically typed languages with multiple inheritance assume the use of multiple inheritance in its full generality. These schemes incur high per-object space overhead [Str87], extra dispatch cost, or a global type analysis phase [DMSV89].

These problems are addressed by the bidirectional object layout, a new scheme suitable for separately-compiled languages with multiple inheritance. The primary advantage of this object layout is that it supports faster method dispatch than current C++ implementations [ES90], while reducing the amount of per-object dispatch information. This paper presents precise rules for constructing bidirectional layouts and explains the dispatch code needed for typical RISC architectures.

Bidirectional object layouts can be efficiently computed because the construction rules use only local knowledge of the type hierarchy to compact the dispatch information. By requiring only local analysis, this technique can be used with separate compilation since new classes added to the system cannot invalidate the layout of existing classes. Therefore, the bidirectional layout scheme scales better to large-scale software development than other compact layout schemes requiring a global type analysis phase.

A separate contribution of this paper is an efficient implementation of method signature refinement: a type may compatibly modify the argument and return types of a method derived from its supertypes, in accordance with the usual subtyping rules [Car84]. This feature is regrettably missing from other statically compiled languages like C++ or Modula-3 [Nel91]. The technique described here allows a class to refine superclass method signatures yet retain fast method dispatch.

The bidirectional object layout has been implemented for the programming language Theta [Mye94][LCD+94][DGLM95], a separately-compiled, statically-typed language which separates subtyping and inheritance. Theta allows a class to have any number of explicitly declared abstract supertypes, but only a single concrete superclass. This policy results from observations about the three common uses of multiple inheritance in programs, which are exploited by the bidirectional layout to generate more compact layouts:

subtyping: An abstract type, or interface, combines several existing interfaces and extends them. The abstract type is a subtype, and the extended interfaces are its supertypes. Elsewhere, this use is sometimes called ``interface inheritance'' among ``abstract classes''.
abstraction: An implementation (a class) is isolated from the interface it implements, providing separate hierarchies for inheritance and subtyping. As a result, a type need not expose implementation details for subtype implementations to inherit them.
inheritance: A new implementation is formed by combining and extending existing implementations. The new implementation is a subclass, and the extended implementations are its superclasses. In addition to method code, a class contains instance variables and private methods that are not accessible outside the class and its subclasses. In this paper, the term ``inheritance'' is used exclusively to mean implementation inheritance.

Figure 1: A common kind of hierarchy

The bidirectional layout supports the complex abstract-type/class hierarchy shown in Figure 1 as efficiently as single-inheritance classes in C++. This common kind of hierarchy has only the subtyping and abstraction uses of multiple inheritance. In the figure, the C_i are classes, and the T_i are abstract types. Arrows are used to denote the relations ``is a subtype of'', ``implements'', and ``inherits from'', depending on whether the two related entities are two abstract types, a class and an abstract type, or two classes. For example, T₁ is the supertype of T₂, and C₃ implements T₃. Such hierarchies are common, because they provide a layer of abstraction that separates interface and implementation.

Although subtyping and inheritance are separate, they often develop in parallel. Separate hierarchies allow us to add new implementations of any of the types in the ladder T₁, T₂, ..., without being forced to inherit from existing classes. On the other hand, an implementation of one of these types is often useful in constructing an implementation of a subtype (either direct or indirect), so inheritance often roughly mirrors the subtype hierarchy. For lack of a better technique, C++ programmers use true multiple inheritance and other inefficient idioms to achieve this same separation.

The bidirectional layout does better than current schemes because it implements subtyping and abstraction differently from true inheritance. It specifically optimizes lattice-like hierarchies like the one shown in Figure 1, where the types that a class and a superclass implement are in a parallel supertype relationship. Even with the use of true multiple inheritance, the bidirectional layout never imposes a penalty compared to current C++ implementations.

As in current C++ implementations, the layout of a class is determined using only information about that class and the hierarchy above it, with the result that new types and classes added to the system do not invalidate existing layouts. Changes to classes only affect their subclasses, and changes to types only affect their subtypes and the classes that implement the subtypes. Note that the supertype relation must be explicitly declared rather than being implicitly inferred from method signatures.

Next: Bidirectional Layout Up: Bidirectional Object Layout for Previous: Bidirectional Object Layout for