This section describes method dispatch and the layout of dispatch vectors. A method call is implemented by fetching an element of the current dispatch vector, at a method index determined from the statically declared type of the object. In the Theta implementation, the dispatch vector contains pointers to method code, leading to the usual three-instruction assembly-language dispatch sequence for the MIPS architecture (most RISC architectures are similar), shown in Figure 5.
ld t1, 0(a0) ; load dispatch vector
ld t9, (i * wordsize)(t1) ; code pointer
jalr ra, t9 ; jump to method
In this code sample, the register "a0" contains the object pointer. The value i is the method index. For any type T and method M of that type, a method index i identifies the proper offset within the dispatch vector. For example, in Figure 4, the method index of the method b in type B is 2.
Method indices are densely packed, which is desirable because dispatch vector space is used efficiently, yielding good cache performance. The indices of the n methods in a type dispatch vector are in the range 0...n-1. In class dispatch vectors, some method indices are negative, and indices are in the range -m...n-1, for some m and n. For example, in Figure 4, m=2 and n=3 for the class CB. The use of negative method indices provides important flexibility in constructing header layouts; the reason for this will become clear later.
A type dispatch vector contains all the methods for types in a supertype chain: a series of types T1...Tn, where
i < j implies Ti is a supertype of TjThe first entries in the dispatch vector are for T1, then for T2, and so on. This ordering ensures that a subtype dispatch vector is compatible with any supertype in the chain. For example, the methods of the types T1...T3 in Figure 1 could be placed in one dispatch vector, in that order. Methods are not duplicated in the dispatch vector, so the Tj portion of the vector contains no methods that are derived from Ti, where i < j. Therefore, the layout of the dispatch vector is uniquely defined by the sequence of types T1...Tn.
For a subtype dispatch vector to be compatible with a supertype dispatch vector, the supertype method indices must correspond to the same methods as in the subtype. This condition implies that the supertype dispatch vector must be embedded exactly at the start of the subtype vector, since any offset would require remapping its method indices.
The non-negative indices in a class dispatch vector are arranged as in a type dispatch vector. The negative indices contain methods for a series of classes C1...Cn, where Ci+1 inherits directly from Ci. As in the non-negative portion, the C1 methods are closest to zero, and indices grow away from zero. Private class methods are found only in the negatively-indexed portion, but public methods derived from types may also be there.
For example, the class dispatch vector for CB in Figure 4 contains a negative portion with C1 = CA, C2 = CB and a non-negative portion with T1 = A, T2 = B.
Andrew C. Myers. Bidirectional Object Layout for Separate Compilation.
Proceedings of OOPSLA '95, pp. 124-139.
Copyright © 1995 Association for Computing Machinery