Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/207110.207119acmconferencesArticle/Chapter ViewAbstractPublication PagespldiConference Proceedingsconference-collections
Article
Free access

Selective specialization for object-oriented languages

Published: 01 June 1995 Publication History

Abstract

Dynamic dispatching is a major source of run-time overhead in object-oriented languages, due both to the direct cost of method lookup and to the indirect effect of preventing other optimizations. To reduce this overhead, optimizing compilers for object-oriented languages analyze the classes of objects stored in program variables, with the goal of bounding the possible classes of message receivers enough so that the compiler can uniquely determine the target of a message send at compile time and replace the message send with a direct procedure call. Specialization is one important technique for improving the precision of this static class information: by compiling multiple versions of a method, each applicable to a subset of the possible argument classes of the method, more precise static information about the classes of the method's arguments is obtained. Previous specialization strategies have not been selective about where this technique is applied, and therefore tended to significantly increase compile time and code space usage, particularly for large applications. In this paper, we present a more general framework for specialization in object-oriented languages and describe a goal directed specialization algorithm that makes selective decisions to apply specialization to those cases where it provides the highest benefit. Our results show that our algorithm improves the performance of a group of sizeable programs by 65% to 275% while increasing compiled code space requirements by only 4% to 10%. Moreover, when compared to the previous state-of-the-art specialization scheme, our algorithm improves performance by 11% to 67% while simultaneously reducing code space requirements by 65% to 73%.

References

[1]
Eric Amlel, Olivier Gruber, and Eric Simon. Optimizing Multi-Method Dispatch Using Compressed Dispatch Tables. in Proceedings OOPSLA '94, pages 244-258, Portland, Oregon, October 1994.]]
[2]
Craig Chambers and David Ungar. Customization: Optimizing Compiler Technology for Self, A Dynamically-Typed Object-Oriented Programming Language. SiGPLAN Notices, 24(7):146-160, July 1989. In Proceedings of the ACM SIGPLAN '89 Conference on Programming Language Design and Implementation.]]
[3]
Craig Chambers and David Ungar. Making Pure Object-Oriented Languages Practical. In Proceedings OOPSLA '91, pages 1-15, November 1991. Published as ACM SIGPLAN Notices, volume 26, number t 1.]]
[4]
Craig Chambers. The Design and Implementation of the SELF Compiler, an Optimizing Compiler for Object-Oriented Programming Languages. PhD thesis, Stanford University, March 1992.]]
[5]
Craig Chambers. The Cecil Language: Specification and Rationale. Technical Report TR-93-03-05, Department of Computer Science and Engineering. University of Washington, March 1993.]]
[6]
Craig Chambers, David Ungar, and Elgin Lee. An Efficient Implementation of SELF- a Dynamically-Typed Object-Oriented Language Based on Prototypes. In Proceedings OOPSLA '89, pages 49-70, October 1989. Published as ACM SIGPLAN Notices, volume 24, number 10.]]
[7]
Craig Chambers, Jeffrey Dean, and David Grove. A Framework for Selective Recompilation in the Presence of Complex Intermodule Dependencies. In I7th International Conference on Software Engineering, Seattle, WA, April 1995.]]
[8]
Weimin Chen, Volker Turau, and Wolfgang Klas. Efficient Dynamic Look-up Strategy for Multi-Methods. In M. Tokoro and R. Pareschi, editors, Proceedings ECOOP '94, pages 408--431, Bologna, Italy, July 1994. Springer-Verlag.]]
[9]
Keith D. Cooper, Mary W. Hall, and Ken Kennedy. Procedure Cloning. In Proceedings of 1992 IEEE International Conference on Computer Languages, pages 96- 105, Oakland, CA, April 1992.]]
[10]
Jeffrey Dean and Craig Chambers. Towards Better Inlining Decisions Using Inlining Trials. In Proceedings of the A CM Conference on LISP and Functional Programming '94, pages 273-282, Orlando, FL, June 1994.]]
[11]
Jeffrey Dean, David Grove, and Craig Chambers. Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis. In Proceedings ECOOP '95, Aarhus, Denmark, August 1995. Springer-Vertag.]]
[12]
Charlie Garrett, Jeffrey Dean, David Grove, and Craig Chambers. Measurement and Application of Dynamic Receiver Class Distributions. Technical Report UW-CS 94-03- 05, University of Washington, March 1994.]]
[13]
Dan Grove and Linda Torczon. Interprocedural Constant Propagation: A Study of Jump Function Implementations. SIGPLAN Notices, 28(6):90-99, June 1993. In Proceedings of the A CM SIGPLAN '93 Conference on Programming Language Design and Implementation.]]
[14]
Urs Holzle and David Ungar. Optimizing Dynamically-Dispatched Calls with Run-Time Type Feedback. SIGPLAN Notices, 29(6):326-336, June 1994. In Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation.]]
[15]
Urs HOlzle, Craig Chambers, and David Ungar. Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches. In P. America, editor, Proceedings ECOOP '91, LNCS 512, pages 21-38, Geneva, Switzerland, July 1991. Sprmger-Vertag.]]
[16]
Daniel H. H. Ingalls. A Simple Technique for Handling Multiple Polymorphism. In Proceedings OOPSLA '86, pages 347-349, November 1986. Published as ACM SIGPLAN Notices, volume 21, number 11.]]
[17]
Neil D. Jones, Carstein K. Gomarde, and Peter Sestoft. Partial Evaluation and Automatic Program Generation. Prentice Hall, New York, NY, 1993.]]
[18]
M. Katz and D. Weise. Towards a New Perspective on Partial Evaluation. In Proceedings of the Workshop on Partial Evaluation and Semantics-Based Program Manipulation '92, pages 29-36. Yale University, 1992.]]
[19]
Gregor Kiczales and Luis Rodriguez. Efficient Method Dispatch in PCL. Technical Report SSL 89-95, Xerox PARC Systems Sciences Laboratory, 1989.]]
[20]
Michael F. Kilian. Why Trellis/Owl Runs Fast. Unpublished manuscript, March 1988.]]
[21]
Doug Lea. Customization in C++. In Proceedings of the 1990 Usenix C++ Conference, San Francisco, CA, Aprfi 1990.]]
[22]
Chu-Cheow Lim and Andreas Stolcke. Sather Language Design and Performance Evaluation. Technical Report TR 91-034, International Computer Science Institute, May 1991.]]
[23]
Jens Palsberg and Michael I. Schwartzbach. Object-Oriented Type Inference. In Proceedings OOPSLA '91, pages 146-t61, November 1991. Published as ACM SIGPLAN Notices, volume 26, number 11.]]
[24]
Hemant D. Pande and Barbara G. Ryder. Static Type Determination for C++. in Proceedings of Sixth USENIX C+ + Technical Conference, 1994.]]
[25]
John Plevyak and Andrew A. Chien. Precise Concrete Type Inference for Object-Oriented Languages. in Proceedings OOPSLA '94, pages 324-340, Portland, Oregon, October 1994.]]
[26]
E. Ruf and D. Weise. Using Types to Avoid Redundant Specialization. In Proceedings of the Symposium on Partial Evaluation and Semantics'Based Program Manipulation '91, pages 32t-333. ACM, 1991.]]

Cited By

View all
  • (2024)Type-Based Gradual Typing Performance OptimizationProceedings of the ACM on Programming Languages10.1145/36329318:POPL(2667-2699)Online publication date: 5-Jan-2024
  • (2024)Partial program analysis for staged compilation systemsFormal Methods in System Design10.1007/s10703-024-00458-xOnline publication date: 13-Jun-2024
  • (2023)A type-directed, dictionary-passing translation of method overloading and structural subtyping in Featherweight Generic GoJournal of Functional Programming10.1017/S095679682300004733Online publication date: 9-Oct-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
PLDI '95: Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation
June 1995
335 pages
ISBN:0897916972
DOI:10.1145/207110
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1995

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

PLDI95
Sponsor:

Acceptance Rates

PLDI '95 Paper Acceptance Rate 28 of 105 submissions, 27%;
Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)187
  • Downloads (Last 6 weeks)44
Reflects downloads up to 13 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Type-Based Gradual Typing Performance OptimizationProceedings of the ACM on Programming Languages10.1145/36329318:POPL(2667-2699)Online publication date: 5-Jan-2024
  • (2024)Partial program analysis for staged compilation systemsFormal Methods in System Design10.1007/s10703-024-00458-xOnline publication date: 13-Jun-2024
  • (2023)A type-directed, dictionary-passing translation of method overloading and structural subtyping in Featherweight Generic GoJournal of Functional Programming10.1017/S095679682300004733Online publication date: 9-Oct-2023
  • (2022)Principles of Staged Static+Dynamic Partial AnalysisStatic Analysis10.1007/978-3-031-22308-2_4(44-73)Online publication date: 2-Dec-2022
  • (2021)Characterizing Massively Parallel Polymorphism2021 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)10.1109/ISPASS51385.2021.00037(205-216)Online publication date: Mar-2021
  • (2020)Contextual dispatch for function specializationProceedings of the ACM on Programming Languages10.1145/34282884:OOPSLA(1-24)Online publication date: 13-Nov-2020
  • (2020)Feedback-driven semi-supervised synthesis of program transformationsProceedings of the ACM on Programming Languages10.1145/34282874:OOPSLA(1-30)Online publication date: 13-Nov-2020
  • (2020)Regex matching with counting-set automataProceedings of the ACM on Programming Languages10.1145/34282864:OOPSLA(1-30)Online publication date: 13-Nov-2020
  • (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
  • (2020)Dynamic dispatch of context-sensitive optimizationsProceedings of the ACM on Programming Languages10.1145/34282354:OOPSLA(1-28)Online publication date: 13-Nov-2020
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media