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

Article

Message Dispatch on Pipelined Processors

Authors:

Jan VitekAuthors Info & Claims

ECOOP '95: Proceedings of the 9th European Conference on Object-Oriented Programming

Pages 253 - 282

Published: 07 August 1995 Publication History

Abstract

Object-oriented systems must implement message dispatch efficiently in order not to penalize the object-oriented programming style. We characterize the performance of most previously published dispatch techniques for both statically- and dynamically-typed languages with both single and multiple inheritance. Hardware organization (in particular, branch latency and superscalar instruction issue) significantly impacts dispatch performance. For example, inline caching may outperform C++-style "vtables" on deeply pipelined processors even though it executes more instructions per dispatch.We also show that adding support for dynamic typing or multiple inheritance does not significantly impact dispatch speed for most techniques, especially on superscalar machines. Instruction space overhead (calling sequences) can exceed the space cost of data structures (dispatch tables), so that minimal table size may not imply minimal run-time space usage.

References

[1]

Ole Agesen, Jens Palsberg, and Michael I. Schwartzbach. Type Inference of SELF: Analysis of Objects with Dynamic and Multiple Inheritance. In ECOOP '93 Conference Proceedings , p. 247-267. Kaiserslautern, Germany, July 1993.

[2]

Ole Agesen and Urs Hölzle. Type Feedback vs. Concrete Type Inference: A Comparison of Optimization Techniques for Object-Oriented Languages . Technical Report TRCS 95-04, Department of Computer Science, UCSB, March 1995.

[3]

Eric Amiel, Olivier Gruber, and Eric Simon. Optimizing Multi-Method Dispatch Using Compressed Dispatch Tables. In OOPSLA '94 Conference Proceedings , pp. 244-258, October 1994. Published as SIGPLAN Notices 29(10), October 1994.

[4]

P. André and J.-C. Royer. Optimizing Method Search with Lookup Caches and Incremental Coloring. OOPSLA '92 Conference Proceedings , Vancouver, Canada, October 1992. Published as SIGPLAN Notices 27(10), October 1992.

[5]

Apple Computer, Inc. Object Pascal User's Manual . Cupertino, 1988.

[6]

Brad Calder and Dirk Grunwald. Reducing Indirect Function Call Overhead in C++ Programs. In 21st Annual ACM Symposium on Principles of Programming Languages , p. 397-408, January 1994.

[7]

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

[8]

Craig Chambers, David Ungar, Bay-Wei Chang, and Urs Hölzle. Parents are Shared Parts: Inheritance and Encapsulation in SELF. Lisp and Symbolic Computation 4(3), Kluwer Academic Publishers, June 1991.

[9]

T. Conroy and E. Pelegri-Llopart. An Assessment of Method-Lookup Caches for Smalltalk-80 Implementations. In {GR83}.

[10]

Cypress Semiconductors. CY7C601 SPARC processor , 1990.

[11]

P. Dencker, K. Dürre, and J. Heuft. Optimization of Parser Tables for Portable Compilers. TOPLAS 6(4):546-572, 1984.

[12]

Karel Driesen, Urs Hölzle. Minimizing Row Displacement Dispatch Tables. Technical Report TRCS 95-05, Department of Computer Science, UCSB, March 1995.

[13]

O.-J. Dahl and B. Myrhaug. Simula Implementation Guide . Publication S47, Norwegian Computing Center, Oslo, March 1973.

[14]

L. Peter Deutsch and Alan Schiffman. Efficient Implementation of the Smalltalk-80 System. Proceedings of the 11th Symposium on the Principles of Programming Languages , Salt Lake City, UT, 1984.

[15]

R. Dixon, T. McKee, P. Schweitzer, and M. Vaughan. A Fast Method Dispatcher for Compiled Languages with Multiple Inheritance. OOPSLA '89 Conference Proceedings , pp. 211-214, New Orleans, LA, October 1989. Published as SIGPLAN Notices 24(10), October 1989.

[16]

Karel Driesen. Selector Table Indexing and Sparse Arrays. OOPSLA '93 Conference Proceedings , p. 259-270, Washington, D.C., 1993. Published as SIGPLAN Notices 28(10), September 1993.

[17]

Karel Driesen. Method Lookup Strategies in Dynamically-Typed Object-Oriented Programming Languages . Master's Thesis, Vrije Universiteit Brussel, 1993.

[18]

P. Dussud. TICLOS: An implementation of CLOS for the Explorer Family. OOPSLA '89 Conference Proceedings , pp. 215-220, New Orleans, LA, October 1989. Published as SIGPLAN Notices 24(10), October 1989.

[19]

Margaret A. Ellis and Bjarne Stroustrup. The Annotated C++ Reference Manual . Addison-Wesley, Reading, MA, 1990.

[20]

Mary F. Fernandez. Simple and effective link-time optimization of Modula-3 programs. To appear in Proceedings of the SIGPLAN '95 Conference on Programming Language Design and Implementation , 1995.

[21]

Charles D. Garrett, Jeffrey Dean, David Grove, and Craig Chambers. Measurement and Application of Dynamic Receiver Class Distributions . Technical Report CSE-TR- 94-03-05, University of Washington, February 1994.

[22]

Adele Goldberg and David Robson. Smalltalk-80: The Language and its Implementation . Second Edition, Addison-Wesley, Reading, MA, 1985.

[23]

Linley Gwennap. Digital leads the pack with 21164. Microprocessor Report 8(12), September 12, 1994.

[24]

John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach . Morgan Kaufmann Publishers Inc. 1990.

[25]

Urs Hölzle, Craig Chambers, and David Ungar. Optimizing Dynamically-Typed Object-Oriented Languages with Polymorphic Inline Caches. In ECOOP '91 Conference Proceedings , Geneva, 1991. Published as Springer Verlag Lecture Notes in Computer Science 512, Springer Verlag, Berlin, 1991.

[26]

Urs Hölzle and David Ungar. Optimizing dynamically-dispatched calls with run-time type feedback. In PLDI '94 Conference Proceedings , pp. 326-335, Orlando, FL, June 1994. Published as SIGPLAN Notices 29(6), June 1994.

[27]

Urs Hölzle. Adaptive Optimization for Self: Reconciling High Performance with Exploratory Programming . Ph.D. Thesis, Technical Report STAN-CS-TR-94-1520, Department of Computer Science, Stanford University, 1994.

[28]

Daniel H. Ingalls. A simple technique for handling multiple polymorphism. OOPSLA '86 Conference Proceedings , p. 347-349, Portland, OR., 1986. Published as SIGPLAN Notices 21(11), November 1986.

[29]

Gregor Kiczales and Louis Rodriguez. Efficient Method Dispatch in PCL. Proc. ACM Conference on Lisp and Functional Programming , 1990. Also in {Pae93}.

[30]

Glenn Krasner. Smalltalk-80: Bits of History, Words of Advice . Addison-Wesley, Reading, MA, 1983.

[31]

Stein Krogdahl. Multiple inheritance in Simula-like languages. BIT 25, p. 318-326, 1985.

[32]

S. Milton and Heinz W. Schmidt. Dynamic Dispatch in Object-Oriented Languages . Technical Report TR-CS-94-02, The Australian National University, Canberra, January 1994.

[33]

MIPS Inc. R4000 Technical Brief, 1992.

[34]

MIPS Inc. R10000 Technical Brief, September 1994.

[35]

Nicholas Oxhøy, Jens Palsberg, and Michael I. Schwartzbach. Making Type Inference Practical. In ECOOP '92 Conference Proceedings , p. 329-349, Utrecht, The Netherlands, June/July 1992.

[36]

Andreas Paepcke (ed.). Object-Oriented Programming: The CLOS Perspective , MIT Press, 1993.

[37]

John Plevyak and Andrew A. Chien. Precise concrete type inference for object-oriented languages. In OOPSLA '94 Conference Proceedings , pp. 324-340, October 1994. Published as SIGPLAN Notices 29(10), October 1994.

[38]

William Pugh and Grant Weddell. Two-Directional Record Layout for Multiple Inheritance. In Proceedings of the SIGPLAN '90 Conference on Programming Language Design and Implementation , p. 85-91, White Plains, NY, June, 1990. Published as SIGPLAN Notices 25(6), June 1990.

[39]

John Rose. Fast Dispatch Mechanisms for Stock Hardware. OOPSLA'88 Conference Proceedings , p. 27-35, San Diego, CA, November 1988. Published as SIGPLAN Notices 23(11), November 1988.

[40]

David Ungar and David Patterson. Berkeley Smalltalk: Who Knows Where the Time Goes? In {GR83}.

[41]

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

[42]

David Ungar and David Patterson. What Price Smalltalk? In IEEE Computer 20(1), January 1987.

[43]

Jan Vitek and R. N. Horspool. Taming Message Passing: Efficient Method Look-Up for Dynamically-Typed Languages. In ECOOP '94 Conference Proceedings , Bologna, Italy, 1994.

[44]

Jan Vitek and R.N. Horspool, Fast Constant-Time Type Inclusion Tests , Unpublished manuscript, 1995.

[45]

Jan Vitek. Compact Dispatch Tables for Dynamically-Typed Object-Oriented Languages . M.S. Thesis, University of Victoria, B.C., forthcoming.

[46]

Jan Vitek, R. N. Horspool, and J. Uhl. Compile-time analysis of object-oriented programs. Proc. CC'92, 4th International Conference on Compiler Construction , pp. 236-250, Paderborn, Germany, Springer-Verlag, 1992.

Cited By

Strandh RFeeley MVerna D(2014)Fast Generic Dispatch for Common LispProceedings of ILC 2014 on 8th International Lisp Conference10.1145/2635648.2635654(89-96)Online publication date: 14-Aug-2014
https://dl.acm.org/doi/10.1145/2635648.2635654
Sonntag BColnet D(2014)Efficient compilation strategy for object-oriented languages under the closed-world assumptionSoftware—Practice & Experience10.1002/spe.217444:5(565-592)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1002/spe.2174
Ducournau R(2011)Implementing statically typed object-oriented programming languagesACM Computing Surveys10.1145/1922649.192265543:3(1-48)Online publication date: 29-Apr-2011
https://dl.acm.org/doi/10.1145/1922649.1922655
Show More Cited By

Recommendations

Evaluation of scheduling techniques on a SPARC-based VLIW testbed
MICRO 30: Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture

The performance of Very Long Instruction Word (VLIW) microprocessors depends on the close cooperation between the compiler and the architecture. This paper evaluates a set of important compilation techniques and related architectural features for VLIW ...
Realization of multimethods in single dispatch object oriented languages

The need for multimethods is preeminent in the domain of object-oriented programming. However, multimethods are far from universally acknowledged. Commonly used languages - C++, Java & C# - are single dispatching languages. In this paper, we demonstrate ...
Microparallel processors

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ECOOP '95: Proceedings of the 9th European Conference on Object-Oriented Programming

August 1995

470 pages

ISBN:3540601600

Editor:
Walter G. Olthoff

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 07 August 1995

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Strandh RFeeley MVerna D(2014)Fast Generic Dispatch for Common LispProceedings of ILC 2014 on 8th International Lisp Conference10.1145/2635648.2635654(89-96)Online publication date: 14-Aug-2014
https://dl.acm.org/doi/10.1145/2635648.2635654
Sonntag BColnet D(2014)Efficient compilation strategy for object-oriented languages under the closed-world assumptionSoftware—Practice & Experience10.1002/spe.217444:5(565-592)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1002/spe.2174
Ducournau R(2011)Implementing statically typed object-oriented programming languagesACM Computing Surveys10.1145/1922649.192265543:3(1-48)Online publication date: 29-Apr-2011
https://dl.acm.org/doi/10.1145/1922649.1922655
Ducournau R(2008)Perfect hashing as an almost perfect subtype testACM Transactions on Programming Languages and Systems10.1145/1391956.139196030:6(1-56)Online publication date: 30-Oct-2008
https://dl.acm.org/doi/10.1145/1391956.1391960
Cheadle AField ANystrom-Persson JGregg DAdve VBershad B(2008)A method specialisation and virtualised execution environment for JavaProceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments10.1145/1346256.1346264(51-60)Online publication date: 5-Mar-2008
https://dl.acm.org/doi/10.1145/1346256.1346264
Gil JZibin Y(2007)Efficient dynamic dispatching with type slicingACM Transactions on Programming Languages and Systems10.1145/1290520.129052530:1(5-es)Online publication date: 1-Nov-2007
https://dl.acm.org/doi/10.1145/1290520.1290525
Preußer TZabel MSpallek RBollella G(2007)Enabling constant-time interface method dispatch in embedded Java processorsProceedings of the 5th international workshop on Java technologies for real-time and embedded systems10.1145/1288940.1288969(196-205)Online publication date: 26-Sep-2007
https://dl.acm.org/doi/10.1145/1288940.1288969
Zibin YGil J(2002)Fast algorithm for creating space efficient dispatching tables with application to multi-dispatchingACM SIGPLAN Notices10.1145/583854.58243437:11(142-160)Online publication date: 4-Nov-2002
https://dl.acm.org/doi/10.1145/583854.582434
Zibin YGil JIbrahim MMatsuoka S(2002)Fast algorithm for creating space efficient dispatching tables with application to multi-dispatchingProceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications10.1145/582419.582434(142-160)Online publication date: 4-Nov-2002
https://dl.acm.org/doi/10.1145/582419.582434
Mehta NMedvidovic NPhadke SGhezzi CJazayeri MWolf A(2000)Towards a taxonomy of software connectorsProceedings of the 22nd international conference on Software engineering10.1145/337180.337201(178-187)Online publication date: 1-Jun-2000
https://dl.acm.org/doi/10.1145/337180.337201
Show More Cited By

View Options

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

Media

Figures

Other

Tables

View Table of Contents