More Web Proxy on the site http://driver.im/

Article

Free access

Iterative type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs

Authors:

Craig Chambers,

David UngarAuthors Info & Claims

PLDI '90: Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation

Pages 150 - 164

https://doi.org/10.1145/93542.93562

Published: 01 June 1990 Publication History

Abstract

Object-oriented languages have suffered from poor performance caused by frequent and slow dynamically-bound procedure calls. The best way to speed up a procedure call is to compile it out, but dynamic binding of object-oriented procedure calls without static receiver type information precludes inlining. Iterative type analysis and extended message splitting are new compilation techniques that extract much of the necessary type information and make it possible to hoist run-time type tests out of loops.

Our system compiles code on-the-fly that is customized to the actual data types used by a running program. The compiler constructs a control flow graph annotated with type information by simultaneously performing type analysis and inlining. Extended message splitting preserves type information that would otherwise be lost by a control-flow merge by duplicating all the code between the merge and the place that uses the information. Iterative type analysis computes the types of variables used in a loop by repeatedly recompiling the loop until the computed types reach a fix-point. Together these two techniques enable our SELF compiler to split off a copy of an entire loop, optimized for the common-case types.

By the time our SELF compiler generates code for the graph, it has eliminated many dynamically-dispatched procedure calls and type tests. The resulting machine code is twice as fast as that generated by the previous SELF compiler, four times faster than ParcPlace Systems Smalltalk-80,^* the fastest commercially available dynamically-typed object-oriented language implementation, and nearly half the speed of optimized C. Iterative type analysis and extended message splitting have cut the performance penalty for dynamically-typed object-oriented languages in half.

References

[1]

Afxed V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, MA, 1986.

Digital Library

[2]

Craig Chambers and David Ungar. Customization: Optimizing Compiler Technology for SELF, a Dynamically- Typed Object-Oriented Programming Language. In Proceedings of the SIGPLAN '89 Conference on Programming Language Design and Implementation, Portland, OR, June, 1989. Published as SIGPLAN Notices 24(7), July, 1989.

Digital Library

[3]

Craig Chambers, David Ungar, and Elg Lee. An Efficient Implementation of SELF, a Dynamically-Typed Object-Oriented Language Based on Prototypes. In OOPSLA '89 Conference Proceedings, pp. 49-70, New Orleans, LA, 1989. Published as SlGPLAN Notices 24(10), October, 1989.

Digital Library

[4]

L. Peter Deutsch and Allan M. Schiffman. F. fficient Implementation of the SmaUtalk-80 System. In Proceedings of the l th Annual ACM Symposium on the Principles of Programming Languages, pp. 297-302, Salt Lake City, LIT, 1984.

Digital Library

[5]

Adele Goldberg and David Robson. Smalltalk-80: The Language and Its Implementation. Addison-Wesley, Reading, MA, 1983.

Digital Library

[6]

Justin Owen Graver. Type-Checldng and Type-Inference for Object-Oriented Programming Languages. Ph.D. thesis, University of Illinois at Urbana-Champaign, 1989.

[7]

Justin O. Graver and Ralph E. Johnson. A Type System for Smalltalk. In Conference Record of the 17th Annual ACM Symposium on Principles of Programming Languages, pp. 136-150, San Francisco, CA, January, 1990.

Digital Library

[8]

Richards Louis Heintz, Jr. Low Level Optimizations for an Object-Oriented Programming Language. Master's thesis, University of Illinois at Urbana-champign, 1990.

[9]

John Hennessy. Stanford integer b=nehmarks. Personal communication, June, 1988.

[10]

Ralph E. Johnson. Type-Checking Smalltalk. In OOPS- LA '86 Conference Proceedings, pp. 315-321, Portland, OR, 1986. Published as SIGPLAN Notices 21(11), November, 1986.

Digital Library

[11]

Ralph F. Johnson, Justin O. Graver, and Lawrence W. Zurawski. 'IS: An Optimizia8 Compiler for Smalltalk. In OOPSLA '88 Conference Proceedings, pp. 18-26, San Diego, CA, 1988. Published as SIGPLAN Notices 23(11), November, 1988.

Digital Library

[12]

Elgin Lee. Object Storage and Inheritance for SELF, a Prototype-Based Object-Oriented Programming Language. F. ugineer's thesis, Stanford University, 1988.

[13]

Carl D. McConnelL The Design of the RTL System. Master's thesis, University of illinois at Urbana-Champaign, 1989.

[14]

John Mitchell Personal communication, November, 1989.

[15]

Robin Milner, Mads Torte, and Robert Harper. The Definition of Standard ML. M1T Press, Cambridge, MA, 1990.

Digital Library

[16]

Atsushi Ohori and Peter Buneman. Static Type Inference for Parametric Classes. In OOPSLA '89 Conference Proceedings, pp. 445-456, New Orleans, LA, 1989. Published as SIGPLAN Notices 24(10), October, 1989.

Digital Library

[17]

David A. Padua and Michael J. Wolfe. Advancexi Compilex Opgmizations for Supercomputers. In Communications of the ACM, pp. 1184-1201, December, 1986.

Digital Library

[18]

Jonathan Rees and William Clinger, editors. Revised Report on the Algorithmic Language Scheme. 1986.

[19]

Peter Sestoft and Harald Scndergaard. A Bibliography on Partial Evaluation. In SlGPLANNotices 23(2), Pp. 19- 27, February, 1988.

Digital Library

[20]

David Ungar. The Design and Evaluation of a High Per. formance Smalltalk System. MIT Press, Cambridge, MA, 1987.

Digital Library

[21]

David Ungar. A Performance Comparison of C, SELF, and Smalltalk Implementations. Unpublished manuscript, March, 1989.

[22]

David Ungar and Randall B. Smith. SELF: The Power of Simplicity. In OOPSLA '87 Conference Proceedings, pp. 227-241, Orlando, FL, 1987. Published as SIGPLAN Notices 22(12), December, 1987.

Digital Library

[23]

M. Wand. Complete Type Inference for Simple Objects. In Proceedings of the 2nd IEEE Symposium on Logic in Computer Science, pp. 37-44, 1987.

[24]

M. Wand. Type Inference for Record Concatenation and Multiple Inheritance. In Proceedings of the 4th IEEE Symposium on Logic in Computer Science, pp. 92-97, 1989.

Digital Library

Cited By

Sun YWang CFan GShi QZhang X(2024)Fast and Precise Static Null Exception Analysis With Synergistic PreprocessingIEEE Transactions on Software Engineering10.1109/TSE.2024.346655150:11(3022-3036)Online publication date: Nov-2024
https://doi.org/10.1109/TSE.2024.3466551
Yang BKim JMoon S(2017)ExceptionizationACM Transactions on Architecture and Code Optimization10.1145/304668114:1(1-25)Online publication date: 14-Apr-2017
https://dl.acm.org/doi/10.1145/3046681
Ungar DSmith RRyder BHailpern B(2007)SelfProceedings of the third ACM SIGPLAN conference on History of programming languages10.1145/1238844.1238853(9-1-9-50)Online publication date: 9-Jun-2007
https://dl.acm.org/doi/10.1145/1238844.1238853
Show More Cited By

Index Terms

Iterative type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
        Control structures
      2. Language types
2. Theory of computation
  1. Randomness, geometry and discrete structures
  2. Semantics and reasoning
    1. Program constructs
      1. Type structures

Recommendations

Iterative type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs

Object-oriented languages have suffered from poor performance caused by frequent and slow dynamically-bound procedure calls. The best way to speed up a procedure call is to compile it out, but dynamic binding of object-oriented procedure calls without ...
Inferable object-oriented typed assembly language
PLDI '10: Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation

A certifying compiler preserves type information through compilation to assembly language programs, producing typed assembly language (TAL) programs that can be verified for safety independently so that the compiler does not need to be trusted. There ...
Inferable object-oriented typed assembly language
PLDI '10

A certifying compiler preserves type information through compilation to assembly language programs, producing typed assembly language (TAL) programs that can be verified for safety independently so that the compiler does not need to be trusted. There ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '90: Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation

June 1990

351 pages

ISBN:0897913647

DOI:10.1145/93542

Chairman:
Bernard N. Fischer

ACM SIGPLAN Notices Volume 25, Issue 6
Jun. 1990
343 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/93548
Editor:
Marina Chen
Issue’s Table of Contents

Copyright © 1990 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 June 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

96
Total Citations
View Citations
659
Total Downloads

Downloads (Last 12 months)92
Downloads (Last 6 weeks)13

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sun YWang CFan GShi QZhang X(2024)Fast and Precise Static Null Exception Analysis With Synergistic PreprocessingIEEE Transactions on Software Engineering10.1109/TSE.2024.346655150:11(3022-3036)Online publication date: Nov-2024
https://doi.org/10.1109/TSE.2024.3466551
Yang BKim JMoon S(2017)ExceptionizationACM Transactions on Architecture and Code Optimization10.1145/304668114:1(1-25)Online publication date: 14-Apr-2017
https://dl.acm.org/doi/10.1145/3046681
Ungar DSmith RRyder BHailpern B(2007)SelfProceedings of the third ACM SIGPLAN conference on History of programming languages10.1145/1238844.1238853(9-1-9-50)Online publication date: 9-Jun-2007
https://dl.acm.org/doi/10.1145/1238844.1238853
Brandt SKnudsen J(2006)Generalising the BETA type systemECOOP ’96 — Object-Oriented Programming10.1007/BFb0053072(421-448)Online publication date: 21-May-2006
https://doi.org/10.1007/BFb0053072
Nguyen PXue J(2004)Strength reduction for loop-invariant typesProceedings of the 27th Australasian conference on Computer science - Volume 2610.5555/979922.979948(213-222)Online publication date: 1-Jan-2004
https://dl.acm.org/doi/10.5555/979922.979948
Chambers CUngar D(2004)A retrospective onACM SIGPLAN Notices10.1145/989393.98942539:4(295-312)Online publication date: 1-Apr-2004
https://dl.acm.org/doi/10.1145/989393.989425
Hazelwood KGrove DJohnson RConte THwu W(2003)Adaptive online context-sensitive inliningProceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization10.5555/776261.776289(253-264)Online publication date: 23-Mar-2003
https://dl.acm.org/doi/10.5555/776261.776289
Aycock J(2003)A brief history of just-in-timeACM Computing Surveys10.1145/857076.85707735:2(97-113)Online publication date: 1-Jun-2003
https://dl.acm.org/doi/10.1145/857076.857077
Lerner SGrove DChambers C(2002)Composing dataflow analyses and transformationsACM SIGPLAN Notices10.1145/565816.50329837:1(270-282)Online publication date: 1-Jan-2002
https://dl.acm.org/doi/10.1145/565816.503298
Lerner SGrove DChambers CLaunchbury JMitchell J(2002)Composing dataflow analyses and transformationsProceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/503272.503298(270-282)Online publication date: 16-Jan-2002
https://dl.acm.org/doi/10.1145/503272.503298
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