article

Quantifying and evaluating the space overhead for alternative C++ memory layouts

Authors:

Peter F. Sweeney,

Michael BurkeAuthors Info & Claims

Software—Practice & Experience, Volume 33, Issue 7

Pages 595 - 636

https://doi.org/10.1002/spe.519

Published: 01 June 2003 Publication History

Abstract

This paper develops a formalism that precisely characterizes when class tables are required for C++ memory layouts. A memory layout is a particular choice of data structures for implementing run-time support for object-oriented languages. We use this formalism to quantify and evaluate, on a set of benchmarks, the space overhead for a set of C++ memory layouts. In particular, this paper studies the space overhead due to three language features: virtual dispatch, virtual inheritance, and dynamic typing. To date, there has been no scientific quantification or evaluation of C++ memory layouts. Our approach can help C++ implementors. This work has already influenced the memory layout design choices in IBM's Visual Age C++ V5 compiler.Applying our approach to a set of five benchmarks, we demonstrate that the impact of object-oriented space overhead can vary dramatically between applications (ranging from 0.42% to 99.79% for our benchmarks). In particular, applications whose object space is dominated by instances of classes that heavily use object-oriented language features will be significantly impacted by the choice of a memory layout.

References

[1]

1. Nackman LR, Barton JJ. Base-class composition with multiple derivation and virtual bases. Sixth Usenix C++ Technical Conference. USENIX Association: Berkeley, 1994.]]

[2]

2. Martin B. The separation of interface and implementation in C++. C++ Conference, Cambridge, MA, April 1991. USENIX Association: Berkeley, 1991; 51-62.]]

[3]

3. Linton MA, Pan DZ. Interface translation and implementation filtering. C++ Conference, Cambridge, MA, April 1991. USENIX Association: Berkeley, 1991; 227-236.]]

[4]

4. Gil J, Sweeney PF. Space- and time-efficient memory layout for multiple inheritance. Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), October 1999. ACM Press: New York, 1999; 256-275.]]

[5]

5. Stroustrup B. Multiple inheritance for C++. Proceedings of the Spring 1987 European Unix Systems Users's Group Conference, Helsinki, May 1987. USENIX Association: Berkeley, 1987.]]

[6]

6. Rose JR. Fast dispatch mechanisms for stock hardware. Proceedings of the 1988 ACM Conference on Object Oriented Programming Systems, Languages, and Applications (OOPSLA), San Diego, CA, October 1988. ACM Press: New York, 1988; 27-35.]]

Digital Library

[7]

7. Dixon R, McKee T, Schweitzer P, Vaughan M. A fast method dispatcher for compiled languages with multiple inheritance. Proceedings of the 1989 ACM Conference on Object Oriented Programming Systems, Languages, and Applications (OOPSLA), New Orleans, LA, October 1989. ACM Press: New York, 1989; 211-214.]]

Digital Library

[8]

8. Ellis MA, Stroustrup B. The Annotated C++ Reference Manual. Addison-Wesley, 1990.]]

[9]

9. Bacon DF, Sweeney PF. Fast static analysis of C++ virtual function calls. Eleventh Annual Conference on Object-Oriented Programming Systems, Languages, and Applications. OOPSLA '96, San Jose, CA, October 1996. ACM Press: New York, 1996; 324-341.]]

Digital Library

[10]

10. Fernandez MF. Simple and effective link-time optimization of modula-3 programs. SIGPLAN '95 Conference on Programming Language Design and Implementation June 1995. ACM Press: New York, 1995; 103-115.]]

Digital Library

[11]

11. Aigner G, Hölzle U. Eliminating virtual function calls in C++ programs. Proceedings of the Tenth European Conference on Object-Oriented Programming--ECOOP'96, Linz, Austria, July 1996 (Lecture Notes in Computer Science, vol. 1098). Springer: New York, 1996; 142-166.]]

[12]

12. Calder B, Grunwald D. Reducing indirect function call overhead in C++ programs. 21st Annual ACM SIGACT-SIGPLAN Symposium on the Principles of Programming Languages, Portland, OR, January 1994. ACM Press: New York, 1994; 397-408.]]

[13]

13. Porat S, Bernstein D, Fedorov Y, Rodrigue J. Compiler optimizations of C++ virtual function calls. Proceedings of the Second Conference on Object-Oriented Technologies and Systems, Toronto, Canada, June 1996. USENIX Association: Berkeley, 1996; 3-14.]]

[14]

14. Dean J, Grove D, Chambers C. Optimization of object-oriented programs using static class hierarchy analysis. Proceedings of the Ninth European Conference on Object-Oriented Programming--ECOOP'95, Aarhus, Denmark, August 1995, Olthoff W (ed.). Springer: New York, 1995; 77-101.]]

[15]

15. Agesen O, Hölzle U. Type feedback vs. concrete type inference: A comparison of optimization techniques for object-oriented languages. Proceedings of the 1995 ACM Conference on Object Oriented Programming Systems, Languages, and Applications (OOPSLA), Austin, TX, October 1995. ACM Press: New York, 1995; 91-107.]]

Digital Library

[16]

16. Zibin Y, Gil J. Fast algorithm for creating space efficient dispatching tables with application to multi-dispatching. Proceedings of the Seventeenth ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, November 2002. ACM Press: New York, 2002; 142-160.]]

[17]

17. Burke M, Srinivasan H, Sweeney PF. A framework for evaluating space and time overhead for C++ object models. Technical Report RC 20421, IBM Thomas J. Watson Research Center, March 1996.]]

[18]

18. Lippman SB. Inside the C++ Object Model. Addison-Wesley: New York, 1996.]]

[19]

19. Srinivasan H, Sweeney PF. Evaluating virtual dispatch mechanisms for C++. Technical Report RC 20330, IBM Thomas J. Watson Research Center, January 1996.]]

[20]

20. Microsoft Corporation and Digital Equipment Coporation. The Component Object Model Specification, version 0.9 edition, October 1995.]]

[21]

21. Gosling J, Joy B, Steele G. The JavaTM Language Specification (The JavaTM Series). Addison-Wesley, 1996.]]

[22]

22. Myers AC. Bidirectional object layout for separate compilation. Proceedings of the 1995 ACM Conference on Object Oriented Programming Systems, Languages, and Applications (OOPSLA), Austin, TX, October 1995. ACM Press: New York, 1995; 124-139.]]

Digital Library

[23]

23. Pugh W, Weddell G. Two-directional record layout for multiple inheritance. Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation (PLDI), White Plains, NY, June 1990. ACM Press: New York, 1990: 85-91.]]

Digital Library

[24]

24. Rossie JG Jr, Friedman DP. An algebraic semantics of subobjects. Tenth Annual Conference on Object-Oriented Programming Systems, Languages, and Applications. OOPSLA '95, Austin, TX, October 1995. ACM Press: New York, 1995; 187.]]

Digital Library

[25]

25. Accredited Standards Committee. Working Paper for Draft Proposed International Standard for Information Systems-- Programming Language C++, November 1997. Doc. No. X3J16/97-0108 WG21/N1146.]]

[26]

26. Jones DT, O'Riordan MJ, Zbikowski MJ. Method and system for implementing virtual functions and virtual base classes and setting a this pointer for an object-oriented programming language. US Patent 5,297,284, March 1994. Assignee Microsoft Corporation.]]

[27]

27. Hind M, Burke M, Carini P, Choi J-D. Interprocedural pointer alias analysis. ACM Transactions on Programming Languages and Systems 1999; 21(4):848-894.]]

[28]

28. Karasick M. The architecture of Montana: An open and extensible programming environment with an incremental C++ compiler. Proceedings of the Foundations of Software Engineering, November 1998. ACM Press: New York, 1998; 131-142.]]

Digital Library

[29]

29. Sweeney PF, Tip F. A study of dead data members in C++ applications. Proceedings of ACM SIGPLAN '98 Conference on Programming Language Design and Implementation (PLDI'98), Montreal, Canada, June 1998. ACM Press: New York, 1998; 324-333 ACM SIGPLAN Notices33(6).]]

Digital Library

Cited By

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
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
Show More Cited By

Index Terms

Quantifying and evaluating the space overhead for alternative C++ memory layouts

Recommendations

Ironclad C++: a library-augmented type-safe subset of c++
OOPSLA '13

The C++ programming language remains widely used, despite inheriting many unsafe features from C---features that often lead to failures of type or memory safety that manifest as buffer overflows, use-after-free vulnerabilities, or abstraction ...
Ironclad C++: a library-augmented type-safe subset of c++
OOPSLA '13: Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications

The C++ programming language remains widely used, despite inheriting many unsafe features from C---features that often lead to failures of type or memory safety that manifest as buffer overflows, use-after-free vulnerabilities, or abstraction ...
Difficulties in Learning C++ and GUI Programming with Qt Platform: View of Students
ICEEG '17: Proceedings of the 1st International Conference on E-commerce, E-Business and E-Government

We have conducted a C++ and GUI programming workshop with Qt platform and a set of 14 tutorials on the several of concepts and topics of programming fundamentals and Qt framework. This is a programming workshop with computer lab sessions without any ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Software

Software Volume 33, Issue 7

June 2003

106 pages

ISSN:0038-0644

EISSN:1097-024X

Issue’s Table of Contents

Publisher

John Wiley & Sons, Inc.

United States

Publication History

Published: 01 June 2003

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
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 R(2011)Implementing statically typed object-oriented programming languagesACM Computing Surveys10.1145/1922649.192265543:3(1-48)Online publication date: 29-Apr-2011
https://dl.acm.org/doi/10.1145/1922649.1922655
Morandat FDucournau R(2010)Empirical assessment of C++-like implementations for multiple inheritanceProceedings of the Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems10.1145/1925801.1925803(1-5)Online publication date: 22-Jun-2010
https://dl.acm.org/doi/10.1145/1925801.1925803
Ducournau RMorandat FPrivat JArora SLeavens G(2009)Empirical assessment of object-oriented implementations with multiple inheritance and static typingProceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications10.1145/1640089.1640093(41-60)Online publication date: 26-Oct-2009
https://dl.acm.org/doi/10.1145/1640089.1640093
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 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
Wasserrab DNipkow TSnelting GTip F(2006)An operational semantics and type safety prooffor multiple inheritance in C++ACM SIGPLAN Notices10.1145/1167515.116750341:10(345-362)Online publication date: 16-Oct-2006
https://dl.acm.org/doi/10.1145/1167515.1167503
Wasserrab DNipkow TSnelting GTip FTarr PCook WBiddle RGabriel R(2006)An operational semantics and type safety prooffor multiple inheritance in C++Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications10.1145/1167473.1167503(345-362)Online publication date: 23-Oct-2006
https://dl.acm.org/doi/10.1145/1167473.1167503

View Options

View options

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 Issue’s Table of Contents