The dispatch header rule of Section 3.1 works correctly but sometimes wastes space. For example, consider the type lattice shown in Figure 8. The leftmost supertype at each branch is arbitrarily considered to be primary, a convention that is followed throughout. The figure demonstrates the successive application of the rule in Section 3.1, producing the T6 layout shown, a three-word dispatch header. Obviously, the first two dispatch vectors are compatible and can be merged, reducing the per-object overhead. Unfortunately, the simple type rule does not allow this merge.
Figure 8: Inefficient dispatch header
The compatibility arises because the layouts for T4 and T5 contain a common T3 piece, and can be merged. T3 is a secondary supertype of T4 , and is exposed in the T4 layout. Since T3 is in a single-supertype chain above T5, the T5 layout requires no more words of dispatch header space than does T3's.
Figure 9: The two merge cases for <H
The fact that the T5 header can be merged into the T4 header at some offset is expressed by the <H predicate: T5 <H T4. Figure 9 provides the definition of <H. Given a type T and an arbitrary layout L, it shows the two cases in which the T header can be merged into L. The result of the merge is compatible with L, and has the T header embedded within it. In the figure, the blocks labeled w, x, and y represent arbitrary pieces of dispatch header, possibly including multiple dispatch vectors. The block labeled m represents a part of a dispatch vector. These conventions will be followed throughout.
The first way to satisfy 
<H L
is if T has a supertype S whose header is exactly
the same size, and which is exposed in L so that
can be merged into the same place. For 
to be exposed in
L means that nothing is appended to the end of its dispatch vectors
in that layout, so that the block labeled m
(the dispatch vector entries for
methods of T that are not methods of S) has nothing
to collide with. Then, since
is compatible with
,
the merge result is compatible with L. In order for the size
of the T and S headers to be the same,
T and all its supertypes that are
subtypes of S must have only one supertype. In other words, there is a
simple chain of supertypes leading up to S.
The second way to satisfy
<H L is to expose the header of
S at the beginning of L,
and embed it at the end
of . Since
is
exposed at the beginning of L, and nothing is appended to its
dispatch vectors, there is nothing for the w portion of
to
collide with, and the two layouts can be merged.
In order for
to
be located at the end of
,
T and
all its supertypes that are subtypes of S
must lie on a primary
supertype chain, since, as shown later,
primary supertypes are always aligned with the
last dispatch vector in the type header. There may be branches in the supertype
structure over T,
which produces the w portion of the layout. Note
that the dispatch vectors of T
that are shared with the embedded
header for S
may have methods appended to them, which is why w
extends to the right of
.
Andrew C. Myers. Bidirectional Object Layout for Separate Compilation.
Proceedings of OOPSLA '95, pp. 124-139.
Copyright © 1995 Association for Computing Machinery