Space and time-efficient memory layout for multiple inheritance

ABSTRACT

Traditional implementations of multiple inheritance bring about not only an overhead in terms of run-time but also a significant increase in object space. For example, the number of compiler-generated fields in a certain object can be as large as quadratic in the number of its subobjects. The problem of efficient object layout is compounded by the need to support two different semantics of multiple inheritance: shared, in which a base class inherited along distinct paths occurs only once in the derived class, and repeated, in which this base has multiple distinct occurrences in the derived. In this theoretical and foundational paper, we introduce two new techniques to optimize memory layout for multiple inheritance. The main ideas behind these techniques are the inlining of virtual bases and bidirectional memory layout. Our techniques never increase time overhead, and usually even decrease it. We show that in some example hierarchies, more than ten-fold reduction in the space overhead can be achieved. We analyze the complexity of the algorithms to apply these techniques, and give theorems to estimate the efficacy of this application. For concreteness, techniques and examples are discussed in the context of C++.

References

1. 1.D. F. Bacon. Fast and Effective Optimziatfon of Statically Typed Object-Oriented Languages. PhD thesis, University of California at Berkeley, Dec 1997.
2. 2.M. Burke, H. Srinivasan, and P. E Sweeney. A framework for evaluating space and time overhead for c++ object models. Research Report RC 20421, IBM, T2 Watson Research Center, March 1996. Declassified .tan. 1998.
3. 3.L. Cardelli and P. Wegner. On understanding types, data abstractions, and potymorphism. ACM Comput. Surv., 17(4):471-522, 1985.
4. 4.L. Carter and M. Wegman. Universal classes of hash functions. d. Comput. Syst. Sci., 18:143-154,1979.
5. 5.C. Chambers, J. Dean, and D. Grove. Whole-program optimization of object-oriented languages. Technical Report UW-CSE-96-06-02, University of Washington, Department of Computer Science and Engineering, June 1996.
6. 6.Ellis and B. Stroustrup. The Annotated C++ Reference Manual. Addison-Wesley, Jan. 1994.
7. 7.E. Ernst. Propogating mixins. In R. Guerraoui, editor, To appear in theProceedings of the 13th European Conference on Object-Oriented Programming, Lecture Notes in Computer Science, Lisbon, Portugal, June 1999. ECOOP'99, Springer Verlag.
8. 8.S. Even. personal communication, March 1999.
9. 9.M. Flatt, S. Krishnamurthi, and M. Felleisen. Classes and mixins. In Proc. of POPL '98: 25nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 171-183, Jan. 1998.
10. 10.M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.
11. 11.J. Gil and A. Itai. The complexity of object oriented type analysis. In E. Jul, editor, Proceedings of the 11th European Conference on Object- Oriented Programming, Lecture Notes in Computer Science, Brussels, Belgium, July 1998. ECOOP'98, Springer Veflag.
12. 12.D.T. Jones, M. 1. O'R.iordan, and M. J. Zbikowski. Method and system for implementing virtual functoins and virtual base classes and setting a this pointer for an object-odentedprogramming language. US Patent 5,297,284, Mar. 1994. Assignee: Microsoft Corporation, Redmond Wash.
13. 13.M. Karasick. The architecture of montana: An open and extenstbl~ programming environment with an incremental C++ compiler, in Proceedings of Foundations of Software Engineering (FSE'98) (Orlando, FL), Nov. 1997.
14. 14.A.K.rall, J. Vitek, and R. N. Horspool. Near optimal hierarchical encoding of types. In M. Ak~it and S. Matsuoka, editors, Proceedings of the 11th European Conference on Object-Oriented Programming, number 1241 in Lecture Notes in Computer Science, pages 128-145, Jyvaskyla, Finland, June 9-13 1997. ECOOP'97, Springer Vedag.
15. 15.S. Krogdahl. Multiple inheritance in simula-like languages. B/T, 25:318--326,1984.
16. 16.D. Lea, editor, the 6th C++ Conference, Cambridge, MA, Apr. 1994. USEN1X.
17. 17.M.A. Linton and D. Z. Pan. Interface translation and implementation filtering. In Lea { 16}, pages 227-236.
18. 18.S.B. Lipprnan. Inside the C++ Object Model. Addison-Wesley, second edition, 1996.
19. 19.B. Martin. The separation of interface and implementation in C++. In the 3rd C++ Conference, pages 51--62, Washington, DC, Apr. 1991. USENIX.
20. 20.B. Meyer. Object-Oriented Software Construction. Prentice-Hall, second edition, 1997.
21. 21.A. C. Myers. Bidirectional object layout for separate compilation. In OOPSLA'95 {24}, pages 124-139.
22. 22.L. Nackman and J. Barton. Base-class composition with multiple derivation and virtual bases. In Lea {16}, pages 57-72.
23. 23.L. R. Nackman and J. J. Barton. Base-class composition with multiple derivation and virtual bases. In Lea {16}, pages 57-71.
24. 24.OOPSLA'95. Proceedings of the 10~h Annum Conference on Object-Oriented Programming Systems, Languages, and Applications, Austin, Texas, USA, Oct. 15-19 I995. Acre SIGPLAN Notices 30(10) Oct. 1995.
25. 25.W. Pugh and G. Weddell. Two-directional record layout for multiple inheritance. In Proceedings of the ACM SIGPLAN '90 Conference on Programming Design and Implementation (PLDI'90) (White Plains, NY), pages 85--91, June 1990. Also published as ACM SIGPLAN Notices 25(6).
26. 26.J.G. Rossie Jr. and D. E Friedman. An algebraic semantics of subobjects. In OOPSLA'95 {24}, pages 187-199.
27. 27.A. L. M. Shalit. Dylan Reference Manual Addison-Wesley, Reading, MA, 1996.
28. 28.R.M. Stallman. Using andPorting GNU CC. the Free Software Foundation, Feb. 1998. for version 2.8.1.
29. 29.B. Stroustrup. Multiple inheritance for C++. In Proceedings of the European Unix System User's Group Conference, pages 189--207, May 1987.
30. 30.B. Stroustmp. The Design and Evolution of C++. Addison-Wesley, Mar. 1994.
31. 31.B. Stroustrup. The C++ Programming Language. Addison-Wesley, third edition, 1997.
32. 32.P. E Sweeney and M. Burke. A methodology for quantifying and evaluating the space overheadin C++ object models. IBM Research Report RC 21370, IBM, T.t. Watson Research Center, P.O. Box 704, Yorktown Heights, NY 10598, USA, Dec. 1998.
33. 33.E Tip and P. E Sweeney. Class hierarchy specialization. In Proceedings of the Twelfth Annual Conference on Object-Oriented Programruing Systems, Languages, and Applications (OOPSLA "9 7), (Atlanta, GA), pages 271-285, Oct 1997. Also published as ACM SI(iPLAN Notices 32(10).

Index Terms

• Information systems

  • Information storage systems

    • Storage management

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Inheritance

      • Language types

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • File systems management

        • Memory management

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

      • Sorting and searching