Empirical assessment of object-oriented implementations with multiple inheritance and static typing

ABSTRACT

Object-oriented languages involve a threefold tradeoff between runtime efficiency, expressiveness (multiple inheritance), and modularity, i.e. open-world assumption (OWA). Runtime efficiency is conditioned by both the implementation technique and compilation scheme. The former specifies the data structures that support method invocation, attribute access and subtype testing. The latter consists of the production line of an executable from the source code. Many implementation techniques have been proposed and several compilation schemes can be considered from fully global compilation under the closed-world assumption (CWA) to separate compilation with dynamic loading under the OWA, with midway solutions. This article reviews a significant subset of possible combinations and presents a systematic, empirical comparison of their respective efficiencies with all other things being equal. The testbed consists of the Prm compiler that has been designed for this purpose. The considered techniques include C++ subobjects, coloring, perfect hashing, binary tree dispatch and caching. A variety of processors were considered. Qualitatively, these first results confirm the intuitive or theoretical abstract assessments of the tested approaches. As expected, efficiency increases as CWA strengthens. From a quantitative standpoint, the results are the first to precisely compare the efficiency of techniques that are closely associated with specific languages like C++ and Eiffel. They also confirm that perfect hashing should be considered for implementing Java and .Net interfaces.

REFERENCES

• 1: B. Alpern, A. Cocchi, S. Fink, and D. Grove. Efficient implementation of Java interfaces: Invokeinterface considered harmless. In Proc. OOPSLA'01, SIGPLAN Notices, 36(10), pages 108--124. ACM Press, 2001a.
• 2: B. Alpern, A. Cocchi, and D. Grove. Dynamic type checking in Jalapeño. In Proc. USENIX JVM'01, 2001b.
• 3: M. Arnold, S.J. Fink, D. Grove, M. Hind, and P.F. Sweeney. A survey of adaptive optimization in virtual machines. Proceedings of the IEEE, 93(2):449--466, Feb. 2005.
• 4: D. F. Bacon, M. Wegman, and K. Zadeck. Rapid type analysis for C++. Technical report, IBM Thomas J.Watson Research Center, 1996.
• 5: D.F. Bacon and P. Sweeney. Fast static analysis of C++ virtual function calls. In Proc. OOPSLA'96, SIGPLAN Notices, 31(10), pages 324--341. ACM Press, 1996.
• 6: H.-J. Boehm. Space-efficient conservative garbage collection. In Proc. ACM PLDI'93, ACM SIGPLAN Notices, 28(6), pages 197--206, 1993.
• 7: D. Boucher. GOld: a link-time optimizer for Scheme. In M. Felleisen, editor, Proc. Workshop on Scheme and Functional Programming. Rice Technical Report 00-368, pages 1--12, 2000.
• 8: C. Click and J. Rose. Fast subtype checking in the Hotspot JVM. In Proc. ACM-ISCOPE Conf. on Java Grande (JGI'02), pages 96--107, 2002.
• 9: N.H. Cohen. Type-extension type tests can be performed in constant time. ACM Trans. Program. Lang. Syst., 13(4):626--629, 1991.
• 10: S. Collin, D. Colnet, and O. Zendra. Type inference for late binding. the SmallEiffel compiler. In Proc. Joint Modular Languages Conference, LNCS 1204, pages 67--81. Springer, 1997.
• 11: Z. J. Czech, G. Havas, and B. S. Majewski. Perfect hashing. Theor. Comput. Sci., 182(1-2):1--143, 1997.
• 12: J. Dean, C. Chambers, and D. Grove. Selective specialization for object-oriented languages. In Proc. ACM PLDI'95, pages 93--102, 1995a.
• 13: J. Dean, D. Grove, and C. Chambers. Optimization of objectoriented programs using static class hierarchy analysis. In W. Olthoff, editor, Proc. ECOOP'95, LNCS 952, pages 77--101. Springer, 1995b.
• 14: R. Dixon, T. McKee, P. Schweitzer, and M. Vaughan. A fast method dispatcher for compiled languages with multiple inheritance. In Proc. OOPSLA'89, pages 211--214. ACM Press, 1989.
• 15: K. Driesen. Efficient Polymorphic Calls. Kluwer Academic Publisher, 2001.
• 16: R. Ducournau. Coloring, a versatile technique for implementing object-oriented languages. Rapport de Recherche 06-001, LIRMM, Université Montpellier 2, 2006.
• 17: R. Ducournau. Perfect hashing as an almost perfect subtype test. ACM Trans. Program. Lang. Syst., 30(6):1--56, 2008.
• 18: R. Ducournau. Implementing statically typed object-oriented programming languages. ACM Computing Surveys, 2009. (to appear).
• 19: R. Ducournau. Yet Another Frame-based Object-Oriented Language: YAFOOL Reference Manual. Sema Group, Montrouge, France, 1991.
• 20: R. Ducournau and F. Morandat. More results on perfect hashing for implementing object-oriented languages. Rapport de Recherche 09-001, LIRMM, Université Montpellier 2, 2009.
• 21: R. Ducournau and J. Privat. Metamodeling semantics of multiple inheritance. Rapport de Recherche 08-017, LIRMM, Université Montpellier 2, 2008.
• 22: N. Eckel and J. Gil. Empirical study of object-layout and optimization techniques. In E. Bertino, editor, Proc. ECOOP'2000, LNCS 1850, pages 394--421. Springer, 2000.
• 23: M.A. Ellis and B. Stroustrup. The annotated C++ reference manual. Addison-Wesley, Reading, MA, US, 1990.
• 24: M.R. Garey and D.S. Johnson. Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco (CA), USA, 1979.
• 25: J. Gil and P. Sweeney. Space and time-efficient memory layout for multiple inheritance. In Proc. OOPSLA'99, SIGPLAN Notices, 34(10), pages 256--275. ACM Press, 1999.
• 26: A. Goldberg and D. Robson. Smalltalk-80, the Language and its Implementation. Addison-Wesley, Reading (MA), USA, 1983.
• 27: D. Grove and C. Chambers. A framework for call graph construction algorithms. ACM Trans. Program. Lang. Syst., 23(6):685--746, 2001.
• 28: S. P. Harbinson. Modula-3. Prentice Hall, 1992.
• 29: U. Hölzle, C. Chambers, and D. Ungar. Optimizing dynamicallytyped object-oriented languages with polymorphic inline caches. In P. America, editor, Proc. ECOOP'91, LNCS 512, pages 21--38. Springer, 1991.
• 30: R. Jones and R. Lins. Garbage Collection. Wiley, 1996.
• 31: A. Kennedy and D. Syme. Design and implementation of generics for the .NET Common Language Runtime. In Proc. ACM PLDI'01, pages 1--12. ACM Press, 2001.
• 32: S. B. Lippman. Inside the C++ Object Model. Addison-Wesley, New York, 1996.
• 33: B. Meyer. Eiffel: The Language. Prentice-Hall, 1992.
• 34: B. Meyer. Object-Oriented Software Construction. Prentice-Hall, second edition, 1997.
• 35: F. Morandat, R. Ducournau, and J. Privat. Evaluation de l'efficacité des implémentations de l'héritage multiple en typage statique. In B. Carré and O. Zendra, editors, Actes LMO'2009, pages 17--32. Cépaduès, 2009.
• 36: H. Mössenböck. Object-Oriented Programming in Oberon-2. Springer, 1993.
• 37: S. Muthukrishnan and M. Muller. Time and space efficient method lookup for object-oriented languages. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 42--51. ACM/SIAM, 1996.
• 38: A. Myers. Bidirectional object layout for separate compilation. In Proc. OOPSLA'95, SIGPLAN Notices, 30(10), pages 124--139. ACM Press, 1995.
• 39: M. Odersky and P. Wadler. Pizza into Java: Translating theory into practice. In Proc. POPL'97, pages 146--159. ACM Press, 1997.
• 40: K. Palacz and J. Vitek. Java subtype tests in real-time. In L. Cardelli, editor, Proc. ECOOP'2003, LNCS 2743, pages 378--404. Springer, 2003.
• 41: J. Privat and R. Ducournau. Link-time static analysis for efficient separate compilation of object-oriented languages. In ACM Workshop on Prog. Anal. Soft. Tools Engin. (PASTE'05), pages 20--27, 2005.
• 42: W. Pugh and G. Weddell. Two-directional record layout for multiple inheritance. In Proc. PLDI'90, ACM SIGPLAN Notices, 25(6), pages 85--91, 1990.
• 43: O. Shivers. Control-Flow Analysis of Higher-Order Languages. PhD thesis, Carnegie Mellon University, 1991.
• 44: R. Sprugnoli. Perfect hashing functions: a single probe retrieving method for static sets. Comm. ACM, 20(11):841--850, 1977.
• 45: G.L. Steele. Common Lisp, the Language. Digital Press, second edition, 1990.
• 46: P. F. Sweeney and M. G. Burke. Quantifying and evaluating the space overhead for alternative C++ memory layouts. Softw., Pract. Exper., 33(7):595--636, 2003.
• 47: S. T. Taft, R. A. Duff, R. L. Brukardt, E. Ploedereder, and P. Leroy, editors. Ada 2005 Reference Manual: Language and Standard Libraries. LNCS 4348. Springer, 2006.
• 48: F. Tip and P. F. Sweeney. Class hierarchy specialization. Acta Informatica, 36(12):927--982, 2000.
• 49: J. Vitek, R.N. Horspool, and A. Krall. Efficient type inclusion tests. In Proc. OOPSLA'97, SIGPLAN Notices, 32(10), pages 142--157. ACM Press, 1997.
• 50: O. Zendra, D. Colnet, and S. Collin. Efficient dynamic dispatch without virtual function tables: The SmallEiffel compiler. In Proc. OOPSLA'97, SIGPLAN Notices, 32(10), pages 125--141. ACM Press, 1997.
• 51: Y. Zibin and J. Gil. Two-dimensional bi-directional object layout. In L. Cardelli, editor, Proc. ECOOP'2003, LNCS 2743, pages 329--350. Springer, 2003.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages
      D.3.4 Processors
          Subjects: Run-time environments

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Object representation

General Terms:
Experimentation, Languages, Measurement, Performance

Keywords:
binary tree dispatch, closed-world assumption, coloring, downcast, dynamic loading, interfaces, late binding, method tables, multiple inheritance, multiple subtyping, open-world assumption, perfect hashing, single inheritance, subtype test, type analysis, virtual function table