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: David Francis Bacon , Susan L. Graham, Fast and effective optimization of statically typed object-oriented languages, 1997
• 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: Luca Cardelli , Peter Wegner, On understanding types, data abstraction, and polymorphism, ACM Computing Surveys (CSUR), v.17 n.4, p.471-523, Dec. 1985 [doi>10.1145/6041.6042]
• 4: L. Carter and M. Wegman. Universal classes of hash functions. d. Comput. Syst. Sci., 18:143-154,1979.
• 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: Margaret A. Ellis , Bjarne Stroustrup, The annotated C++ reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 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: S. Even. personal communication, March 1999.
• 9: Matthew Flatt , Shriram Krishnamurthi , Matthias Felleisen, Classes and mixins, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.171-183, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268961]
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: Joseph Gil , Alon Itai, The Complexity of Type Analysis of Object Oriented Programs, Proceedings of the 12th European Conference on Object-Oriented Programming, p.601-634, July 20-24, 1998
• 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: Michael Karasick, The architecture of Montana: an open and extensible programming environment with an incremental C++ compiler, Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, p.131-142, November 01-05, 1998, Lake Buena Vista, Florida, United States
• 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: Stein Krogdahl, Multiple inheritance in simula-like languages, BIT, v.25 n.2, p.318-326, 1985 [doi>10.1007/BF01934377]
• 16: D. Lea, editor, the 6th C++ Conference, Cambridge, MA, Apr. 1994. USEN1X.
• 17: M.A. Linton and D. Z. Pan. Interface translation and implementation filtering. In Lea { 16}, pages 227-236.
• 18: Stanley B. Lippman, Inside the C++ object model, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
• 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: Bertrand Meyer, Object-oriented software construction (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1997
• 21: Andrew C. Myers, Bidirectional object layout for separate compilation, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.124-139, October 15-19, 1995, Austin, Texas, United States
• 22: L. Nackman and J. Barton. Base-class composition with multiple derivation and virtual bases. In Lea {16}, pages 57-72.
• 23: L. R. Nackman and J. J. Barton. Base-class composition with multiple derivation and virtual bases. In Lea {16}, pages 57-71.
• 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: William Pugh , Grant Weddell, Two-directional record layout for multiple inheritance, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.85-91, June 1990, White Plains, New York, United States
• 26: Jonathan G. Rossie, Jr. , Daniel P. Friedman, An algebraic semantics of subobjects, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.187-199, October 15-19, 1995, Austin, Texas, United States
• 27: A. L. M. Shalit. Dylan Reference Manual Addison-Wesley, Reading, MA, 1996.
• 28: R.M. Stallman. Using andPorting GNU CC. the Free Software Foundation, Feb. 1998. for version 2.8.1.
• 29: B. Stroustrup. Multiple inheritance for C++. In Proceedings of the European Unix System User's Group Conference, pages 189--207, May 1987.
• 30: Bjarne Stroustrup, The design and evolution of C++, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 31: Bjarne Stroustrup, The C++ programming language (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 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: Frank Tip , Peter F. Sweeney, Class hierarchy specialization, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.271-285, October 05-09, 1997, Atlanta, Georgia, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: C++

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Inheritance
  D.4 OPERATING SYSTEMS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Reliability, Theory, Verification