Efficient implementation of Java interfaces: Invokeinterface considered harmless

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. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 2: Bowen Alpern , C. R. Attanasio , Anthony Cocchi , Derek Lieber , Stephen Smith , Ton Ngo , John J. Barton , Susan Flynn Hummel , Janice C. Sheperd , Mark Mergen, Implementing jalapeño in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.314-324, November 01-05, 1999, Denver, Colorado, United States
• 3: B. Alpern, A. Cocchi, and D. Grove. Dynamic type checking in Jalapeno. In USENIX Java Virtual Machine Research and Technology Symposium, Apr. 2001.
• 4: Pascal André , Jean-Claude Royer, Optimizing method search with lookup caches and incremental coloring, conference proceedings on Object-oriented programming systems, languages, and applications, p.110-126, October 18-22, 1992, Vancouver, British Columbia, Canada
• 5: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.47-65, October 2000, Minneapolis, Minnesota, United States
• 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. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
• 9: Craig Chambers , David Ungar, Interactive type analysis and extended message splitting; optimizing dynamically-typed object-oriented programs, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.150-164, June 1990, White Plains, New York, United States
• 10: Brad J Cox, Object oriented programming: an evolutionary approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 11: Jeffrey Adgate Dean , Craig Chambers, Whole-program optimization of object-oriented languages, 1996
• 12: David Detlefs , Ole Agesen, Inlining of Virtual Methods, Proceedings of the 13th European Conference on Object-Oriented Programming, p.258-278, June 14-18, 1999
• 13: L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
• 14: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 15: R. Dixon , T. McKee , M. Vaughan , P. Schweizer, A fast method dispatcher for compiled languages with multiple inheritance, Conference proceedings on Object-oriented programming systems, languages and applications, p.211-214, October 02-06, 1989, New Orleans, Louisiana, United States
• 16: Karel Driesen, Selector table indexing & sparse arrays, ACM SIGPLAN Notices, v.28 n.10, p.259-270, Oct. 1, 1993
• 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.
• 20: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 21: David Grove , Jeffrey Dean , Charles Garrett , Craig Chambers, Profile-guided receiver class prediction, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.108-123, October 15-19, 1995, Austin, Texas, United States
• 22: Urs Hölzle , Craig Chambers , David Ungar, Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches, Proceedings of the European Conference on Object-Oriented Programming, p.21-38, July 15-19, 1991
• 23: Urs Hölzle , Craig Chambers , David Ungar, Debugging optimized code with dynamic deoptimization, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.32-43, June 15-19, 1992, San Francisco, California, United States
• 24: Urs Hölzle , David Ungar, Optimizing dynamically-dispatched calls with run-time type feedback, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.326-336, June 20-24, 1994, Orlando, Florida, United States
• 25: IBM Research, 2001. http://www.research.ibm.com/hyperspace/.
• 26: Kazuaki Ishizaki , Motohiro Kawahito , Toshiaki Yasue , Hideaki Komatsu , Toshio Nakatani, A study of devirtualization techniques for a Java Just-In-Time compiler, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.294-310, October 2000, Minneapolis, Minnesota, United States
• 27: Ralph E. Johnson , Justin O. Graver , Laurance W. Zurawski, TS: an optimizing compiler for smalltalk, Conference proceedings on Object-oriented programming systems, languages and applications, p.18-26, September 25-30, 1988, San Diego, California, United States
• 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: Glenn Krasner, Smalltalk-80: bits of history, words of advice, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 31: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 32: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 33: Andrew C. Myers, Bidirectional object layout for separate compilation, ACM SIGPLAN Notices, v.30 n.10, p.124-139, Oct. 17, 1995
• 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: Massimiliano Poletto , Vivek Sarkar, Linear scan register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.5, p.895-913, Sept. 1999 [doi>10.1145/330249.330250]
• 36: Todd A. Proebsting, Simple and efficient BURS table generation, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.331-340, June 15-19, 1992, San Francisco, California, United States
• 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: Jan Vitek , R. Nigel Horspool, Compact Dispatch Tables for Dynamically Typed Object Oriented Languages, Proceedings of the 6th International Conference on Compiler Construction, p.309-325, April 24-26, 1996
• 45: Jan Vitek , R. Nigel Horspool, Taming Message Passing: Efficient Method Look-Up for Dynamically Typed Languages, Proceedings of the 8th European Conference on Object-Oriented Programming, p.432-449, July 04-08, 1994

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces

General Terms:
Design, Experimentation, Languages, Performance