This paper has presented the bidirectional object layout, a new layout scheme that produces compact objects with fast method dispatch. The scheme works for statically typed, separately compiled object-oriented languages with explicit subtype declarations, an important category that previous object layout work has not fully explored. The rules for constructing new objects depend only on local information about the type hierarchy, so existing object layouts are not invalidated by extensions to the hierarchy. Therefore, the bidirectional layout scheme scales better to large-scale software development than other schemes requiring a global type analysis phase.
The object layouts produced by this scheme are as compact or more compact than those produced by current compilers, and dispatch is as fast or faster on stock hardware. Typically, the dispatch information is compacted into a single dispatch vector, and method dispatch is as fast as a single-inheritance implementation of C++.
There are two key insights behind the scheme: first, the three different uses of multiple inheritance are treated differently in the scheme, allowing dispatch information to be compacted in ways that are not possible for full multiple inheritance. Second, the object layout is reordered, separating the dispatch information from the fields of the object. The dispatch information can then be merged by the set of formal rules that have been presented here.
Perusal of existing code shows that existing C++ code also separates the functionalities of subtyping, abstraction, and inheritance, and that the bidirectional layout will support many existing hierarchies more efficiently.
Finally, the paper has shown how full method subtyping rules with signature refinement can be supported efficiently in the bidirectional scheme and in most existing multiple-view systems.
I would like to thank Kavita Bala, Miguel Castro, Dawson Engler, Umesh Maheshwari, and the referees for their excellent comments on this paper, and especially Barbara Liskov for her support and advice on this paper and the thesis that led to it.
Andrew C. Myers. Bidirectional Object Layout for Separate Compilation.
Proceedings of OOPSLA '95, pp. 124-139.
Copyright © 1995 Association for Computing Machinery