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

article

Free access

Efficient dynamic dispatch without virtual function tables: the SmallEiffel compiler

Authors:

Olivier Zendra,

Dominique Colnet,

Suzanne CollinAuthors Info & Claims

ACM SIGPLAN Notices, Volume 32, Issue 10

Pages 125 - 141

https://doi.org/10.1145/263700.263728

Published: 09 October 1997 Publication History

Abstract

SmallEiffel is an Eiffel compiler which uses a fast simple type inference mechanism to remove most late binding calls, replacing them by static bindings. Starting from the system's entry point, it compiles only statically living code, which saves compiling and then removing dead code. As the whole system is analyzed at compile time, multiple inheritance and genericity do not cause any overhead.SmallEiffel features a coding scheme which eliminates the need for virtual function tables. Dynamic dispatch is implemented without any array access but uses a simple static binary branch code. We show that this implementation makes it possible to use modern hardware very efficiently. It also allows us to inline more calls even when dynamic dispatch is required. Some more dispatch sites are removed after the type inference algorithm has been performed, if the different branches of a dispatch site lead to the same code.The advantage of this approach is that it greatly speeds up execution time and considerably decreases the amount of generated code.

References

[1]

Ole Kgesen. The Cartesian Product Algorithm- Simple and Precise Type Inference of Parametric Polymorphism. In Proceedings of the 9th European Conference on Object-Oriented Programming (ECOOP'95), volume 952 of Lecture Notes in Computer Sciences, pages 2-26. Springer-Verlag, i995.

[2]

Ole Agesen,Concrete Type Inference: Delivering Object-Oriented Applications. PhD thesis, Department of Computer Science of Stanford University, Published by Sun Microsystem Laboratories (SMLI TR-96-52), 1996.,

Digital Library

[3]

Ole Agesen and;Urs HSlzle. Type Feedback vs. Concrete Type inference: A Comparison of Optimization Techniques for Object- Oriented Languages. in Proceedings of lOth Annual A CM Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA'95), pages 91-107, I995.

Digital Library

[4]

Gerald Aigner and Urs H6lzle. Eliminating Virtual Function Calls in C++ Programs. In proceedings of the l Oth European Conference on Object-Oriented Programming (ECOOP'96), volume 1098 of Lecture Notes in Computer Sciences, pages 142- 166. Springer-Verlag, 1996.

Digital Library

[5]

Ole Agesen, Jens Palsberg, and Michael I. Schwartzbach. Type Inference of SELF. Analysis of Objects with Dynamic and Multi:~ ple Inheritance. in Proceedings of the 7th European Conference on Object-Oriented Pro- (zvoOP'9s), vo/um 707 of ture Notes in Computer Sciences, pages 247- 267. Springer-Verlag, 1993.

Digital Library

[6]

Alfred V. Ah0 and Jeffrey D. Ullman. Principles o/Compiler Design. Addison-Wesley, eading~ Massachusetts, 1977. ~ '

[7]

David F. Bacon and Peter F. Sweeney. Fast Static' Analysis of C++ Virtual Function Calls. In Proceedings'of llthAnnual A CM Conference on Object-Oriented Programming Systems, Languages and Applications (OOP- SLA '96), pages 324-341~, 1996.

Digital Library

[8]

Suzanne Collin, Dominique Colnet,~ and Olivier Zendra. Type Inference for Late Binding. The SmaUEiffel Compiler. In Joint Modular Languages Conference, volume 1204 of Lecture Notes in Computer Sciences, pages 67-81. Springer-Vedag, 1997.

Digital Library

[9]

Robert Cartwright and Mike Fagan. Soft Typing. in Proceedings of the A CM SIG- PLAN '91 Conference on Programming Language Design and Implementation, pages 278-292, 1991.

Digital Library

[10]

Brad Calder and Dirk Grunwald. Reducing Indirect Function Call Overhead In C++ Programs. In 21st Annual A CM Symposium on the Principles of Programming Languages, pages 397-408, :lanua~y 1994.

Digital Library

[11]

Diane Corney and,John Gough. Type Tes~ Elimination using Typeflow Analysis. in PLSA 199~ International Conference, Zurich, volume 782 of Lecture Notes in Computer Sciences, pages 137-150. Spfinget- Verlag, 1994.

[12]

Craig Chambers and David Ungar. Customization: Optimizing Compiler Technology for SELF~ a Dynamically-Typed Object- Oriented Language. In Proceedings of the A CM S{GPLAN '89 Conference on Programming Language Design and Implementation, volume 24 of SIGPLAN notices, pa~ 146- 160, 1989.

Digital Library

[13]

Jeffrey Dean, Greg DeFouw, David Grove, Vassily Litvinov, and Craig Chambers. Vortex: An Optimizing Compiler for Object- Oriented Languages. In Proceedings of 11th Annual A CM Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA '96), pages 83-100, 1996.

[14]

Jeffrey Dean, David Grove, and Craig Chambers. Optimization of Object-Oriented Programs Using Static Class Hierarchy, Analysis. In Proceedings of the 9th European, Conference on Object-Oriented Programming (ECOOP'95}, volume 952 of Lecture Notes in Computer Sciences, pages 77-101. Springer- Verlag, 1995.

Digital Library

[15]

Karel Driesen and Urs HSlzle. The Direct. Cost of Virtual Function Calls in C++. In Proceedings of 11th Annual A CM Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA'96}, pages 306-323, 1996.

Digital Library

[16]

D.M. Dhamdhere. Practical Adaptation of the Global Optimization Algorithm of Morel and Renvoise. A CM Transactions on Programming Languages and Systems, 13(2):291-294, 1991.

Digital Library

[17]

Karel Driesen, Urs Htilzle, and Jan Vitek. Message Dispatch on Pipelined Processors. in Proceedings of the #th European Conference on Object-Oriented Programming (EGOOP'95), volume 952 of Lecture Notes in Computer Sciences, pages 253-282. Springer- Verlag, 1995.

Digital Library

[18]

Amer Diwan, J. Eliot B. Moss, and Kathryn' S. McKinley. Simple and Effective Analysis of Statically-Typed Object- Oriented Programs. in Rroceedings of 11th Annual A CM Conference on Object-Oriented Programming Systems, Languages and Appli. cations (OOPSLA '96}, pages 292-305, 1996.

[19]

Peter L. Deutsch and Alan Sehiffman, Efficient Implementation of the Smalltalk-80 System. In 11th Annual A GM Symposium on the Principles of Programming Languages~ 1984.

Digital Library

[20]

Jonathan Eifrig, Scott Smith, and Valery Trifonov. Sound Polymorphic Type Inference for Objects. In Proceedings of lflth Annual A CM Conference on Object.Oriented Programming Systems, Languages and Applications (OOPSLA '95), pages 169-184, 1995.

Digital Library

[21]

J. Graver and R. Johnson. A Type System for Smalltalk. In 17th Annual A GM 5ympo. slum on the Principles of Programming Lan. guages, pages 139-150, 1990.

[22]

A. Goldbe~g and D. Robson. Smalltalk. 80, the Language and its Implementation. Addison-Wesley, Reading, Massachusetts, 1983.

Digital Library

[23]

Urs H61zle, Craig Chambers, and David Ungar. Optimizing Dynamically-Typed Object- Oriented Languages With Polymorphic Inline Caches. In Proceedings of the 5th European Conference on Object-Oriented Programming (EGOOP'91), volume 512 of Lecture Notes in Computer Sciences, pages 21- 38. Springer-Verlag, 1991.

Digital Library

[24]

Urs H61zle and David Ungar. Do Objec~ Oriented Languages Need Special Hardware Support ? in Proceedings of the 9th European Conference on Object-Oriented Programming (ECOOP'95), volume 952 of Lecture Notes in Computer :~ciences, pages 283-302. Springer- Verlag, 1995.

Digital Library

[25]

Bill Joy James Gosling and Guy Steele. The Java Language Specification. Addison Weseey, 1996.

Digital Library

[26]

lens Knoop, Oliver Ruthing, and Bernhard Steffen. Partial Dead Code Elimination. In Proceedings of the ACM SIGPLAN '9~ Conference on Programming Language Design and Implementation, pages 147-10000, 1994.

Digital Library

[27]

Bertrand Meyer. Object-oriented Software Construction. Prentice Hall, 1988.

Digital Library

[28]

Bertrand Meyer. Eiffel, The Language. Prentice Hall, 1994.

Digital Library

[29]

R. Milner. A Theory of Type Polymorphism in Programming. In Journal of Computer and System Sciences, pages 348-375, 1978.

[30]

G. Masini, A. Napoli, D. Colnet, D. L6onard, and K. Tombre. Object Oriented Languages. Academic Press Limited, London, 1991.

[31]

John Plevyak and Andrew A. Chien. Precise Concrete Type Inference for Object-Oriented languages." In Proceedings of 9th Annual A CM Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA '9~), pages 324-340, 1994.

Digital Library

[32]

Jens Palsberg and Michael I. Schwartzbach. Object-Oriented Type Inference. In Proceedings of 6th Annual A CM Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA'91), pages 146-161, 1991.

Digital Library

[33]

J. Palsberg and M.I. Schwartzbach. Safety Analysis Versus Type Inference for partial Types. Information Processing Letters, pages i75-180, 1992.

Digital Library

[34]

John R. Rose. Fas~ Dispatch Mechanisms for Stock Hardware. In Proceedings of 3rd Annual A CM Conference on Object-Oriented Programming Systems, Languages and Applications (OOPSLA '88), pages 27-35, 1988.

Digital Library

[35]

N. Suzuki and M. Terada. Creating Efficient System for Object-Oriented Languages. In 11th Annual A CM Symposium on the Principles of Pro#ramming Languages, pages 290- 296, 1984.

Digital Library

[36]

B. S~roustrup. The C++ Programming Language. Addison-Wesley Series in Computer Science, 1986.

Digital Library

[37]

N. Suzuki. Inferring Types in Smalltalk. In Eighth Symposium on Principles of Programming Languages, pages 187-199, 1981.

Digital Library

[38]

David Ungar and David Patterson. What Price Small~a/k ? IF, EE Computer, 20(1), 1987.

Digital Library

[39]

David Ungar and Randall B. Smith. Self: The Power of Simplicity. In Proceedings of 2nd Annual A GM Conference on Object- Oriented Programming Systems, Languages and Applications (OOPSLA '87), pages 227- 241, 1987.

Digital Library

[40]

Jan Vitek, R. Nigel Horspool, and James S. Uhl. Compile-Time Analysis of Object- Oriented Programs. In International Conference on Compiler Construction, volume 641 of Lecture Notes in Computer Sciences, pages 237-250. Spriager-Verlag, 1992.

Digital Library

Cited By

Colnet DSonntag B(2015)Exploiting array manipulation habits to optimize garbage collection and type flow analysisSoftware—Practice & Experience10.1002/spe.230045:12(1639-1657)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1002/spe.2300
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 RMorandat F(2011)Perfect class hashing and numbering for object-oriented implementationSoftware—Practice & Experience10.1002/spe.102441:6(661-694)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1002/spe.1024
Show More Cited By

Index Terms

Efficient dynamic dispatch without virtual function tables: the SmallEiffel compiler
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language types

Recommendations

Efficient dynamic dispatch without virtual function tables: the SmallEiffel compiler
OOPSLA '97: Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

SmallEiffel is an Eiffel compiler which uses a fast simple type inference mechanism to remove most late binding calls, replacing them by static bindings. Starting from the system's entry point, it compiles only statically living code, which saves ...
Some New Efficient Second-Order Spectral-Null Codes with Small Lookup Tables

Tallini and Bose introduced a recursive method to construct second-order spectral-null codes which result in short (information length 16) base optimal second-order spectral-null codes that can be easily implemented either with table lookup or ...
An economic load dispatch and multiple environmental dispatch problem solution with microgrids using interior search algorithm

Microgrid is a novel small-scale system of the centralized electricity for a small-scale community such as villages and commercial area. Microgrid consists of micro-sources like distribution generator, solar and wind units. A microgrid is consummate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 32, Issue 10

Oct. 1997

344 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/263700

Chairmen:
Mary Loomis
Hewlett-Packard Labs
,
Toby Bloom
Engage Technologies, Inc.
,
Editor:
A. Michael Berman

Issue’s Table of Contents

OOPSLA '97: Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications
October 1997
345 pages
ISBN:0897919084
DOI:10.1145/263698
Chairmen:
Mary Loomis
Hewlett-Packard Labs
,
Toby Bloom
Engage Technologies, Inc.
,
Editor:
A. Michael Berman

Copyright © 1997 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 October 1997

Published in SIGPLAN Volume 32, Issue 10

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

58
Total Citations
View Citations
939
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Colnet DSonntag B(2015)Exploiting array manipulation habits to optimize garbage collection and type flow analysisSoftware—Practice & Experience10.1002/spe.230045:12(1639-1657)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1002/spe.2300
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 RMorandat F(2011)Perfect class hashing and numbering for object-oriented implementationSoftware—Practice & Experience10.1002/spe.102441:6(661-694)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1002/spe.1024
Krall AHorspool N(2010)Optimizations for Object-Oriented LanguagesThe Compiler Design Handbook10.1201/9781420040579.ch6Online publication date: 7-Mar-2010
https://doi.org/10.1201/9781420040579.ch6
Morandat FDucournau R(2010)Empirical assessment of C++-like implementations for multiple inheritanceProceedings of the Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems10.1145/1925801.1925803(1-5)Online publication date: 22-Jun-2010
https://dl.acm.org/doi/10.1145/1925801.1925803
Horspool NKrall A(2009)Optimizations for Object-Oriented LanguagesThe Compiler Design Handbook10.1201/9781420043839.ch13(13-1-13-29)Online publication date: 7-Dec-2009
https://doi.org/10.1201/9781420043839.ch13
Ducournau RMorandat FPrivat J(2009)Empirical assessment of object-oriented implementations with multiple inheritance and static typingACM SIGPLAN Notices10.1145/1639949.164009344:10(41-60)Online publication date: 25-Oct-2009
https://dl.acm.org/doi/10.1145/1639949.1640093
Gil JPugh WWeddell GZibin Y(2008)Two-dimensional bidirectional object layoutACM Transactions on Programming Languages and Systems10.1145/1387673.138767730:5(1-38)Online publication date: 4-Sep-2008
https://dl.acm.org/doi/10.1145/1387673.1387677
Pottier FGauthier N(2006)Polymorphic typed defunctionalization and concretizationHigher-Order and Symbolic Computation10.1007/s10990-006-8611-719:1(125-162)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.1007/s10990-006-8611-7
Gil JItai A(2006)The complexity of type analysis of object oriented programsECOOP’98 — Object-Oriented Programming10.1007/BFb0054109(601-634)Online publication date: 25-May-2006
https://doi.org/10.1007/BFb0054109
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 Issue’s Table of Contents