Notation



next up previous
Next: Merging Up: Layout Rules Previous: Layout Rules

Notation

 

The construction rules for the bidirectional object layout are described here in a compact graphical notation. The rules are essentially two-dimensional macros. This section briefly describes the notation, and provides some insight into the workings of object layout.

The dispatch headers and dispatch vectors of an object can be thought of as a two-dimensional array. The array rows are dispatch vectors and the columns are individual methods. Each row generates a word of per-object space overhead in the dispatch header. Since different dispatch vectors of the object have different lengths, the rows of the array are ragged.

Each abstract type and class in the system has a distinct dispatch header layout. These layouts are called type headers and class headers, respectively. The layout of an abstract type or class X is symbolized by placing a double box around it:

The height of the box corresponds to the number of dispatch vectors in it, and to the amount of space consumed by the dispatch header in each object. The width of the box is defined as the length of the last dispatch vector in the header. Both the number of dispatch vectors in the box, and the length of the last dispatch vector, are constants for a particular type or class.

The box notation is useful because a type header is compatible with the dispatch header of each of the type's supertypes, and therefore must contain it at some offset. In the box notation, the box of the supertype must be contained within that of the subtype.

An individual dispatch vector or a portion of one is denoted by a simple box. The notation denotes a dispatch vector that contains methods for T1, T2, and so on, in ascending method index order. Method pointers are not duplicated: for each Ti, the methods included in the dispatch vector are those for which there is no method pointer in the T1...Ti-1 part.

The vertical abutting of boxes means that the dispatch vectors of the lower box should be placed after the dispatch vectors of the upper box. The horizontal abutting of a dispatch header H and a dispatch vector V means that the last dispatch vector within H should have V appended to it.

  
Figure 7: A simple type header layout rule

This notation now can be used to express a simple but inefficient rule for constructing type dispatch headers, shown in Figure 7. This is not the rule actually used in the bidirectional layout; a better rule is presented later. Figure 7 is written as an inference rule. The antecedent, written above the line, indicates that the abstract type T has direct supertypes T1, T2,...,Tn. Supertypes are considered direct if they lie immediately above in the type hierarchy; indirect if they lie anywhere above. The triangles above the supertypes indicate that these types are part of an arbitrary type hierarchy extending above them.

The consequent, below the line, states that the layout for T consists of the concatenated layouts for all the supertypes, except that the last dispatch vector has been extended to include the methods of T that are not shared with T1. The mismatch in the heights of the boxes labeled T and T1 is intentional: the box labeled T represents a single dispatch vector, whereas the box labeled T1 represents a dispatch header that may contain several dispatch vectors. The type T1 is called the primary supertype, since its last dispatch vector is merged with that of T. The types T2...Tn are secondary supertypes.

Although this rule is not the actual bidirectional-layout rule, it has several instructive similarities. A reference to an object of type T points to the last dispatch vector in the layout. Conversion from an object of type T to any of its direct supertypes requires only the subtraction of a constant from the object pointer, which is zero in the case of T1, since it is embedded at the end. Conversion to an indirect supertype of T requires the subtraction of a sum of these constant offsets, which is just a constant itself. Calls to any methods of T, given an object of static type T, require only the standard dispatch sequence, because all of the methods of T are present in the last dispatch vector.



next up previous
Next: Merging Up: Layout Rules Previous: Layout Rules

Andrew C. Myers. Bidirectional Object Layout for Separate Compilation. Proceedings of OOPSLA '95, pp. 124-139.
Copyright © 1995 Association for Computing Machinery