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

Article

Efficient implementation of Java interfaces: Invokeinterface considered harmless

Authors:

Anthony Cocchi,

David GroveAuthors Info & Claims

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

Pages 108 - 124

https://doi.org/10.1145/504282.504291

Published: 01 October 2001 Publication History

Abstract

Single superclass inheritance enables simple and efficient table-driven virtual method dispathc. However, virtual method table dispatch does not handle multiple inheritance and interfaces. This complication has led to a widespread misimpression that interface method dispatch is inherently inefficient. This paper argues that with proper implementation techniques, Java interfaces need not be a source of significant performance degradation.

References

[1]

B. Alpern, C. R. Attanasio, J. J. Barton, M. G. Burke, P. Cheng, J.-D. Choi, A. Cocchi, S. J. Fink, D. Grove, M. Hind, S. F. Hummel, D. Lieber, V. Litvinov, M. F. Mergen, T. Ngo, J. R. Russel, V. Sarkar, M. J. Serrano, J. C. Shepherd, S. E. Smith, V. C. Sreedhar H. Srinivasan, and J. Whaley, The Jalapeno Virtual machine, IBM System Jounal, 39(1), 2000.]]

Digital Library

[2]

B. Alpern, D. Attanasio, J. J. Barton, A. Cocchi, D. Lieber, S. Smith, and T. Ngo. Implementing Jalapeno in Java. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 314-324, 1999.]]

Digital Library

[3]

B. Alpern, A. Cocchi, and D. Grove. Dynamic type checking in Jalapeno. In USENIX Java Virtual Machine Research and Technology Symposium, Apr. 2001.]]

Digital Library

[4]

P. Andre and J.-C. Royer. Optimizing method search with lookup caches and incremental coloring. In Proceedings OOPSLA '92 pages 110-126, Oct. 1992. Published as ACM SIGPLAN Notices, volume 27, number 10.]]

Digital Library

[5]

M. Arnold, S. Fink, D. Grove, M. Hind, and P. Sweeney, Adaptive optimization in the Jalapeno JVM. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Oct. 2000.]]

Digital Library

[6]

G. J. Chaitin, M. Auslander, A. Chandra, J. Cocke, M. Hopkins, and P. Markstein, Register allocation via coloring. Computer Languages 6, pages 47-57, 1981.]]

[7]

C. Chambers, J. Dean, and D. Grove. Whole-program optimization of object-oriented languages. Technical Report UW-CSE-96-06-02. Department of Computer Science and Engineering. University of Washington, June 1996.]]

[8]

C. Chamebrs and D. Ungar. Customization: Optimizing compiler technology for Self, a dynamically-typed object-oriented programming language. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 146-160, July 1989, SIGPLAN Notices, 24(7).]]

Digital Library

[9]

C. Chambers and D. Ungar. Iterative type analysis and extended message splitting: Optimizing dynamically-typed object-oriented programs. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 150-164, 1990.]]

Digital Library

[10]

B. J. Cox. Object Oriented Programming: An Evolutionary Approach. Addison-Wesley, 1987.]]

Digital Library

[11]

J. Dean. Whole Program Optimization of Object-Oriented Languages. PhD thesis, University of Washington, Nov. 1996, TR-96-11-05.]]

Digital Library

[12]

D. Detlefs and O. Agesen. Inlining of virtual methods. In 13th European Conference on Object-Oriented Programming, 1999.]]

Digital Library

[13]

L. P. Deutsch and A. M. Schiffman. Efficient implementation of the Smalltalk-80 system. In 11th Annual ACM Symposium on the Principles of Programming Languages, pages 297-302, Jan. 1984.]]

Digital Library

[14]

P. F. Dietz and D. D. Sleator. Two algorithms for maintaining order in a list. Proceedings of the nineteenth annual ACM Symposium on Theory of Computing, New York City, May 25-27, 1987, pages 365-372, May 1987.]]

Digital Library

[15]

R. Dixon, T. McKee, M, Vaughan, and P. Schweizer. A fast method dispatcher for compiled languages with multiple inheritance. In Proceedings OOPSLA '89 pages 211-214, Oct. 1989. Published as ACM SIGPLAN Notices, volume 24, number 10.]]

Digital Library

[16]

K. Driesen. Selector table indexing & sparse arrays. In Proceedings OOPSLA '98, pages 259-270, Oct. 1993. published as ACM SIGPLAN Notices, volume 28, number 10.]]

Digital Library

[17]

R. Fitzgerald, T. B. Knoblock, E. Ruf, B. Steensgaard, and D. Tarditi. Marmot: An optimizing compiler for Java. Technical Report MSR-TR-99-33, Microsoft Research, June 1999.]]

[18]

E. Gagnon and L. Hendren. SableVM: A research framework for the efficient execution of Java bytecode. Technical Report Sable Technical Report No. 2000-3, School of Computer Science, McGill university, Nov. 2000.]]

[19]

E. Gagnon and L. Hendren. SableVM: A Research Framework for tge Efficient Execution of Java Bytecode. In USENIX Java Virtual Machine Research and Technology Symposium, Apr. 2001.]]

Digital Library

[20]

J. Gosling, B. Joy, and G. Steele. The Java Language Specification. Addison Wesley, 1996.]]

Digital Library

[21]

D. Grove, J. Dean, C. Garrett, and C. Chambers. Profile-guided receiver class prediction. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 108-123, Oct. 1995.]]

Digital Library

[22]

U. Holzle, C. Chambers, and D. Ungar. Optimizing dynamically-typed object-oriented languages with polymorphic inline caches. In P. America, editor, Proceedings ECOOP '91, LNCS 512, pagws 21-38, Springer-Verlag.]]

Digital Library

[23]

U. Holzle, C. chambers, and D. Ungar, Debugging optimizing code with dynamic deoptimization. In Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pages 32-43, June 1992.]]

Digital Library

[24]

U. Holzle and D. Ungar. Optimizing synamically-disparched calls with run-time type feedback. In SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 326-336, June 1994. SIGPLAN Notices, 29(6).]]

Digital Library

[25]

IBM Research, 2001. http://www.research.ibm.com/hyperspace/.]]

[26]

K. Ishizaki, M. Kawahito, T. Yasue, and H. K. and Toshio Nakatani. A study of devirtualization techniques for a Java just-in-time compiler. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Oct. 2000.]]

Digital Library

[27]

R. Johnson. TS: An optimizing compiler for Smalltalk. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 18-26, 1988.]]

Digital Library

[28]

A. Krall. Personal Communications, Sept. 1999.]]

[29]

A. Krall and R. Grafl. CACAO-a 64 bit JavaVM just-in-time compiler. Concurrency: Practice and Experience, 9(11):1017-1030, 1997.]]

[30]

G. Krasner. Smalltalk-80: Bits of History, Words of Advice. Addison-Wesley, 1983.]]

Digital Library

[31]

T. Lindholm and F. Yellin. The Java Virtual Machine Specification. The Java Series. Addison-Wesley, 1996.]]

Digital Library

[32]

T. Lindholm and F. Yellin. The Java Virtual Machine Specification Second Edition. The Java Series. Addison-Wesley, 1999.]]

Digital Library

[33]

A. C. Myers. Bidirectional object layout for separate compilation. ACM SIGPLAN Notices, 30(10):124-139, Oct. 1995.]]

Digital Library

[34]

H. Ossher and P. Tarr. Multi-dimensional separation of concerns and the hyperspace approach. In Software Arthitectures and Component Technology: The State of the Art in Research and Practice. Kluwer, 2001. to appear.]]

[35]

M. Poletto and V. Sarkar. Linear scan register allocation. ACM Transactions on Programming Languages and Systems, 21(5):895-913, Sept. 1999.]]

Digital Library

[36]

T. A. Proebsting. imple and efficient burs table generation. In SIGPLAN '92 Conference on Programming Language Design and Implementation pages 331-340, June 1992. SIGPLAN Notices 27(6).]]

Digital Library

[37]

G. Ramalingam and H. Srinivasan. Object model for Java. Technical Report 20642, IBM Research Division, Dec. 1996.]]

[38]

Y. Shuf. Personal Communication, 2001.]]

[39]

B. Stroustrup. Multiple inheritance for C++. In Proceedings of the Spring 1987 European Unix Users Group Conference, Helsinki, 1987.]]

[40]

The Apache XML Project, 2001. http://xml.apache.org/xerces-j]]

[41]

The Standard Performance Evaluation Corporation. SPEC JVM98 Benchmarks. http://www.spec.org/osg/jvm98, 1998.]]

[42]

The Standard Performance Evaluation Corporation SPEC JBB 2000. http://www,spec.org/osg/jbb2000, 2000.]]

[43]

R. Vallee-Rai. Profiling the Kaffe JIT compiler. Technical Report 1998-02, McGill University, Feb. 1998.]]

[44]

J. Vitek and N. Horspool. Compact dispatch tables for dynamically typed object oriented languages. In Proceedings of International Conference on Compiler Construction (CC'96), pages 281-293, Apr. 1996. Published as LNCS vol 1060.]]

Digital Library

[45]

J. Vitek and R. N. Horspool. Taming message passing: Efficient method look-up for dynamically typed languages. In M. Tokoro and R. Pareschi, editors, Proceedings ECOOP '94, LNCS 821, pages 432-449, Bologna, Italy, July 1994, Springer-Verlag.]]

Digital Library

Cited By

SULZMANN MWEHR S(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
https://doi.org/10.1017/S0956796823000047
Ji RXia JXiong YHu Z(2021)Generalizable synthesis through unificationProceedings of the ACM on Programming Languages10.1145/34855445:OOPSLA(1-28)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485544
Shen XZhang GDea IAndow SArroyo-Fang EGafter NGeorge JGrueter MMeijer EShivers OStumpos STempest AWarden CYang S(2021)Coarsening optimization for differentiable programmingProceedings of the ACM on Programming Languages10.1145/34855075:OOPSLA(1-27)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485507
Show More Cited By

Index Terms

Efficient implementation of Java interfaces: Invokeinterface considered harmless
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Modules / packages
      2. Language types
        Functional languages

Recommendations

Efficient implementation of Java interfaces: Invokeinterface considered harmless

Single superclass inheritance enables simple and efficient table-driven virtual method dispathc. However, virtual method table dispatch does not handle multiple inheritance and interfaces. This complication has led to a widespread misimpression that ...
3D User Interfaces: New Directions and Perspectives

Three-dimensional user interfaces (3D UIs) let users interact with virtual objects, environments, or information using direct 3D input in the physical and/or virtual space. In this article, the founders and organizers of the IEEE Symposium on 3D User ...
Transforming graphical interfaces into auditory interfaces

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

October 2001

382 pages

ISBN:1581133359

DOI:10.1145/504282

Conference Chair:
Linda Northrop
Software Engineering Institute
,
Program Chair:
John Vlissides
IBM T.J. Watson Research Center

ACM SIGPLAN Notices Volume 36, Issue 11
11/01/2001
380 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/504311
Issue’s Table of Contents

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

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

OOPSLA01

Sponsor:

SIGPLAN

OOPSLA01: ACM SIGPLAN Object Oriented Programming Systems Languages and Applications Conference

October 14 - 18, 2001

FL, Tampa Bay, USA

Acceptance Rates

OOPSLA '01 Paper Acceptance Rate 27 of 145 submissions, 19%;

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

68
Total Citations
View Citations
1,705
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

SULZMANN MWEHR S(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
https://doi.org/10.1017/S0956796823000047
Ji RXia JXiong YHu Z(2021)Generalizable synthesis through unificationProceedings of the ACM on Programming Languages10.1145/34855445:OOPSLA(1-28)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485544
Shen XZhang GDea IAndow SArroyo-Fang EGafter NGeorge JGrueter MMeijer EShivers OStumpos STempest AWarden CYang S(2021)Coarsening optimization for differentiable programmingProceedings of the ACM on Programming Languages10.1145/34855075:OOPSLA(1-27)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485507
Brotzman RZhang DKandemir MTan G(2021)SpecSafe: detecting cache side channels in a speculative worldProceedings of the ACM on Programming Languages10.1145/34855065:OOPSLA(1-28)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485506
Henry RHsu OYadav RChou SOlukotun KAmarasinghe SKjolstad F(2021)Compilation of sparse array programming modelsProceedings of the ACM on Programming Languages10.1145/34855055:OOPSLA(1-29)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485505
Muehlboeck FTate R(2021)Transitioning from structural to nominal code with efficient gradual typingProceedings of the ACM on Programming Languages10.1145/34855045:OOPSLA(1-29)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485504
Chaliasos SSotiropoulos TDrosos GMitropoulos CMitropoulos DSpinellis D(2021)Well-typed programs can go wrong: a study of typing-related bugs in JVM compilersProceedings of the ACM on Programming Languages10.1145/34855005:OOPSLA(1-30)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485500
Sulzmann MWehr S(2021)A Dictionary-Passing Translation of Featherweight GoProgramming Languages and Systems10.1007/978-3-030-89051-3_7(102-120)Online publication date: 12-Oct-2021
https://doi.org/10.1007/978-3-030-89051-3_7
Källén MWrigstad THosking AFinocchi I(2019)Performance of an OO compute kernel on the JVM: revisiting Java as a language for scientific computing applicationsProceedings of the 16th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3357390.3361026(144-156)Online publication date: 21-Oct-2019
https://dl.acm.org/doi/10.1145/3357390.3361026
Karlsson OHaller PErdweg SOliveira B(2018)Extending Scala with records: design, implementation, and evaluationProceedings of the 9th ACM SIGPLAN International Symposium on Scala10.1145/3241653.3241661(72-82)Online publication date: 17-Sep-2018
https://dl.acm.org/doi/10.1145/3241653.3241661
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten