Article

Free access

An evaluation of automatic object inline allocation techniques

Authors:

Andrew A. ChienAuthors Info & Claims

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

Pages 1 - 20

https://doi.org/10.1145/286936.286943

Published: 01 October 1998 Publication History

Abstract

Object-oriented languages such as Java and Smalltalk provide a uniform object reference model, allowing objects to be conveniently shared. If implemented directly, these uniform reference models can suffer in efficiency due to additional memory dereferences and memory management operations. Automatic inline allocation of child objects within parent objects can reduce overheads of heap-allocated pointer-referenced objects.We present three compiler analyses to identify inlinable fields by tracking accesses to heap objects. These analyses span a range from local data flow to adaptive whole-program, flow-sensitive inter-procedural analysis. We measure their cost and effectiveness on a suite of moderate-sized C++ programs (up to 30,000 lines including libraries). We show that aggressive interprocedural analysis is required to enable object inlining, and our adaptive inter-procedural analysis [23] computes precise information efficiently. Object inlining eliminates typically 40% of object accesses and allocations (improving performance up to 50%). Furthermore,

References

[1]

O. Agesen, J. Palsberg, and M. Schwartzbach. Type inference of SELF: Analysis of objects with dynamic and multiple inheritance. In Proceedings of ECOOP '93, 1993.

Digital Library

[2]

P. America. Inheritance and subtyping in a parallel object-oriented language, in Proceedings of ECOOP, pages 234-42. Springer-Verlag, June 1987.

Digital Library

[3]

A. Black, N. Hutchinson, E. Jul, and H. Levy. Object structure in the emerald system. In Proceedings of OOPSLA '86, pages 78-86. ACM, September 1986.

Digital Library

[4]

Zoran Budimlic and Ken Kennedy. Optimizing java: Theory and practice. Concurrency: Practice and Experience, 9(6), June 1997.

[5]

Brad Calder, Dirk Grunwald, and Benjamin Zorn. Quantifying differences between C and C++ programs. Technical Report CU-CS-698-94, University of Colorado, Boulder, January 1994.

[6]

C. Chambers and D. Ungar. Iterative type analysis and extended message splitting. In Proceedings of the SIGPLAN Conference on Programming Language Design and Implementation, pages 150-60, 1990.

Digital Library

[7]

Andrew Chien, Julian Dolby, Bishwaroop Ganguly, Vijay Karamcheti, and Xingbin Zhang. Supporting high level programming with high performance: The Illinois Concert system. In Proceedings of the Second International Workshop on High-level Parallel Programming Models and Supportive Environments, pages 15-24, April 1997.

Digital Library

[8]

Jeffrey Dean, Craig Chambers, and David Grove. Selective specialization for object-oriented languages. In Proceedings of the A CM SIGPLAN '95 Conference on Programmin g Language Design and implementation, pages 93-102, La Jolla, CA, June 1995.

Digital Library

[9]

Julian Dolby. Automatic inline allocation of objects. In Proceedings of the 1997 A CM SIGPLAN Conference on Programming Language Design and Implementation, pages 7-17, Las Vegas, Nevada, June 1997.

Digital Library

[10]

Margaret A. Ellis and Bjarne Stroustrup. The Annotated C++ Reference Manual. Addison-Wesley, 1990.

Digital Library

[11]

Maryam Emami, Rakesh Ghiya, and Laurie J. Hendren. Context-sensitive interprocedural points-to analysis in the presence of function pointers. In Proceedings of the 1994 A CM SIGPLAN Conference on Programming Language Design and Implementation, pages 242-256, 1994.

Digital Library

[12]

Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren. The program dependence graph and its use in optimization. A CM Transactions on Programming Languages and Systems, 9(3):319-49, July 1987.

Digital Library

[13]

Tim Freeman and Frank Pfenning. Refinement types for ML. in Proceedings of the 1991 A CM SIGPLAN Conference on Programming Language Design and Implementation, June 1991.

Digital Library

[14]

Keith E. Gorlen, Sanford M. Orlow, and Perry S. Plexico. Data Abstraction and Object-Oriented Programming in C++. John Wiley and Sons, 1991.

Digital Library

[15]

Cordelia Hall, Simon L. Peyton-Jones, and Patrick M. Sansom. Functional Programming, Glasgow 1994, chapter Unboxing Using Specialization. Workshops in Computing Science. Springer- Verlag, 1995.

[16]

Urs HSlzle, Craig Chambers, and David Ungar. Optimizing dynamically-typed objectoriented languages with polymorphic inline caches. In ECOOP'91 Conference Proceedings. Springer- Verlag, 1991. Lecture Notes in Computer Science 512.

Digital Library

[17]

Urs HSlzle and David Ungar. Optimizing dynamically-dispatched calls with run-time type feedback. In Proceedings of the 1994 A CM SIC- PLAN Conference on Programming Language Design and Implementation, pages 326-336, June 1994.

Digital Library

[18]

Norman C. Hutchinson. Emerald: An Object-Based Language for Distributed Programming. PhD thesis, University of Washington, Department of Computer Science, Seattle, Washington, 1987. TR-87- 01-01.

Digital Library

[19]

Christopher Lapkowski and Laurie Hendren. Extended ssa numbering: Introducing ssa properties to languages with multi-level pointers. In Proceedings of GASCON, 1996.

Digital Library

[20]

Xavier Leroy. Unboxed objects and polymorphic typing. In Proceedings of the 19th Symposium on the Principles of Programming Languages, pages 177-188, 1992.

Digital Library

[21]

J. Palsberg and M. Schwartzbach. Object-oriented type inference. In Proceedings of OOPSLA '91, pages 146-61, 1991.

Digital Library

[22]

James Philbin, Jan Edler, Otto J. Anshus, Craig C. Douglas, and Kai Li. Thread scheduling for cache locality. In Proceedings of the Seventh Symposium on Architectural Support for Programming Languages and Operating Systems (ASPLOS-VII), pages 60-71, 1996.

Digital Library

[23]

John Plevyak. Optimization of Object-Oriented and Concurrent Programs. PhD thesis, University of Illinois at Urbana-Champaign, Urbana, Illinois, 1996.

Digital Library

[24]

John Plevyak and Andrew A. Chien. Precise concrete type inference of object-oriented programs. In Proceedings of OOPSLA '94, Object-Oriented Programming Systems, Languages and Architectures, pages 324-340, 1994.

Digital Library

[25]

John Plevyak and Andrew A. Chien. Type directed cloning for object-oriented programs. In Proceedings of the Workshop for Languages and Compilers for Parallel Computing, pages 566-580, 1995.

Digital Library

[26]

Zhong Shao, John H. Reppy, and Andrew W. Appel. Unrolling lists. In A CM Conference on Lisp and Functional Programming, June 1994.

Digital Library

[27]

Olin Shivers. Control flow analysis in scheme, in SIGPLAN Conference on Programming Language Design and Implementation, pages 164-74. ACM, 1988.

Digital Library

[28]

Olin Shivers. Control-Flow Analysis of Higher- Order Languages. PhD thesis, Carnegie Mellon University Department of Computer Science, Pittsburgh, PA, May 1991. also CMU-CS-91-145.

Digital Library

[29]

Olin Shivers. Topics in Advanced Language Implementation, chapter Data-Flow Analysis and Type Recovery in Scheme, pages 47-88. MIT Press, Cambridge, MA, 1991.

[30]

Guy L. Steele Jr. Common LISP: The Language. Digital Press, second edition, 1990.

Digital Library

[31]

David Stoutamire and Stephen Omohundro. Sather 1.1, draft. Available online from hzZp:// www. i cs i. berkeley, edu/~ ather / Sather- i. i. ps, August 1995.

[32]

Sun Microsystems Computer Corporation. The Java Language Specification, March 1995. Available at http://java.sun.com/1.0alpha2/doc/javawhitepaper.ps.

[33]

N. Wirth and J. Gutknecht. Project Oberon: The Design of an Operating System and Compiler. Addison Wesley, 1992.

Digital Library

Cited By

Møller AVeileborg O(2020)Eliminating abstraction overhead of Java stream pipelines using ahead-of-time program optimizationProceedings of the ACM on Programming Languages10.1145/34282364:OOPSLA(1-29)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428236
Venture GKulić D(2019)Robot Expressive MotionsACM Transactions on Human-Robot Interaction10.1145/33442868:4(1-17)Online publication date: 15-Nov-2019
https://dl.acm.org/doi/10.1145/3344286
Stilkerich ILang CErhardt CBay CStilkerich M(2017)The Perfect GetawayACM Transactions on Embedded Computing Systems10.1145/303554216:4(1-30)Online publication date: 11-May-2017
https://dl.acm.org/doi/10.1145/3035542
Show More Cited By

Index Terms

An evaluation of automatic object inline allocation techniques
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types
        Object oriented languages

Recommendations

An automatic object inlining optimization and its evaluation
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation

Automatic object inlining [19, 20] transforms heap data structures by fusing parent and child objects together. It can improve runtime by reducing object allocation and pointer dereference costs. We report continuing work studying object inlining ...
Automatic inline allocation of objects
PLDI '97: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation

Object-oriented languages like Java and Smalltalk provide a uniform object model that simplifies programming by providing a consistent, abstract model of object behavior. But direct implementations introduce overhead, removal of which requires ...
An evaluation of automatic object inline allocation techniques

Object-oriented languages such as Java and Smalltalk provide a uniform object reference model, allowing objects to be conveniently shared. If implemented directly, these uniform reference models can suffer in efficiency due to additional memory ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

October 1998

428 pages

ISBN:1581130058

DOI:10.1145/286936

Chairmen:
Bjorn Freeman-Benson
Object Technology International, Victoria, B.C., Canada
,
Craig Chambers
Univ. of Washington, Seattle

ACM SIGPLAN Notices Volume 33, Issue 10
Oct. 1998
412 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/286942
Chairmen:
Bjorn Freeman-Benson
Object Technology International, Victoria, B.C., Canada
,
Craig Chambers
Univ. of Washington, Seattle
Issue’s Table of Contents

Copyright © 1998 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 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

OOPSLA98

Sponsor:

SIGPLAN

OOPSLA98: Conference on Object Oriented Programming Systems Languages and Applications

October 18 - 22, 1998

British Columbia, Vancouver, Canada

Acceptance Rates

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
657
Total Downloads

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

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Møller AVeileborg O(2020)Eliminating abstraction overhead of Java stream pipelines using ahead-of-time program optimizationProceedings of the ACM on Programming Languages10.1145/34282364:OOPSLA(1-29)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428236
Venture GKulić D(2019)Robot Expressive MotionsACM Transactions on Human-Robot Interaction10.1145/33442868:4(1-17)Online publication date: 15-Nov-2019
https://dl.acm.org/doi/10.1145/3344286
Stilkerich ILang CErhardt CBay CStilkerich M(2017)The Perfect GetawayACM Transactions on Embedded Computing Systems10.1145/303554216:4(1-30)Online publication date: 11-May-2017
https://dl.acm.org/doi/10.1145/3035542
Eizenberg AHu SPokam GDevietti J(2016)Remix: online detection and repair of cache contention for the JVMACM SIGPLAN Notices10.1145/2980983.290809051:6(251-265)Online publication date: 2-Jun-2016
https://dl.acm.org/doi/10.1145/2980983.2908090
Eizenberg AHu SPokam GDevietti JKrintz CBerger E(2016)Remix: online detection and repair of cache contention for the JVMProceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/2908080.2908090(251-265)Online publication date: 2-Jun-2016
https://dl.acm.org/doi/10.1145/2908080.2908090
Clifford DPayer HStarzinger MTitzer B(2014)Allocation folding based on dominanceACM SIGPLAN Notices10.1145/2775049.260299449:11(15-24)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2775049.2602994
Clifford DPayer HStarzinger MTitzer BGrove DGuyer S(2014)Allocation folding based on dominanceProceedings of the 2014 international symposium on Memory management10.1145/2602988.2602994(15-24)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2602988.2602994
Kandemir MSrikantaiah SSon SPhillips JHu AGraeb H(2011)Improving shared cache behavior of multithreaded object-oriented applications in multicoresProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132356(118-125)Online publication date: 7-Nov-2011
https://dl.acm.org/doi/10.5555/2132325.2132356
Kandemir MSrikantaiah SSon S(2011)Improving shared cache behavior of multithreaded object-oriented applications in multicoresProceedings of the 2011 IEEE/ACM International Conference on Computer-Aided Design10.1109/ICCAD.2011.6105315(118-125)Online publication date: 7-Nov-2011
https://dl.acm.org/doi/10.1109/ICCAD.2011.6105315
Wimmer CMössenbösck H(2010)Automatic feedback-directed object fusingACM Transactions on Architecture and Code Optimization10.1145/1839667.18396697:2(1-35)Online publication date: 5-Oct-2010
https://dl.acm.org/doi/10.1145/1839667.1839669
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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