Two-dimensional bidirectional object layout

Abstract

Object layout schemes used in C++ and other languages rely on (sometimes numerous) compiler generated fields. We describe a language-independent object layout scheme, which is space optimal, that is, objects are contiguous, and contain no compiler generated fields other than a single type identifier. As in C++ and other multiple inheritance languages such as CECIL and DYLAN, the new scheme sometimes requires extra levels of indirection to access some of the fields. Using a data set of 28 hierarchies, totaling almost 50,000 types, we show that this scheme improves field access efficiency over standard implementations, and competes favorably with (the non-space-optimal) highly optimized C++ specific implementations. The benchmark includes an analytical model for computing the frequency of indirections in a sequence of field access operations. Our layout scheme relies on whole-program analysis, which requires about 10 microseconds per type on a contemporary architecture (Pentium III, 900Mhz, 256MB machine), even in very large hierarchies. We also present a layout scheme for separate compilation using the user-annotation of virtual inheritance edge that is used in C++.

References

1. Arnold, K. and Gosling, J. 1996. The Java Programming Language. The Java Series. Addison-Wesley Publishing Company, Reading, MA.
2. Borning, A. H. and Ingalls, D. H. H. 1982. Multiple inheritance in Smalltalk80. In Proceedings of the 2nd National Conference on Artificial Intelligence. MIT Press, Cambridge, MA, 234--238.
3. Cargill, T. A., Cox, B., Cook, W. R., Loomis, M., and Snyder, A. 1993. Is multiple inheritance essential to OOP? Panel discussion at the ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'93).
4. Chambers, C. 1993. The Cecil language, specification and rationale. Tech. rep. TR-93-03-05, University of Washington, Seattle.
5. Dixon, R., McKee, T., Vaughan, M., and Schweizer, P. 1989. A fast method dispatcher for compiled languages with multiple inheritance. In Proceedings of the 4th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'89), N. K. Meyrowitz, Ed. ACM SIGPLAN Notices 24, 10, 211--214.
6. Eckel, N. and Gil, J. 2000. Empirical study of object-layout strategies and optimization techniques. In Proceedings of the 14th European Conference on Object-Oriented Programming (ECOOP'00), E. Bertino, Ed. Lecture Notes in Computer Science, vol. 1850. Springer Verlag, 394--421.
7. Gil, J. and Sweeney, P. F. 1999. Space- and time-efficient memory layout for multiple inheritance. In Proceedings of the 14th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'99). ACM SIGPLAN Notices 34, 10, 256--275.
8. Goldberg, A. 1984. Smalltalk-80: The Interactive Programming Environment. Addison-Wesley, Reading, MA.
9. Lippman, S. B. 1996. Inside The C++ Object Model 2nd ed. Addison-Wesley, Reading, MA.
10. Magnussun, B., Meyer, B., et al. 1994. Who needs need multiple inheritance. In Proceedings of the International Conference on Technology of Object-Oriented Languages and Systems (TOOLS'94). Prentice-Hall, Englewood Cliffs, NJ.
11. Moon, D. A. 1986. Object-oriented programming with flavors. In Proceedings of the 1st Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'86), N. K. Meyrowitz, Ed. ACM SIGPLAN Notices 21, 11, ON, 1--8.
12. Myers, A. C. 1995. Bidirectional object layout for separate compilation. In Proceedings of the 10th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'95). ACM SIGPLAN Notices 30, 10, 124--139.
13. Pascal, A. and Royer, J. 1992. Optimizing Method Search with Lookup Caches and Incremental Coloring. In Proceedings of the 7th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'92), A. Paepcke, Ed. ACM SIGPLAN Notices 27, 10, 110--126.
14. Pugh, W. and Weddell, G. 1990. Two-directional record layout for multiple inheritance. In Proceedings of the Conference on Programming Language Design and Implementation (PLDI'90). ACM SIGPLAN Notices 25, 6, 85--91.
15. Pugh, W. and Weddell, G. 1993. On object layout for multiple inheritance. Tech. rep. CS-93-22, Department of Computer Science, University of Waterloo.
16. Shalit, A. 1997. The Dylan Reference Manual: The Definitive Guide to the New Object-Oriented Dynamic Language. Addison-Wesley Publishing Company, Reading, MA.
17. Stroustrup, B. 1994. The Design and Evolution of C++. Addison-Wesley Publishing Company, Reading, MA.
18. Stroustrup, B. 1997. The C++ Programming Language 3rd ed. Addison-Wesley Publishing Company, Reading, MA.
19. Sweeney, P. F. and Burke, M. 2003. Quantifying and evaluating the space overhead for alternative C++ memory layouts. Softw. Pract. Exp. 33, 7, 595--636.
20. Trotter, W. T. 1992. Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins University Press, Baltimore, MD.
21. Zendra, O., Colnet, D., and Collin, S. 1997. Efficient dynamic dispatch without virtual function tables: The SmallEiffel compiler. In Proceedings of the 12th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'97). ACM SIGPLAN Notices 32, 10, 125--141.
22. Zibin, Y. and Gil, J. 2001. Efficient subtyping tests with PQ-encoding. In Proceedings of the 16th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'01). ACM SIGPLAN Notices 36, 11, 96--107.
23. Zibin, Y. and Gil, J. 2002. Fast algorithm for creating space efficient dispatching tables with application to multi-dispatching. In Proceedings of the 17th Annual Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'02). ACM SIGPLAN Notices 37, 11, 142--160.
24. Zibin, Y. and Gil, J. 2003. Incremental algorithms for dispatching in dynamically typed languages. In Proceedings of the 13th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'03). ACM Press, New York, NY, 126--138.

Index Terms

• Mathematics of computing

  • Mathematical software

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Data types and structures

      • Language types

        • Object oriented languages