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