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: Ken Arnold , James Gosling , David Holmes, The Java Programming Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 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: Yen-Ping Shan , Tom Cargill , Brad Cox , William Cook , Mary Loomis , Alan Snyder, Is multiple inheritance essential to OOP? (panel), Proceedings of the eighth annual conference on Object-oriented programming systems, languages, and applications, p.360-363, September 26-October 01, 1993, Washington, D.C., United States
• 4: Chambers, C. 1993. The Cecil language, specification and rationale. Tech. rep. TR-93-03-05, University of Washington, Seattle.
• 5: R. Dixon , T. McKee , M. Vaughan , P. Schweizer, A fast method dispatcher for compiled languages with multiple inheritance, Conference proceedings on Object-oriented programming systems, languages and applications, p.211-214, October 02-06, 1989, New Orleans, Louisiana, United States
• 6: Natalie Eckel , Joseph Gil, Empirical Study of Object-Layout Strategies and Optimization Techniques, Proceedings of the 14th European Conference on Object-Oriented Programming, p.394-421, June 12-16, 2000
• 7: Peter F. Sweeney , Joseph (Yossi) Gil, Space and time-efficient memory layout for multiple inheritance, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.256-275, November 01-05, 1999, Denver, Colorado, United States
• 8: Adele Goldberg, SMALLTALK-80: the interactive programming environment, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 9: Stanley B. Lippman, Inside the C++ object model, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
• 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: David A. Moon, Object-oriented programming with flavors, Conference proceedings on Object-oriented programming systems, languages and applications, p.1-8, September 29-October 02, 1986, Portland, Oregon, United States
• 12: 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
• 13: Pascal André , Jean-Claude Royer, Optimizing method search with lookup caches and incremental coloring, conference proceedings on Object-oriented programming systems, languages, and applications, p.110-126, October 18-22, 1992, Vancouver, British Columbia, Canada
• 14: 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
• 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: Andrew Shalit, The Dylan reference manual: the definitive guide to the new object-oriented dynamic language, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
• 17: Bjarne Stroustrup, The design and evolution of C++, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 18: Bjarne Stroustrup, The C++ Programming Language, Third Edition, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 19: Peter F. Sweeney , Michael Burke, Quantifying and evaluating the space overhead for alternative C++ memory layouts, Software—Practice & Experience, v.33 n.7, p.595-636, June 2003 [doi>10.1002/spe.519]
• 20: Trotter, W. T. 1992. Combinatorics and Partially Ordered Sets: Dimension Theory. Johns Hopkins University Press, Baltimore, MD.
• 21: Olivier Zendra , Dominique Colnet , Suzanne Collin, Efficient dynamic dispatch without virtual function tables: the SmallEiffel compiler, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.125-141, October 05-09, 1997, Atlanta, Georgia, United States
• 22: Yoav Zibin , Joseph Yossi Gil, Efficient subtyping tests with PQ-encoding, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.96-107, October 14-18, 2001, Tampa Bay, FL, USA
• 23: Yoav Zibin , Joseph Yossi Gil, Fast algorithm for creating space efficient dispatching tables with application to multi-dispatching, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 24: Yoav Zibin , Joseph (Yossi) Gil, Incremental algorithms for dispatching in dynamically typed languages, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.126-138, January 15-17, 2003, New Orleans, Louisiana, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

Keywords:
bidirectional, coloring, hierarchy, inheritance, layout