Article

Free access

Space and time-efficient memory layout for multiple inheritance

Authors:

Peter F. Sweeney,

Joseph (Yossi) GilAuthors Info & Claims

OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

Pages 256 - 275

https://doi.org/10.1145/320384.320408

Published: 01 October 1999 Publication History

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]

D. F. Bacon. Fast and Effective Optimziatfon of Statically Typed Object-Oriented Languages. PhD thesis, University of California at Berkeley, Dec 1997.

Digital Library

[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]

L. Cardelli and P. Wegner. On understanding types, data abstractions, and potymorphism. ACM Comput. Surv., 17(4):471-522, 1985.

Digital Library

[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]

Ellis and B. Stroustrup. The Annotated C++ Reference Manual. Addison-Wesley, Jan. 1994.

Digital Library

[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]

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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]

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.

Digital Library

[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]

S. Krogdahl. Multiple inheritance in simula-like languages. B/T, 25:318--326,1984.

Digital Library

[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]

S.B. Lipprnan. Inside the C++ Object Model. Addison-Wesley, second edition, 1996.

Digital Library

[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]

B. Meyer. Object-Oriented Software Construction. Prentice-Hall, second edition, 1997.

Digital Library

[21]

A. C. Myers. Bidirectional object layout for separate compilation. In OOPSLA'95 {24}, pages 124-139.

Digital Library

[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]

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).

Digital Library

[26]

J.G. Rossie Jr. and D. E Friedman. An algebraic semantics of subobjects. In OOPSLA'95 {24}, pages 187-199.

Digital Library

[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]

B. Stroustmp. The Design and Evolution of C++. Addison-Wesley, Mar. 1994.

Digital Library

[31]

B. Stroustrup. The C++ Programming Language. Addison-Wesley, third edition, 1997.

Digital Library

[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]

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).

Digital Library

Cited By

Ressia JGîrba TNierstrasz OPerin FRenggli L(2014)TalentsSoftware—Practice & Experience10.1002/spe.216044:4(413-432)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1002/spe.2160
Yang JBalakrishnan GMaeda NIvančić FGupta ASinha NSankaranarayanan SSharma N(2012)Object model construction for inheritance in c++ and its applications to program analysisProceedings of the 21st international conference on Compiler Construction10.1007/978-3-642-28652-0_8(144-164)Online publication date: 24-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28652-0_8
Ressia JGîrba TNierstrasz OPerin FRenggli LLagadec LPlantec A(2011)TalentsProceedings of the International Workshop on Smalltalk Technologies10.1145/2166929.2166940(1-9)Online publication date: 23-Aug-2011
https://dl.acm.org/doi/10.1145/2166929.2166940
Show More Cited By

Index Terms

Space and time-efficient memory layout for multiple inheritance

Recommendations

Space and time-efficient memory layout for multiple inheritance

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 ...
Two-directional record layout for multiple inheritance
PLDI '90: Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation

Much recent work in polymorphic programming languages allows subtyping and multiple inheritance for records. In such systems, we would like to extract a field from a record with the same efficiency as if we were not making use of subtyping and multiple ...
A Reduction of Grid-Bag Layout to Auckland Layout
ASWEC '10: Proceedings of the 2010 21st Australian Software Engineering Conference

Many major programming platforms support layout managers in Grid-bag style, where GUI elements can be placed on a rectangular grid. In Grid-bag layout mangers, cells of the underlying grid can be merged in order to create more complex layouts. In this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

October 1999

462 pages

ISBN:1581132387

DOI:10.1145/320384

Chairmen:
Brent Hailpern
IBM T. J. Watson Research Center
,
Linda M. Northrop
Carnegie Mellon Univ., Pittsburgh, PA
,
Editor:
A. Michael Berman

ACM SIGPLAN Notices Volume 34, Issue 10
Oct. 1999
460 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/320385
Chairman:
Brent Hailpern,
Editors:
A. Michael Berman,
Linda M. Northrop
Issue’s Table of Contents

Copyright © 1999 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

OOPSLA99

Sponsor:

SIGPLAN

OOPSLA99: Conference on Object Oriented Programming Systems Languages and Applications

November 1 - 5, 1999

Colorado, Denver, USA

Acceptance Rates

OOPSLA '99 Paper Acceptance Rate 30 of 152 submissions, 20%;

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
1,013
Total Downloads

Downloads (Last 12 months)141
Downloads (Last 6 weeks)21

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ressia JGîrba TNierstrasz OPerin FRenggli L(2014)TalentsSoftware—Practice & Experience10.1002/spe.216044:4(413-432)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1002/spe.2160
Yang JBalakrishnan GMaeda NIvančić FGupta ASinha NSankaranarayanan SSharma N(2012)Object model construction for inheritance in c++ and its applications to program analysisProceedings of the 21st international conference on Compiler Construction10.1007/978-3-642-28652-0_8(144-164)Online publication date: 24-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28652-0_8
Ressia JGîrba TNierstrasz OPerin FRenggli LLagadec LPlantec A(2011)TalentsProceedings of the International Workshop on Smalltalk Technologies10.1145/2166929.2166940(1-9)Online publication date: 23-Aug-2011
https://dl.acm.org/doi/10.1145/2166929.2166940
Ramananandro TDos Reis GLeroy XBall TSagiv M(2011)Formal verification of object layout for c++ multiple inheritanceProceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/1926385.1926395(67-80)Online publication date: 26-Jan-2011
https://dl.acm.org/doi/10.1145/1926385.1926395
Ramananandro TDos Reis GLeroy X(2011)Formal verification of object layout for c++ multiple inheritanceACM SIGPLAN Notices10.1145/1925844.192639546:1(67-80)Online publication date: 26-Jan-2011
https://dl.acm.org/doi/10.1145/1925844.1926395
Ducournau RMorandat FPrivat J(2009)Empirical assessment of object-oriented implementations with multiple inheritance and static typingACM SIGPLAN Notices10.1145/1639949.164009344:10(41-60)Online publication date: 25-Oct-2009
https://dl.acm.org/doi/10.1145/1639949.1640093
Gil JMaman I(2008)WhiteoakACM SIGPLAN Notices10.1145/1449955.144977143:10(73-90)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1449955.1449771
Gil JMaman IHarris GKiczales GRiehle DBlack A(2008)WhiteoakProceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications10.1145/1449764.1449771(73-90)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1449764.1449771
Gil JPugh WWeddell GZibin Y(2008)Two-dimensional bidirectional object layoutACM Transactions on Programming Languages and Systems10.1145/1387673.138767730:5(1-38)Online publication date: 4-Sep-2008
https://dl.acm.org/doi/10.1145/1387673.1387677
Bergel ADucasse SNierstrasz OWuyts R(2008)Stateful traits and their formalizationComputer Languages, Systems and Structures10.1016/j.cl.2007.05.00334:2-3(83-108)Online publication date: 1-Jul-2008
https://dl.acm.org/doi/10.1016/j.cl.2007.05.003
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents