The advantages of the object layout described here are most apparent for a full class header. The kind of type lattice shown in Figure 8 is uncommon for abstract types, but similar hierarchies are frequent in a system with separate subtyping and inheritance, as shown earlier in Figure 1. Merge optimizations like that in Section 3.3 are correspondingly more important, and are used by the bidirectional layout to produce compact class headers.
In Theta, a class implements either a single type or none; it inherits either from a single superclass or from none. Classes that do not implement a type are useful because they can be inherited without fear of damaging existing objects. They can also be used for private data structures within another implementation.
There are several cases to be considered when constructing class headers, and the following sections will enumerate them and provide the construction rules.
The simplest case to consider is a class that does not inherit from any superclass, shown in Rule 2. This rule optimizes the header of a non-inheriting class C by making its class dispatch vector compatible with the type it implements, T.
Rule 2: A non-inheriting class
The horizontal abutting
of the two boxes, with 
on the right, indicates that the methods
of C
that are not found in T (i.e., the private methods)
are prepended to the
last type dispatch vector of T.
The indices of the T methods do not
change; the methods of C are added with negative indices starting
from -1.
Note that if T has only single supertypes above it in the hierarchy (a simple hierarchy), then the whole class header for C will consume only a single word per object.
If a class does not inherit from a superclass or implement an abstract type, Rule 2 also applies. The layout for T is considered to be empty, so the dispatch header of such a class contains a single dispatch vector with only negatively-indexed methods.
The key to the efficiency of the bidirectional layout is the merging of type and class headers in type/class lattices, which is described by Rule 3. This rule computes the layout of a class C that implements type T and inherits from class Cs. The header of Cs must contain an exposed S header that T is compatible with. The C header is formed by extending the Cs class dispatch vector backward, and the embedded S header forward. The backward extension of the Cs class dispatch vector makes the layout compatible with C, and the forward extension makes it compatible with T. Both extensions can affect the same dispatch vector, which is made possible because the backward extension of the class dispatch vector cannot collide with the forward extension of S.
Rule 3: Merging type headers into class headers
As in the merge cases of Figure 9, the supertype S must either be on a simple supertype chain above T, or, if it is exposed at the start of (i.e., x is empty), on a primary supertype chain above T. Thus, Rule 3 is analogous to the earlier Rule M2.
Rule 4 guarantees that the class header construction rules are complete. In the rule, C is a class that implements the abstract type T, and inherits from the class Cs. The header for C is formed by concatenating the headers of T and Cs, without merging. The methods of C that are not already in the class dispatch vector of Cs are prepended to the negative portion of the class dispatch vector. Rule 4 corresponds to merge Rule M3 and the simple type header layout policy of Figure 7: like a C++ layout, it tends to make the object dispatch overhead larger with each level of hierarchy.
Rule 4: Default class header rule
When Rule 4 is applied to a class C
that does not implement an
abstract type, the
portion of the layout is considered to be
empty. To produce the class header for C, it just prepends the new
C methods.
When T is a supertype of the type that Cs
implements, the Theta
implementation performs an optimization not shown in the diagram.
Since is already embedded in
the Cs header, there is no need to concatenate
to the Cs header to
create the C header.
The new C methods
are simply prepended to the class dispatch vector.
When Rule 3 applies, its advantage over Rule 4 is that it does not increase the size of the dispatch header with each level of hierarchy. Type/class lattices like those depicted in Figure 1 require only rules 1, 2, and 3, and all applications of rule 1 use merge rules M1 and M2. None of these rules cause the header to grow, so the class headers of all classes in a simple type/class lattice occupy only a single word. In fact, only a single word of dispatch information is required for a class as long as the following two conditions are met:
Negative method indices allow smaller headers. Without them, reasonable merge schemes can be defined [Mye94], but the size of headers in a type/class lattice is two words rather than one. The two dispatch vectors correspond to the negative and non-negative portions of the class dispatch vector.
Rules 2 through 4 are both complete and correct, which again can be shown inductively. For completeness, consider all possible classes. If the class does not implement a type, its header is defined by Rule 4. If the class does not inherit from a superclass, its header is defined by Rule 2. If the class both implements a type and inherits from a class, its header is defined by either Rule 3 or Rule 4, depending on whether merging is possible. Therefore, all class headers are constructible.
For correctness, embedded type and class headers must be found at known offsets from the class dispatch vector. Rules 2 and 4 clearly preserve this property. Rule 3 operates almost identically to merge rule M2, and the correctness arguments from Section 3.3.2 again suffice.
Andrew C. Myers. Bidirectional Object Layout for Separate Compilation.
Proceedings of OOPSLA '95, pp. 124-139.
Copyright © 1995 Association for Computing Machinery
