Article

Free access

Automatic inline allocation of objects

Author:

Julian DolbyAuthors Info & Claims

PLDI '97: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation

Pages 7 - 17

https://doi.org/10.1145/258915.258918

Published: 01 May 1997 Publication History

Abstract

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 aggressive implementation techniques (e.g. type inference, function specialization); in this paper, we introduce object inlining, an optimization that automatically inline allocates objects within containers (as is done by hand in C++) within a uniform model. We present our technique, which includes novel program analyses that track how inlinable objects are used throughout the program. We evaluated object inlining on several object-oriented benchmarks. It produces performance up to three times as fast as a dynamic model without inlining and roughly equal to that of manually-inlined codes.

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]

Jennifer M. Anderson, Saman P. Amarasinghe, and Monica S. Lam. Data and computation transformations for multiprocessors. In Proceedings of Fifth Symposium on Principles and Practice of Parallel Programming, 1995.

Digital Library

[3]

Apple Computer inc. The NewtonScript Program. ruing Language, December 1995. Available online from ftp://ftpdev.info.apple.com/Developer_Services/ Newton.Development/DOCS_PDF/NSCRIPTR.ZIP.

[4]

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

Digital Library

[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 SIG- PLAN Conference on Programming Language Design and Implementation, pages 150-60, 1990.

Digital Library

[7]

Craig Chambers. The Cecil language: Specification and rationale, version 2.0. Technical report, Department of Computer Science and Engineering, University of Washington, Seattle, Washington, March 1995.

[8]

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 Inter. national Workshop on High-level Parallel Programming Models and Supportive Environments, April 1997.

Digital Library

[9]

Andrew A. Chien, Uday S. Reddy, John Plevyak, and Julian Dolby. ICC++ - a C++ dialect for highperformance parallel computation. In Proceedings of the ~nd International Symposium on Object Technologies for Advanced Software, March 1996.

Digital Library

[10]

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

Digital Library

[11]

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

Digital Library

[12]

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

[13]

Adele Goldberg and David Robson. Smalltalk-80: The language and its implementation. Addison-Wesley, 1985.

Digital Library

[14]

H. Mossenbock.Object-Oriented Programming in Oberon-2. Springer-Verlag, 1993.

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 object-oriented 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 dynamicallydispatched calls with run-time type feedback. In Proceedings of the 199j ACM SIGPLAN 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]

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

[20]

N. Wirth and J. Gutknecht. Project Oberon: The Design of an Operating System and Compiler. Addison Wesley, 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]

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

Digital Library

[23]

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

Digital Library

[24]

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

[25]

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

Digital Library

[26]

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

[27]

Sun Microsystems Computer Corporation. The Java Language Specification, March 1995. Available at ht tp://j ava. sun. corn/1.0alp ha2/doc }java-whitepaper. ps.

[28]

Gregory V. Wilson and Paul Lu, editors. Parallel Programming Using C-t-4-. MIT Press, 1995.

[29]

Micheal E. Wolf and Monica S. Lam. A data locality optimizing algorithm. In Proceedings of the 1991 A CM SIGPLAN Conference on Programming Language Design and Implementation, June 1991.

Digital Library

Cited By

Lam CParreaux L(2024)Being Lazy When It CountsFunctional and Logic Programming10.1007/978-981-97-2300-3_11(188-216)Online publication date: 15-May-2024
https://dl.acm.org/doi/10.1007/978-981-97-2300-3_11
Bruno RJovanovic VWimmer CAlonso GFreund SYahav E(2021)Compiler-assisted object inlining with value fieldsProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454034(128-141)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454034
Xu SBremner DHeidinga DBlackburn SBockisch CHaupt MHosking TRajan HSrisa-an WGrimmer MWelc A(2017)Fusing method handle graphs for efficient dynamic JVM language implementationsProceedings of the 9th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3141871.3141874(18-27)Online publication date: 24-Oct-2017
https://dl.acm.org/doi/10.1145/3141871.3141874
Show More Cited By

Index Terms

Automatic inline allocation of objects
1. Social and professional topics
  1. Professional topics
    1. Management of computing and information systems
      1. Project and people management
2. Software and its engineering

Recommendations

An evaluation of automatic object inline allocation techniques
OOPSLA '98: Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

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 ...
Automatic inline allocation of objects

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

PLDI '97: Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation

May 1997

365 pages

ISBN:0897919076

DOI:10.1145/258915

Chairmen:
Marina Chen
Boston Univ., Boston, MA
,
Ron K. Cytron
Washington Univ., St. Louis, MO
,
Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ

ACM SIGPLAN Notices Volume 32, Issue 5
May 1997
365 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/258916
Chairmen:
Ron K. Cytron
Washington Univ., St. Louis, MO
,
Marina Chen
Boston Univ., Boston, MA
,
Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ
Issue’s Table of Contents

Copyright © 1997 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 May 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI97

Sponsor:

SIGPLAN

PLDI97: Conference on Programming Language

June 16 - 18, 1997

Nevada, Las Vegas, USA

Acceptance Rates

PLDI '97 Paper Acceptance Rate 31 of 158 submissions, 20%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
661
Total Downloads

Downloads (Last 12 months)86
Downloads (Last 6 weeks)19

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lam CParreaux L(2024)Being Lazy When It CountsFunctional and Logic Programming10.1007/978-981-97-2300-3_11(188-216)Online publication date: 15-May-2024
https://dl.acm.org/doi/10.1007/978-981-97-2300-3_11
Bruno RJovanovic VWimmer CAlonso GFreund SYahav E(2021)Compiler-assisted object inlining with value fieldsProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454034(128-141)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454034
Xu SBremner DHeidinga DBlackburn SBockisch CHaupt MHosking TRajan HSrisa-an WGrimmer MWelc A(2017)Fusing method handle graphs for efficient dynamic JVM language implementationsProceedings of the 9th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages10.1145/3141871.3141874(18-27)Online publication date: 24-Oct-2017
https://dl.acm.org/doi/10.1145/3141871.3141874
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
Matsakis NHerman DLomov D(2014)Typed objects in JavaScriptACM SIGPLAN Notices10.1145/2775052.266109550:2(125-134)Online publication date: 14-Oct-2014
https://dl.acm.org/doi/10.1145/2775052.2661095
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
Matsakis NHerman DLomov DBlack ATratt L(2014)Typed objects in JavaScriptProceedings of the 10th ACM Symposium on Dynamic languages10.1145/2661088.2661095(125-134)Online publication date: 20-Oct-2014
https://dl.acm.org/doi/10.1145/2661088.2661095
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
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